Articulation Points in Graph in DSA Rust - Execution Trace

Concept Flow - Articulation Points in Graph

Start DFS at a node

↓

Mark node visited, set discovery & low time

↓

For each neighbor

↓

If neighbor not visited

↓

Recurse DFS

↓

Check articulation condition

↓

Mark articulation point if condition met

↓

Repeat for all nodes

↓

End: List all articulation points

Start DFS from each node, track discovery and low times, update low values through recursion, and mark nodes as articulation points when conditions are met.

Execution Sample

DSA Rust

fn dfs(u: usize, parent: Option<usize>, graph: &Vec<Vec<usize>>, visited: &mut Vec<bool>, disc: &mut Vec<usize>, low: &mut Vec<usize>, time: &mut usize, ap: &mut Vec<bool>) {
    visited[u] = true;
    *time += 1;
    disc[u] = *time;
    low[u] = *time;
    let mut children = 0;
    for &v in &graph[u] {
        if !visited[v] {
            children += 1;
            dfs(v, Some(u), graph, visited, disc, low, time, ap);
            low[u] = low[u].min(low[v]);
            if parent.is_none() && children > 1 {
                ap[u] = true;
            }
            if parent.is_some() && low[v] >= disc[u] {
                ap[u] = true;
            }
        } else if Some(v) != parent {
            low[u] = low[u].min(disc[v]);
        }
    }
}

This DFS function finds articulation points by tracking discovery and low times, updating low values, and marking points based on conditions.

Execution Table

Step	Operation	Node Visited	Parent	Children Count	Discovery Time (disc)	Low Time (low)	Articulation Point Marked	Graph State (Adjacency)	Visual State
1	Start DFS	0	None	0	1	1	No	[0:[1,2],1:[0,2],2:[0,1,3,4],3:[2,4],4:[2,3]]	Visited: {0}, disc: {0:1}, low: {0:1}, AP: {}
2	Visit neighbor	1	0	0	2	2	No	[...]	Visited: {0,1}, disc: {0:1,1:2}, low: {0:1,1:2}, AP: {}
3	Visit neighbor	2	0	0	3	3	No	[...]	Visited: {0,1,2}, disc: {0:1,1:2,2:3}, low: {0:1,1:2,2:3}, AP: {}
4	Visit neighbor	3	2	0	4	4	No	[...]	Visited: {0,1,2,3}, disc: {0:1,1:2,2:3,3:4}, low: {0:1,1:2,2:3,3:4}, AP: {}
5	Visit neighbor	4	3	0	5	5	No	[...]	Visited: {0,1,2,3,4}, disc: {0:1,1:2,2:3,3:4,4:5}, low: {0:1,1:2,2:3,3:4,4:5}, AP: {}
6	Backtrack	4	3	0	5	4	No	[...]	Update low[3] = min(4,5) = 4
7	Backtrack	3	2	1	4	3	No	[...]	Update low[2] = min(3,4) = 3
8	Visit neighbor	4	2	1	5	4	No	[...]	Already visited, update low[2] = min(3,5) = 3
9	Check articulation	2	0	2	3	3	Yes	[...]	low[3] >= disc[2], mark 2 as AP
10	Backtrack	2	0	2	3	1	No	[...]	Update low[0] = min(1,3) = 1
11	Check articulation	0	None	2	1	1	Yes	[...]	Root with >1 child, mark 0 as AP
12	End DFS	-	-	-	-	-	-	[...]	All nodes visited, articulation points: {0,2}

