Bridges in Graph Tarjan's Algorithm in DSA Rust - Execution Trace

Concept Flow - Bridges in Graph Tarjan's Algorithm

Start DFS at node u

↓

Set discovery[u

↓

For each neighbor v of u

↓

If v not visited

↓

DFS(v)

↓

Update low[u

↓

If low[v

↓

Edge u-v is a bridge

↓

Record bridge

↓

Else if v visited and v != parent[u

↓

Update low[u

↓

End DFS at u

↓

Repeat for all nodes

↓

Output all bridges found

This flow shows how DFS explores nodes, sets discovery and low times, updates low values based on neighbors, and identifies bridges when low[v] > discovery[u].

Execution Sample

DSA Rust

fn dfs(u: usize, parent: usize, time: &mut usize, disc: &mut Vec<usize>, low: &mut Vec<usize>, graph: &Vec<Vec<usize>>, bridges: &mut Vec<(usize, usize)>) {
    *time += 1;
    disc[u] = *time;
    low[u] = *time;
    for &v in &graph[u] {
        if disc[v] == 0 {
            dfs(v, u, time, disc, low, graph, bridges);
            low[u] = low[u].min(low[v]);
            if low[v] > disc[u] {
                bridges.push((u, v));
            }
        } else if v != parent {
            low[u] = low[u].min(disc[v]);
        }
    }
}

This Rust DFS function finds bridges by tracking discovery and low times, updating them during traversal, and recording edges where low[v] > disc[u].

Execution Table

Step	Operation	Current Node (u)	Neighbor (v)	discovery	low	Bridges Found	Visual State
1	Start DFS at node 0	0	-	[0,0,0,0,0]	[0,0,0,0,0]	[]	Graph: 0--1--2--3--4 All nodes unvisited
2	Set discovery[0] and low[0]	0	-	[1,0,0,0,0]	[1,0,0,0,0]	[]	Node 0 visited, disc=1, low=1
3	Visit neighbor 1 of 0	0	1	[1,0,0,0,0]	[1,0,0,0,0]	[]	Edge 0-1 explored
4	Neighbor 1 not visited, DFS(1)	1	-	[1,0,0,0,0]	[1,0,0,0,0]	[]	Go deeper to node 1
5	Set discovery[1] and low[1]	1	-	[1,2,0,0,0]	[1,2,0,0,0]	[]	Node 1 visited, disc=2, low=2
6	Visit neighbor 0 of 1	1	0	[1,2,0,0,0]	[1,2,0,0,0]	[]	Neighbor 0 is parent, skip
7	Visit neighbor 2 of 1	1	2	[1,2,0,0,0]	[1,2,0,0,0]	[]	Edge 1-2 explored
8	Neighbor 2 not visited, DFS(2)	2	-	[1,2,0,0,0]	[1,2,0,0,0]	[]	Go deeper to node 2
9	Set discovery[2] and low[2]	2	-	[1,2,3,0,0]	[1,2,3,0,0]	[]	Node 2 visited, disc=3, low=3
10	Visit neighbor 1 of 2	2	1	[1,2,3,0,0]	[1,2,3,0,0]	[]	Neighbor 1 is parent, skip
11	Visit neighbor 3 of 2	2	3	[1,2,3,0,0]	[1,2,3,0,0]	[]	Edge 2-3 explored
12	Neighbor 3 not visited, DFS(3)	3	-	[1,2,3,0,0]	[1,2,3,0,0]	[]	Go deeper to node 3
13	Set discovery[3] and low[3]	3	-	[1,2,3,4,0]	[1,2,3,4,0]	[]	Node 3 visited, disc=4, low=4
14	Visit neighbor 2 of 3	3	2	[1,2,3,4,0]	[1,2,3,4,0]	[]	Neighbor 2 is parent, skip
15	Visit neighbor 4 of 3	3	4	[1,2,3,4,0]	[1,2,3,4,0]	[]	Edge 3-4 explored
16	Neighbor 4 not visited, DFS(4)	4	-	[1,2,3,4,0]	[1,2,3,4,0]	[]	Go deeper to node 4
17	Set discovery[4] and low[4]	4	-	[1,2,3,4,5]	[1,2,3,4,5]	[]	Node 4 visited, disc=5, low=5
18	Visit neighbor 3 of 4	4	3	[1,2,3,4,5]	[1,2,3,4,5]	[]	Neighbor 3 is parent, skip
19	End DFS at 4, back to 3	3	-	[1,2,3,4,5]	[1,2,3,4,5]	[]	Update low[3] = min(4,5) = 4
20	Check if low[4] > disc[3]	3	4	[1,2,3,4,5]	[1,2,3,4,5]	[(3,4)]	Bridge found: edge 3-4
21	End DFS at 3, back to 2	2	-	[1,2,3,4,5]	[1,2,3,4,5]	[(3,4)]	Update low[2] = min(3,4) = 3
22	Check if low[3] > disc[2]	2	3	[1,2,3,4,5]	[1,2,3,4,5]	[(3,4),(2,3)]	Bridge found: edge 2-3
23	End DFS at 2, back to 1	1	-	[1,2,3,4,5]	[1,2,3,4,5]	[(3,4),(2,3)]	Update low[1] = min(2,3) = 2
24	Check if low[2] > disc[1]	1	2	[1,2,3,4,5]	[1,2,3,4,5]	[(3,4),(2,3),(1,2)]	Bridge found: edge 1-2
25	End DFS at 1, back to 0	0	-	[1,2,3,4,5]	[1,2,3,4,5]	[(3,4),(2,3),(1,2)]	Update low[0] = min(1,2) = 1
26	Check if low[1] > disc[0]	0	1	[1,2,3,4,5]	[1,2,3,4,5]	[(3,4),(2,3),(1,2),(0,1)]	Bridge found: edge 0-1
27	DFS complete for all nodes	-	-	[1,2,3,4,5]	[1,2,3,4,5]	[(3,4),(2,3),(1,2),(0,1)]	All nodes visited, bridges found: (3,4), (2,3), (1,2), (0,1)
28	Termination	-	-	-	-	[(3,4),(2,3),(1,2),(0,1)]	No more nodes to visit

💡 All nodes visited, DFS complete, bridges identified where low[v] > discovery[u]

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 9	After Step 13	After Step 17	After Step 25	Final
discovery	[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]
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,5]	[1,2,3,4,5]
bridges	[]	[]	[]	[]	[]	[]	[(3,4),(2,3),(1,2)]	[(3,4),(2,3),(1,2),(0,1)]

Key Moments - 3 Insights

Why do we check if low[v] > discovery[u] to find a bridge?

Because if low[v] is greater than discovery[u], it means v and its descendants cannot reach u or any ancestor of u without using edge u-v. This confirms edge u-v is a bridge. See execution_table step 20 where this condition identifies edge (3,4) as a bridge.

Why do we skip updating low[u] when neighbor v is the parent?

The parent edge leads back to the node we came from, so it doesn't provide a back edge to an ancestor. Updating low[u] with parent's discovery time would be incorrect. See execution_table steps 6, 10, 14, and 18 where neighbors equal to parent are skipped.

What does the 'low' array represent during DFS?

The 'low' value of a node is the earliest discovery time reachable from that node by following DFS tree edges and at most one back edge. It helps detect if a subtree can connect back to ancestors. See variable_tracker for how 'low' updates after each DFS return.

Visual Quiz - 3 Questions

Look at the execution_table at step 20. What condition is true to identify edge (3,4) as a bridge?

A low[4] > discovery[3]

B discovery[4] > low[3]

C low[3] > discovery[4]

D discovery[3] > low[4]

💡 Hint

Check the 'Bridges Found' and 'Operation' columns at step 20 in execution_table.

At which step does the discovery time of node 2 get set?

A Step 5

B Step 13

C Step 9

D Step 17

💡 Hint

Look at the 'Set discovery' operations and the 'Current Node' column in execution_table.

If the graph had an extra edge from node 4 to node 1, how would the low[4] value change after DFS?

A It would increase

B It would decrease

C It would remain the same

D It would become zero

💡 Hint

Refer to variable_tracker and remember that back edges to ancestors lower the low value.

Concept Snapshot

Tarjan's Algorithm finds bridges by DFS traversal.
Each node gets discovery and low times.
Low[u] = earliest visited node reachable from u.
If low[v] > discovery[u], edge u-v is a bridge.
Skip parent node when updating low.
Record bridges during DFS backtracking.

Full Transcript

Tarjan's algorithm for finding bridges in a graph uses a depth-first search (DFS) approach. Each node is assigned a discovery time when first visited and a low value representing the earliest discovered node reachable from it. During DFS, for each neighbor, if it is unvisited, we recurse and update the low value of the current node based on the neighbor's low value. If the neighbor is already visited and not the parent, we update the low value with the neighbor's discovery time. An edge is a bridge if the low value of the neighbor is greater than the discovery time of the current node. This means the neighbor cannot reach any ancestor of the current node without that edge. The execution table traces these steps on a sample graph, showing discovery and low arrays, and when bridges are found. Key moments clarify why we check low[v] > discovery[u], why we skip the parent node, and what low values represent. The visual quiz tests understanding of these concepts with references to the execution table and variable tracker. The snapshot summarizes the algorithm's key points for quick recall.

Practice

1. What is the main purpose of Tarjan's algorithm when finding bridges in a graph?

easy

A. To detect cycles in a graph

B. To find the shortest path between two nodes

C. To find edges that, if removed, increase the number of connected components

D. To sort nodes in topological order

Solution

1. Step 1: Understand what a bridge is in a graph

   A bridge is an edge that, when removed, increases the number of connected components in the graph.

2. Step 2: Identify Tarjan's algorithm goal

   Tarjan's algorithm finds such edges efficiently by using DFS and tracking discovery and low times.

3. Final Answer:

   To find edges that, if removed, increase the number of connected components -> Option C

4. Quick Check:

   Bridges = edges increasing components [OK]

Hint: Bridges break connectivity when removed [OK]

Common Mistakes:

• Confusing bridges with cycles
• Thinking it finds shortest paths
• Mixing bridges with articulation points

2. Which of the following Rust code snippets correctly declares a vector to store adjacency lists for a graph with 5 nodes?

easy

A. let graph: Vec = vec![vec![0]; 5];

B. let graph: Vec<usize> = vec![0; 5];

C. let graph: Vec = vec![vec![]; 4];

D. let graph: Vec = vec![vec![]; 5];

Solution

1. Step 1: Understand adjacency list representation

   Each node has a vector of neighbors, so graph is a vector of vectors.

2. Step 2: Check vector initialization for 5 nodes

   vec![vec![]; 5] creates 5 empty vectors, one per node.

3. Final Answer:

   let graph: Vec = vec![vec![]; 5]; -> Option D

4. Quick Check:

   Adjacency list for 5 nodes = vec![vec![]; 5] [OK]

Hint: Use vec![vec![]; n] for adjacency lists [OK]

Common Mistakes:

• Using wrong vector type (Vec<usize> instead of Vec)
• Initializing with wrong size
• Filling inner vectors with zeros instead of empty

3. Given the following Rust code snippet implementing part of Tarjan's algorithm, what will be printed as bridges for the graph edges?

let edges = vec![(0,1), (1,2), (2,0), (1,3)];
// Graph: triangle 0-1-2 and a bridge edge 1-3
// After running Tarjan's algorithm, which edges are bridges?
println!("Bridges: {:?}", vec![(1,3)]);

medium

A. Bridges: [(1, 3)]

B. Bridges: [(0, 1), (1, 2), (2, 0)]

C. Bridges: []

D. Bridges: [(0, 3)]

Solution

1. Step 1: Analyze the graph structure

   The edges (0,1), (1,2), (2,0) form a cycle (triangle), so none are bridges.

2. Step 2: Identify the bridge edge

   The edge (1,3) connects node 3 to the triangle and is a bridge because removing it disconnects node 3.

3. Final Answer:

   Bridges: [(1, 3)] -> Option A

4. Quick Check:

   Only edge (1,3) breaks connectivity [OK]

Hint: Edges in cycles are not bridges [OK]

Common Mistakes:

• Marking cycle edges as bridges
• Ignoring leaf node connections
• Confusing bridge edges with articulation points

4. Identify the bug in this Rust snippet of Tarjan's algorithm for finding bridges:

fn dfs(u: usize, parent: usize, graph: &Vec, disc: &mut Vec<usize>, low: &mut Vec<usize>, time: &mut usize, bridges: &mut Vec<(usize, usize)>) {
    disc[u] = *time;
    low[u] = *time;
    *time += 1;
    for &v in &graph[u] {
        if v == parent {
            continue;
        }
        if disc[v] == 0 {
            dfs(v, u, graph, disc, low, time, bridges);
            low[u] = low[u].min(low[v]);
            if low[v] > disc[u] {
                bridges.push((u, v));
            }
        } else {
            low[u] = low[u].min(disc[v]);
        }
    }
}

medium

A. disc and low arrays are not initialized with zeros

B. The parent check should be if v != parent instead of v == parent

C. The time variable should be passed by value, not mutable reference

D. The condition low[v] > disc[u] should be low[v] < disc[u]

Solution

1. Step 1: Check initialization of disc and low arrays

   disc and low must be initialized with zeros to detect unvisited nodes (disc[v] == 0).

2. Step 2: Verify other logic correctness

   Parent check and time passing are correct; condition low[v] > disc[u] is correct for bridges.

3. Final Answer:

   disc and low arrays are not initialized with zeros -> Option A

4. Quick Check:

   Uninitialized disc causes wrong visited checks [OK]

Hint: Initialize disc and low with zeros before DFS [OK]

Common Mistakes:

• Not initializing disc and low arrays
• Wrong parent check condition
• Passing time by value instead of mutable reference

5. You have a graph with 6 nodes and edges: (0,1), (1,2), (2,0), (1,3), (3,4), (4,5), (5,3). Using Tarjan's algorithm, which edges are bridges in this graph?

hard

A. [(3, 4), (4, 5), (5, 3)]

B. [(1, 3)]

C. [(0, 1), (1, 2), (2, 0)]

D. [(1, 3), (3, 4)]

Solution

1. Step 1: Analyze graph components

   Nodes 0,1,2 form a cycle (triangle), so edges among them are not bridges. Nodes 3,4,5 form a cycle, so edges among them are not bridges.

2. Step 2: Identify bridge edges

   The edge (1,3) connects the two cycles. Removing (1,3) disconnects the graph, so it is a bridge.

3. Final Answer:

   [(1, 3)] -> Option B

4. Quick Check:

   Only edge connecting components is bridge [OK]

Hint: Bridges connect separate cycles or components [OK]

Common Mistakes:

• Marking cycle edges as bridges
• Ignoring connectivity between components
• Confusing bridges with articulation points