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

Concept Flow - Bridges in Graph Tarjan's Algorithm

Start DFS from a node

↓

Assign discovery time & low value

↓

For each neighbor

↓

If neighbor not visited

↓

Recurse DFS on neighbor

↓

Update low value of current node

↓

Check if low[neighbor

Yes↓

Edge is a bridge

No↓

Continue DFS

↓

End DFS

This flow shows how Tarjan's algorithm uses DFS to find bridges by tracking discovery and low times, updating low values, and identifying edges where low of neighbor is greater than discovery of current.

Execution Sample

DSA Java

void dfs(int u, int parent) {
  disc[u] = time;
  low[u] = time;
  time++;
  for (int v : graph[u]) {
    if (v == parent) continue;
    if (disc[v] == -1) {
      dfs(v, u);
      low[u] = Math.min(low[u], low[v]);
      if (low[v] > disc[u]) bridges.add(new int[]{u, v});
    } else {
      low[u] = Math.min(low[u], disc[v]);
    }
  }
}

This code runs DFS, assigns discovery and low times, updates low values, and detects bridges when low of neighbor is greater than discovery of current.

Execution Table

Step	Operation	Current Node (u)	Neighbor (v)	disc[u]	low[u]	disc[v]	low[v]	Bridge Found?	Bridges List	Visual State
1	Start DFS	0	-	-1	-1	-	-	No	[]	disc=[-1,-1,-1,-1], low=[-1,-1,-1,-1]
2	Assign disc & low	0	-	0	0	-	-	No	[]	disc=[0,-1,-1,-1], low=[0,-1,-1,-1]
3	Visit neighbor	0	1	0	0	-1	-1	No	[]	disc=[0,-1,-1,-1], low=[0,-1,-1,-1]
4	DFS on neighbor	1	-	-1	-1	-	-	No	[]	disc=[0,-1,-1,-1], low=[0,-1,-1,-1]
5	Assign disc & low	1	-	1	1	-	-	No	[]	disc=[0,1,-1,-1], low=[0,1,-1,-1]
6	Visit neighbor	1	0	1	1	0	0	No	[]	disc=[0,1,-1,-1], low=[0,1,-1,-1]
7	Neighbor is parent, skip	1	0	1	1	0	0	No	[]	disc=[0,1,-1,-1], low=[0,1,-1,-1]
8	Visit neighbor	1	2	1	1	-1	-1	No	[]	disc=[0,1,-1,-1], low=[0,1,-1,-1]
9	DFS on neighbor	2	-	-1	-1	-	-	No	[]	disc=[0,1,-1,-1], low=[0,1,-1,-1]
10	Assign disc & low	2	-	2	2	-	-	No	[]	disc=[0,1,2,-1], low=[0,1,2,-1]
11	Visit neighbor	2	1	2	2	1	1	No	[]	disc=[0,1,2,-1], low=[0,1,2,-1]
12	Neighbor is parent, skip	2	1	2	2	1	1	No	[]	disc=[0,1,2,-1], low=[0,1,2,-1]
13	Visit neighbor	2	3	2	2	-1	-1	No	[]	disc=[0,1,2,-1], low=[0,1,2,-1]
14	DFS on neighbor	3	-	-1	-1	-	-	No	[]	disc=[0,1,2,-1], low=[0,1,2,-1]
15	Assign disc & low	3	-	3	3	-	-	No	[]	disc=[0,1,2,3], low=[0,1,2,3]
16	Visit neighbor	3	2	3	3	2	2	No	[]	disc=[0,1,2,3], low=[0,1,2,3]
17	Neighbor is parent, skip	3	2	3	3	2	2	No	[]	disc=[0,1,2,3], low=[0,1,2,3]
18	End DFS on 3	3	-	3	3	-	-	No	[]	low[3] remains 3
19	Return to 2, update low[2]	2	3	2	2	3	3	No	[]	low[2] = min(2, low[3]=3) = 2
20	Check bridge 2-3	2	3	2	2	3	3	Yes	[[2,3]]	low[3] (3) > disc[2] (2), bridge found
21	Return to 1, update low[1]	1	2	1	1	2	2	No	[[2,3]]	low[1] = min(1, low[2]=2) = 1
22	Check bridge 1-2	1	2	1	1	2	2	Yes	[[2,3],[1,2]]	low[2] (2) > disc[1] (1), bridge found
23	Return to 0, update low[0]	0	1	0	0	1	1	No	[[2,3],[1,2]]	low[0] = min(0, low[1]=1) = 0
24	Check bridge 0-1	0	1	0	0	1	1	Yes	[[2,3],[1,2],[0,1]]	low[1] (1) > disc[0] (0), bridge found
25	DFS complete	-	-	-	-	-	-	No	[[2,3],[1,2],[0,1]]	All nodes visited, DFS ends

💡 DFS ends after all nodes visited and all edges checked for bridges

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 10	After Step 15	After Step 18	After Step 19	After Step 21	After Step 23	Final
disc	[-1,-1,-1,-1]	[0,-1,-1,-1]	[0,1,-1,-1]	[0,1,2,-1]	[0,1,2,3]	[0,1,2,3]	[0,1,2,3]	[0,1,2,3]	[0,1,2,3]	[0,1,2,3]
low	[-1,-1,-1,-1]	[0,-1,-1,-1]	[0,1,-1,-1]	[0,1,2,-1]	[0,1,2,3]	[0,1,2,3]	[0,1,2,3]	[0,1,2,3]	[0,1,2,3]	[0,1,2,3]
bridges	[]	[]	[]	[]	[]	[]	[]	[[2,3],[1,2]]	[[2,3],[1,2],[0,1]]	[[2,3],[1,2],[0,1]]

Key Moments - 3 Insights

Why do we skip the neighbor if it is the parent node during DFS?

We skip the parent to avoid immediately going back on the edge we came from, preventing false bridge detection. See execution_table rows 6-7 and 11-12 where neighbors equal parent are skipped.

Why is an edge a bridge only if low[neighbor] > disc[current]?

Because low[neighbor] > disc[current] means neighbor cannot reach current or any ancestor except through current, so removing edge disconnects graph. See execution_table rows 22 and 24 where this condition triggers bridge detection.

How do discovery and low arrays help find bridges?

Discovery time marks when a node is first visited; low tracks earliest reachable ancestor. Comparing them shows if a subtree connects back to ancestors. See variable_tracker and execution_table steps updating disc and low.

Visual Quiz - 3 Questions

Look at the execution_table at step 22, what is the bridge found?

A [1, 2]

B [0, 1]

C [2, 3]

D No bridge

💡 Hint

Check the 'Bridge Found?' and 'Bridges List' columns at step 22 in execution_table.

At which step does the DFS on node 3 end?

A Step 15

B Step 18

C Step 19

D Step 21

💡 Hint

Look at the 'Operation' column at step 18 in execution_table.

If we did not skip the parent neighbor in DFS, what would happen?

A Algorithm would detect false bridges

B Algorithm would run faster

C No change in bridge detection

D Algorithm would miss some bridges

💡 Hint

Refer to key_moments about skipping parent neighbors and execution_table rows 6-7.

Concept Snapshot

Tarjan's Algorithm for Bridges:
- Use DFS to assign discovery (disc) and low values
- low[u] = earliest visited vertex reachable from u
- For edge u-v, if low[v] > disc[u], edge is a bridge
- Skip parent node in DFS to avoid false positives
- Bridges disconnect graph if removed

Full Transcript

Tarjan's algorithm finds bridges in a graph by running a depth-first search (DFS). Each node gets a discovery time when first visited and a low value representing the earliest visited node reachable from it. During DFS, for each neighbor, if it is not visited, we recurse and update the low value of the current node. If the low value of the neighbor is greater than the discovery time of the current node, the edge between them is a bridge. We skip the parent node in DFS to avoid going back immediately and falsely detecting bridges. The algorithm ends when all nodes are visited and all edges checked. The key arrays are disc and low, and the bridges list stores all found bridges.

Practice

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

easy

A. To identify edges that, if removed, increase the number of connected components

B. To find the shortest path between two nodes

C. To detect cycles in a graph

D. To sort nodes in topological order

Solution

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

   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 is used to find such edges efficiently by using DFS and tracking discovery and low times.

3. Final Answer:

   To identify edges that, if removed, increase the number of connected components -> Option A

4. Quick Check:

   Bridges = edges increasing components [OK]

Hint: Bridges split graph into more parts when removed [OK]

Common Mistakes:

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

2. Which of the following Java code snippets correctly initializes the arrays used for discovery and low times in Tarjan's algorithm for a graph with n nodes?

easy

A. int[] disc = new int[n]; int[] low = new int[n]; Arrays.fill(disc, 0); Arrays.fill(low, 0);

B. int[] disc = new int[n]; int[] low = new int[n];

C. int disc[] = new int[n]; int low[] = new int[n]; disc = null; low = null;

D. int[] disc = new int[n]; int[] low = new int[n]; Arrays.fill(disc, -1); Arrays.fill(low, -1);

Solution

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

   Both arrays must be initialized with -1 to indicate unvisited nodes.

2. Step 2: Verify correct Java syntax and usage

   int[] disc = new int[n]; int[] low = new int[n]; Arrays.fill(disc, -1); Arrays.fill(low, -1); correctly creates arrays and fills them with -1 using Arrays.fill.

3. Final Answer:

   int[] disc = new int[n]; int[] low = new int[n]; Arrays.fill(disc, -1); Arrays.fill(low, -1); -> Option D

4. Quick Check:

   Arrays initialized with -1 = int[] disc = new int[n]; int[] low = new int[n]; Arrays.fill(disc, -1); Arrays.fill(low, -1); [OK]

Hint: Initialize discovery and low arrays with -1 for unvisited [OK]

Common Mistakes:

• Not filling arrays with -1, causing wrong visited checks
• Setting arrays to null after creation
• Filling arrays with 0 instead of -1

3. Consider the following Java code snippet implementing part of Tarjan's algorithm for bridges detection. What will be the output list of bridges for the given graph edges?

int n = 5;
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
graph.get(0).add(1); graph.get(1).add(0);
graph.get(1).add(2); graph.get(2).add(1);
graph.get(2).add(0); graph.get(0).add(2);
graph.get(1).add(3); graph.get(3).add(1);
graph.get(3).add(4); graph.get(4).add(3);

// After running Tarjan's bridge detection, which edges are bridges?

medium

A. [[0, 1], [1, 2]]

B. [[0, 2], [2, 1]]

C. [[1, 3], [3, 4]]

D. []

Solution

1. Step 1: Analyze the graph structure

   The graph has edges forming a triangle between nodes 0,1,2 and a chain 1-3-4.

2. Step 2: Identify bridges

   Edges in the triangle are not bridges because removing them doesn't disconnect the graph. Edges (1,3) and (3,4) are bridges because removing them increases components.

3. Final Answer:

   [[1, 3], [3, 4]] -> Option C

4. Quick Check:

   Bridges separate graph parts = [[1, 3], [3, 4]] [OK]

Hint: Edges in cycles are not bridges; chains are [OK]

Common Mistakes:

• Marking edges in cycles as bridges
• Ignoring edges that disconnect graph
• Confusing node order in edges

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

void dfs(int u, int parent) {
    disc[u] = time;
    low[u] = time;
    for (int v : graph.get(u)) {
        if (v == parent) continue;
        if (disc[v] == -1) {
            dfs(v, u);
            low[u] = Math.min(low[u], low[v]);
            if (low[v] > disc[u]) {
                bridges.add(new int[]{u, v});
            }
        } else {
            low[u] = Math.min(low[u], disc[v]);
        }
    }
}

medium

A. The time variable is not incremented correctly

B. The condition to add a bridge should be low[v] >= disc[u]

C. The else block should update low[u] with low[v], not disc[v]

D. The parent check should be if (v != parent) instead of if (v == parent)

Solution

1. Step 1: Check time increment usage

   The code assigns the current time to disc[u] and low[u] but fails to increment the time variable. This causes all nodes to receive the same discovery and low values, breaking the algorithm.

2. Step 2: Verify other potential issues

   The bridge condition (low[v] > disc[u]) is correct. The else block properly updates low[u] with disc[v] for back edges. The parent skip is correctly implemented.

3. Final Answer:

   The time variable is not incremented correctly -> Option A

4. Quick Check:

   Time increment missing [OK]

Hint: Check time increments carefully in DFS [OK]

Common Mistakes:

• Changing bridge condition incorrectly
• Updating low[u] with wrong values
• Misusing parent check condition

5. Given a connected undirected graph with n nodes and m edges, you want to find all bridges using Tarjan's algorithm. Which of the following modifications will correctly handle disconnected graphs as well?

hard

A. Only run DFS from node 0 since graph is connected

B. Run DFS from every node that is unvisited to cover all components

C. Reset discovery and low arrays to zero before each DFS call

D. Increase the time variable by 2 after each DFS call

Solution

1. Step 1: Understand the problem with disconnected graphs

   Tarjan's algorithm assumes DFS covers all nodes. For disconnected graphs, DFS from one node misses others.

2. Step 2: Correct approach for disconnected graphs

   Run DFS from every unvisited node to ensure all components are covered and bridges found.

3. Final Answer:

   Run DFS from every node that is unvisited to cover all components -> Option B

4. Quick Check:

   DFS from all unvisited nodes = Run DFS from every node that is unvisited to cover all components [OK]

Hint: Run DFS on all unvisited nodes for disconnected graphs [OK]

Common Mistakes:

• Assuming graph is always connected
• Resetting arrays incorrectly
• Changing time increments unnecessarily