💡 All nodes visited, DFS complete, articulation points identified.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	After Step 10	After Step 11	Final
visited	[false,false,false,false,false]	[true,false,false,false,false]	[true,true,false,false,false]	[true,true,true,false,false]	[true,true,true,true,false]	[true,true,true,true,true]	[true,true,true,true,true]	[true,true,true,true,true]	[true,true,true,true,true]	[true,true,true,true,true]	[true,true,true,true,true]	[true,true,true,true,true]	[true,true,true,true,true]
disc	[0,0,0,0,0]	[1,0,0,0,0]	[1,2,0,0,0]	[1,2,3,0,0]	[1,2,3,4,0]	[1,2,3,4,5]	[1,2,3,4,5]	[1,2,3,4,5]	[1,2,3,4,5]	[1,2,3,4,5]	[1,2,3,4,5]	[1,2,3,4,5]	[1,2,3,4,5]
low	[0,0,0,0,0]	[1,0,0,0,0]	[1,2,0,0,0]	[1,2,3,0,0]	[1,2,3,4,0]	[1,2,3,4,5]	[1,2,3,4,4]	[1,2,3,4,4]	[1,2,3,4,4]	[1,2,3,4,4]	[1,2,3,4,1]	[1,2,3,4,1]	[1,2,3,4,1]
ap	[false,false,false,false,false]	[false,false,false,false,false]	[false,false,false,false,false]	[false,false,false,false,false]	[false,false,false,false,false]	[false,false,false,false,false]	[false,false,false,false,false]	[false,false,true,false,false]	[false,false,true,false,false]	[true,false,true,false,false]	[true,false,true,false,false]	[true,false,true,false,false]	[true,false,true,false,false]
children	0	0	0	0	0	0	1	2	2	2	2	2	2

Key Moments - 3 Insights

Why do we mark a node as an articulation point when it is the root and has more than one child?

Because the root node with multiple children means removing it disconnects the graph. This is shown in execution_table row 11 where the root node 0 is marked AP after having 2 children.

Why do we update the low time of a node with the discovery time of an already visited neighbor?

This happens when we find a back edge to an ancestor, which helps track the earliest reachable ancestor. See execution_table row 8 where low[2] is updated using disc[4].

Why do we check if low[v] >= disc[u] to mark articulation points for non-root nodes?

Because if the lowest reachable vertex from v is not before u, removing u disconnects v's subtree. This is shown in execution_table row 9 where node 2 is marked AP.

Visual Quiz - 3 Questions

Look at the execution_table at step 9, which node is marked as an articulation point?

A Node 2

B Node 3

C Node 0

D Node 4

💡 Hint

Check the 'Articulation Point Marked' column at step 9 in execution_table.

At which step does the root node get marked as an articulation point?

A Step 6

B Step 11

C Step 3

D Step 9

💡 Hint

Look for the root node marking in the 'Articulation Point Marked' column in execution_table.

If node 4 was not connected to node 3, how would the articulation points change?

A Node 3 would become an articulation point

B Node 4 would become an articulation point

C Node 2 would no longer be an articulation point

D No change in articulation points

💡 Hint

Consider how removing node 3 would affect connectivity without the edge to node 4.

Concept Snapshot

Articulation Points in Graph:
- Use DFS to assign discovery and low times.
- Update low[u] = min(low[u], low[v]) after visiting neighbors.
- Root node with >1 child is AP.
- Non-root node u is AP if low[v] >= disc[u].
- Helps find nodes whose removal disconnects the graph.

Full Transcript

Articulation points are nodes in a graph which, if removed, increase the number of connected components. We find them using DFS by tracking discovery and low times for each node. The low time tells the earliest visited vertex reachable from the subtree rooted at that node. If a root node has more than one child, it is an articulation point. For other nodes, if any child's low time is greater or equal to the node's discovery time, that node is an articulation point. This process is done by recursively visiting nodes, updating low values, and marking articulation points accordingly.

Practice

1. What is an articulation point in a graph?

easy

A. A vertex with the highest degree in the graph

B. A vertex that, when removed, increases the number of connected components

C. A vertex that has no edges connected to it

D. A vertex that forms a cycle with its neighbors

Solution

1. Step 1: Understand articulation point definition

   An articulation point is a vertex that, if removed, breaks the graph into more pieces (connected components).

2. Step 2: Compare options with definition

   Only A vertex that, when removed, increases the number of connected components matches this definition exactly.

3. Final Answer:

   A vertex that, when removed, increases the number of connected components -> Option B

4. Quick Check:

   Articulation point = vertex increasing components when removed [OK]

Hint: Articulation point breaks graph connectivity when removed [OK]

Common Mistakes:

• Confusing articulation point with highest degree vertex
• Thinking articulation point is a vertex with no edges
• Mixing articulation point with cycle forming vertex

