Bridges in Graph Tarjan's Algorithm in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a bridge in a graph?

A bridge is an edge in a graph that, if removed, increases the number of connected components. It disconnects part of the graph.

intermediate

What is the main idea behind Tarjan's algorithm for finding bridges?

Tarjan's algorithm uses DFS to assign discovery times and low values to nodes. An edge is a bridge if the low value of the connected node is greater than the discovery time of the current node.

intermediate

In Tarjan's algorithm, what does the 'low' value represent?

The 'low' value of a node is the earliest discovery time reachable from that node or its descendants, including back edges.

intermediate

Why do we ignore the parent node when updating low values in Tarjan's algorithm?

Because the parent edge is the one we came from, counting it would create a false back edge. We only consider other edges to update low values.

intermediate

How does Tarjan's algorithm detect a bridge during DFS traversal?

If for an edge (u, v), low[v] > disc[u], it means v cannot reach u or any ancestor of u without using edge (u, v), so (u, v) is a bridge.

What does the discovery time represent in Tarjan's algorithm?

A The lowest reachable node from a given node

B The order in which nodes are first visited during DFS

C The number of edges connected to a node

D The total number of nodes in the graph

Discovery time is the timestamp when a node is first visited in DFS.

When is an edge (u, v) considered a bridge in Tarjan's algorithm?

A When low[u] > disc[v]

B When disc[u] == disc[v]

C When low[v] > disc[u]

D When low[u] < disc[v]

If low[v] > disc[u], edge (u, v) is a bridge.

What is the purpose of the 'low' array in Tarjan's algorithm?

A To store the earliest visited vertex reachable from the subtree rooted at a node

B To count the number of edges in the graph

C To store the parent of each node

D To mark visited nodes

The 'low' array helps find back edges and bridges by tracking earliest reachable nodes.

Why do we skip the parent node when updating low values during DFS?

A Because the parent edge is the one we came from and not a back edge

B Because the parent node is always visited last

C Because the parent node has the highest discovery time

D Because the parent node is not connected

Skipping the parent avoids counting the edge we came from as a back edge.

What data structure is primarily used in Tarjan's algorithm to find bridges?

A Stack only

B Breadth-First Search (BFS) traversal

C Priority Queue

D Depth-First Search (DFS) traversal

Tarjan's algorithm uses DFS to explore nodes and compute discovery and low values.

Explain how Tarjan's algorithm finds bridges in a graph using discovery and low values.

Think about how DFS timestamps and back edges help find critical edges.

Describe the role of the 'low' array and why it is important in detecting bridges.

Focus on how low values track connectivity beyond the direct parent.

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