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.

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 edges that, if removed, increase the number of connected components

C. To find the shortest path between two nodes

D. To count the total number of edges in the graph

Solution

1. Step 1: Understand the definition of a bridge

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

2. Step 2: Relate Tarjan's algorithm to bridges

   Tarjan's algorithm efficiently finds such edges by using DFS and low-link values.

3. Final Answer:

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

4. Quick Check:

   Bridges = edges increasing components when removed [OK]

Hint: Bridges disconnect graph parts when removed [OK]

Common Mistakes:

• Confusing bridges with shortest paths
• Thinking bridges detect cycles
• Assuming bridges count edges

2. Which of the following is the correct way to declare the array that stores discovery times in C for Tarjan's algorithm?

easy

A. int disc = new int[MAX];

B. int disc[];

C. int disc[MAX];

D. int[] disc = new int[MAX];

Solution

1. Step 1: Recall C array declaration syntax

   In C, arrays are declared with type and size like int arr[size];

2. Step 2: Match with discovery time array

   So, int disc[MAX]; is correct for fixed size MAX.

3. Final Answer:

   int disc[MAX]; -> Option C

4. Quick Check:

   C arrays use type name[size] [OK]

Hint: Use type name[size] for arrays in C [OK]

Common Mistakes:

• Using Java or C++ style array declarations in C
• Not specifying array size
• Using dynamic allocation syntax incorrectly

3. Consider the following code snippet for Tarjan's algorithm to find bridges. What will be printed?

void dfs(int u, int parent) {
  disc[u] = low[u] = ++time;
  for (int v : adj[u]) {
    if (disc[v] == -1) {
      dfs(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] > disc[u])
        printf("Bridge: %d - %d\n", u, v);
    } else if (v != parent) {
      low[u] = min(low[u], disc[v]);
    }
  }
}

// Graph edges:
// 0-1, 1-2, 2-0, 1-3
// Start dfs(0, -1);

medium

A. Bridge: 1 - 3

B. Bridge: 0 - 1

C. Bridge: 2 - 0

D. No bridges

Solution

1. Step 1: Analyze the graph structure

   The graph has a triangle 0-1-2 and an edge 1-3. Triangle edges are not bridges because removing them doesn't disconnect the graph.

2. Step 2: Apply Tarjan's condition for bridges

   Edge 1-3 is a bridge because removing it disconnects node 3.

3. Final Answer:

   Bridge: 1 - 3 -> Option A

4. Quick Check:

   Only edge 1-3 disconnects graph [OK]

Hint: Bridges disconnect nodes; triangle edges are safe [OK]

Common Mistakes:

• Thinking all edges in a cycle are bridges
• Ignoring parent check in DFS
• Misinterpreting low and disc values

4. The following code snippet is intended to find bridges using Tarjan's algorithm. What is the bug?

void dfs(int u, int parent) {
  disc[u] = low[u] = ++time;
  for (int v : adj[u]) {
    if (disc[v] == -1) {
      dfs(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] >= disc[u])
        printf("Bridge: %d - %d\n", u, v);
    } else if (v != parent) {
      low[u] = min(low[u], disc[v]);
    }
  }
}

medium

A. The condition should be low[v] > disc[u], not >=.

B. The disc array is not initialized.

C. The parent parameter is not used correctly.

D. The time variable is not incremented.

Solution

1. Step 1: Understand bridge condition in Tarjan's algorithm

   Bridge condition is low[v] > disc[u], meaning no back edge from v or its descendants to u or above.

2. Step 2: Identify the bug in condition

   Using >= incorrectly marks edges that are not bridges (like parent edges in cycles).

3. Final Answer:

   The condition should be low[v] > disc[u], not >=. -> Option A

4. Quick Check:

   Bridge if low[v] > disc[u] [OK]

Hint: Use strict greater than for bridge check [OK]

Common Mistakes:

• Using >= instead of > in bridge condition
• Not initializing discovery times
• Ignoring parent node in DFS

5. Given a connected undirected graph with 5 nodes and edges: 0-1, 1-2, 2-3, 3-4, 1-4, which edges are bridges according to Tarjan's algorithm?

hard

A. [0-1, 2-3]

B. [2-3, 3-4]

C. [1-4]

D. [0-1]

Solution

1. Step 1: Visualize the graph

   Edges: 0-1, 1-2, 2-3, 3-4, 1-4. The edge 1-4 creates a cycle with 1-2-3-4.

2. Step 2: Identify bridges

   Removing 0-1 disconnects node 0, so 0-1 is a bridge. Edges 2-3 and 3-4 are in cycle with 1-4, so not bridges.

3. Final Answer:

   [0-1] -> Option D

4. Quick Check:

   Only 0-1 disconnects graph [OK]

Hint: Edges in cycles are not bridges [OK]

Common Mistakes:

• Marking cycle edges as bridges
• Ignoring connectivity after edge removal
• Confusing bridge with articulation point