Bridges in Graph Tarjan's Algorithm in DSA C - 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

↓

Continue

↓

Else if v != parent[u

↓

Update low[u

↓

DFS complete for u

↓

Repeat for all nodes

↓

Output all bridges found

The algorithm runs DFS from each node, sets discovery and low times, updates low values based on neighbors, and identifies edges where low[v] > discovery[u] as bridges.

Execution Sample

DSA C

void dfs(int u, int parent) {
  discovery[u] = low[u] = time++;
  for (int v : adj[u]) {
    if (discovery[v] == -1) {
      dfs(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] > discovery[u]) bridges.push_back({u, v});
    } else if (v != parent) {
      low[u] = min(low[u], discovery[v]);
    }
  }
}

This code performs DFS, sets discovery and low times, updates low values, and detects bridges when low[v] > discovery[u].

Execution Table

Step	Operation	Current Node (u)	Neighbor (v)	discovery[]	low[]	Bridge Found	Visual State
1	Start DFS at node 0	0	-	[0:0,1:-1,2:-1,3:-1,4:-1]	[0:0,1:-1,2:-1,3:-1,4:-1]	No	Nodes: 0(discovery=0, low=0)
2	Visit neighbor 1 of 0	0	1	[0:0,1:-1,2:-1,3:-1,4:-1]	[0:0,1:-1,2:-1,3:-1,4:-1]	No	Nodes: 0(d=0,l=0)
3	DFS call on node 1	1	-	[0:0,1:1,2:-1,3:-1,4:-1]	[0:0,1:1,2:-1,3:-1,4:-1]	No	Nodes: 0(d=0,l=0),1(d=1,l=1)
4	Visit neighbor 0 of 1 (parent)	1	0	[0:0,1:1,2:-1,3:-1,4:-1]	[0:0,1:1,2:-1,3:-1,4:-1]	No	No update, 0 is parent
5	Visit neighbor 2 of 1	1	2	[0:0,1:1,2:-1,3:-1,4:-1]	[0:0,1:1,2:-1,3:-1,4:-1]	No	Nodes: 0(d=0,l=0),1(d=1,l=1)
6	DFS call on node 2	2	-	[0:0,1:1,2:2,3:-1,4:-1]	[0:0,1:1,2:2,3:-1,4:-1]	No	Nodes: 0(d=0,l=0),1(d=1,l=1),2(d=2,l=2)
7	Visit neighbor 1 of 2 (parent)	2	1	[0:0,1:1,2:2,3:-1,4:-1]	[0:0,1:1,2:2,3:-1,4:-1]	No	No update, 1 is parent
8	Visit neighbor 3 of 2	2	3	[0:0,1:1,2:2,3:-1,4:-1]	[0:0,1:1,2:2,3:-1,4:-1]	No	Nodes: 0(d=0,l=0),1(d=1,l=1),2(d=2,l=2)
9	DFS call on node 3	3	-	[0:0,1:1,2:2,3:3,4:-1]	[0:0,1:1,2:2,3:3,4:-1]	No	Nodes: 0(d=0,l=0),1(d=1,l=1),2(d=2,l=2),3(d=3,l=3)
10	Visit neighbor 2 of 3 (parent)	3	2	[0:0,1:1,2:2,3:3,4:-1]	[0:0,1:1,2:2,3:3,4:-1]	No	No update, 2 is parent
11	Visit neighbor 4 of 3	3	4	[0:0,1:1,2:2,3:3,4:-1]	[0:0,1:1,2:2,3:3,4:-1]	No	Nodes: 0(d=0,l=0),1(d=1,l=1),2(d=2,l=2),3(d=3,l=3)
12	DFS call on node 4	4	-	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	No	Nodes: 0(d=0,l=0),1(d=1,l=1),2(d=2,l=2),3(d=3,l=3),4(d=4,l=4)
13	Visit neighbor 3 of 4 (parent)	4	3	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	No	No update, 3 is parent
14	Backtrack to node 3	3	-	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	No	Update low[3] = min(3,4) = 3
15	Check bridge condition for edge 3-4	3	4	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	Yes	Bridge found: (3,4)
16	Backtrack to node 2	2	-	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	No	Update low[2] = min(2,3) = 2
17	Check bridge condition for edge 2-3	2	3	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	Yes	Bridge found: (2,3)
18	Backtrack to node 1	1	-	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	No	Update low[1] = min(1,2) = 1
19	Check bridge condition for edge 1-2	1	2	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	Yes	Bridge found: (1,2)
20	Backtrack to node 0	0	-	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	No	Update low[0] = min(0,1) = 0
21	Check bridge condition for edge 0-1	0	1	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	Yes	Bridge found: (0,1)
22	DFS complete for all nodes	-	-	[0:0,1:1,2:2,3:3,4:4]	[0:0,1:1,2:2,3:3,4:4]	No	All bridges found: (0,1), (1,2), (2,3), (3,4)

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

Variable Tracker

Variable	Start	After Step 1	After Step 6	After Step 12	After Step 15	After Step 17	After Step 19	After Step 21	Final
discovery	[-1,-1,-1,-1,-1]	[0,-1,-1,-1,-1]	[0,1,2,-1,-1]	[0,1,2,3,4]	[0,1,2,3,4]	[0,1,2,3,4]	[0,1,2,3,4]	[0,1,2,3,4]	[0,1,2,3,4]
low	[-1,-1,-1,-1,-1]	[0,-1,-1,-1,-1]	[0,1,2,-1,-1]	[0,1,2,3,4]	[0,1,2,3,4]	[0,1,2,3,4]	[0,1,2,3,4]	[0,1,2,3,4]	[0,1,2,3,4]
time	0	1	3	5	5	5	5	5	5
bridges	[]	[]	[]	[]	[(3,4)]	[(3,4),(2,3)]	[(3,4),(2,3),(1,2)]	[(3,4),(2,3),(1,2),(0,1)]	[(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, so removing u-v disconnects the graph. See steps 15, 17, 19, and 21 in execution_table.

Why do we ignore the parent node when updating low[u] with discovery[v]?

Because the parent edge is the one we came from, and including it would incorrectly lower low[u]. We only update low[u] with discovery[v] for back edges to ancestors other than the parent. See step 4 and 7 where neighbors equal parent are ignored.

What happens if the graph has cycles? How does low[] help?

Low[] tracks the earliest visited node reachable from a subtree. In cycles, low[v] will be less or equal to discovery[u], so no bridge is found on that edge. This prevents false bridge detection. See no bridges found on edges in cycles in the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 15, which edge is identified as a bridge?

A (3,4)

B (2,3)

C (1,2)

D (0,1)

💡 Hint

Check the 'Bridge Found' and 'Visual State' columns at step 15 in execution_table.

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

A Step 3

B Step 6

C Step 9

D Step 12

💡 Hint

Look at the discovery[] column in execution_table rows and find when discovery[2] changes from -1.

If node 3 had an additional back edge to node 0, how would low[3] change after visiting that neighbor?

A low[3] would remain the same

B low[3] would increase

C low[3] would decrease to discovery[0]

D low[3] would become discovery[3]

💡 Hint

Refer to the update rule low[u] = min(low[u], discovery[v]) for back edges in the code and execution_table.

Concept Snapshot

Tarjan's Algorithm finds bridges by DFS traversal.
Assign discovery and low times to each node.
For each edge u-v, if low[v] > discovery[u], edge u-v is a bridge.
Ignore parent edge when updating low values.
Low[u] tracks earliest reachable ancestor from u's subtree.
Bridges disconnect the graph if removed.

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 visited node reachable from its subtree. During DFS, for each neighbor v of node u, if v is unvisited, DFS is called recursively on v. After returning, low[u] is updated to the minimum of low[u] and low[v]. If low[v] is greater than discovery[u], the edge u-v is a bridge because v cannot reach u or any ancestor without this edge. If v is already visited and not the parent of u, low[u] is updated to the minimum of low[u] and discovery[v], accounting for back edges. The algorithm continues until all nodes are visited, and all bridges are recorded. This method efficiently identifies edges whose removal increases the number of connected components in the graph.