2. Which Rust data structure is best suited to store the graph for finding articulation points?

easy

A. Vec (adjacency list)

B. HashMap

C. Vec<usize> (simple list)

D. String

Solution

1. Step 1: Identify graph representation for articulation points

   Graphs are commonly stored as adjacency lists for efficient traversal and edge lookup.

2. Step 2: Match Rust data structures

   Vec represents adjacency lists well, storing neighbors for each vertex.

3. Final Answer:

   Vec (adjacency list) -> Option A

4. Quick Check:

   Adjacency list = Vec in Rust [OK]

Hint: Use adjacency list (Vec of Vec) for graph edges [OK]

Common Mistakes:

• Using HashMap which is unrelated
• Using simple Vec<usize> which can't store edges
• Using String which is not a graph structure

3. What is the output of the following Rust code snippet that finds articulation points in a graph?

let graph = vec![
    vec![1, 2],
    vec![0, 2],
    vec![0, 1, 3],
    vec![2, 4],
    vec![3]
];
// Articulation points found: [2, 3]
println!("{:?}", find_articulation_points(&graph));

medium

A. [1, 4]

B. [0, 1]

C. [2, 3]

D. []

Solution

1. Step 1: Analyze graph structure

   Vertices 2 and 3 connect parts of the graph such that removing them increases components.

2. Step 2: Identify articulation points

   Removing vertex 2 disconnects vertex 3 and 4; removing vertex 3 disconnects vertex 4.

3. Final Answer:

   [2, 3] -> Option C

4. Quick Check:

   Vertices 2 and 3 are articulation points [OK]

Hint: Check vertices whose removal splits graph [OK]

Common Mistakes:

• Choosing vertices with no articulation role
• Ignoring connectivity after removal
• Assuming leaf nodes are articulation points

4. Identify the bug in this Rust code snippet for finding articulation points:

fn dfs(u: usize, graph: &Vec, visited: &mut Vec<bool>, disc: &mut Vec<usize>, low: &mut Vec<usize>, parent: &mut Vec, time: &mut usize) {
    visited[u] = true;
    disc[u] = *time;
    low[u] = *time;
    *time += 1;

    for &v in &graph[u] {
        if !visited[v] {
            parent[v] = Some(u);
            dfs(v, graph, visited, disc, low, parent, time);
            low[u] = low[u].min(low[v]);
        } else if v != parent[u].unwrap() {
            low[u] = low[u].min(disc[v]);
        }
    }
}

medium

A. Not updating low[v] after recursion

B. Not marking visited[u] as true

C. Not incrementing time variable

D. Using unwrap() on parent[u] without checking if it is Some

Solution

1. Step 1: Check unwrap usage on parent[u]

   parent[u] may be None for root node, unwrap() causes panic if None.

2. Step 2: Identify safe handling

   Code should check if parent[u] is Some before unwrap or handle root separately.

3. Final Answer:

   Using unwrap() on parent[u] without checking if it is Some -> Option D

4. Quick Check:

   Unsafe unwrap on Option causes runtime panic [OK]

Hint: Check Option unwrap safety for root node [OK]

Common Mistakes:

• Ignoring root node parent None case
• Assuming unwrap() is always safe
• Missing visited marking (actually present here)

5. Given a graph with multiple disconnected components, how should the articulation points algorithm be adapted in Rust to find all articulation points?

hard

A. Run DFS from every unvisited vertex to cover all components

B. Run DFS only from vertex 0 assuming graph is connected

C. Run BFS instead of DFS for articulation points

D. Ignore disconnected components as they have no articulation points

Solution

1. Step 1: Understand disconnected graph scenario

   Articulation points can exist in any component, so all must be checked.

2. Step 2: Adapt algorithm to run DFS on all components

   Run DFS from every unvisited vertex to cover all disconnected parts.

3. Final Answer:

   Run DFS from every unvisited vertex to cover all components -> Option A

4. Quick Check:

   Multiple DFS runs cover all components [OK]

Hint: Run DFS on all unvisited nodes for full coverage [OK]

Common Mistakes:

• Assuming graph is always connected
• Using BFS which doesn't track articulation points easily
• Ignoring disconnected components