Bridges in Graph Tarjan's Algorithm in DSA Java

Mental Model

A bridge is an edge that, if removed, makes the graph split into more parts. Tarjan's algorithm finds these by exploring nodes deeply and tracking the earliest reachable node from each subtree.

Analogy: Imagine a city connected by roads. A bridge road is one that, if closed, cuts off some neighborhoods from others. We explore the city like a detective, marking when we first visit places and seeing if we can reach earlier places through other routes.

Graph:
  1 --- 2
  |     |
  3 --- 4

Edges:
1->2, 2->4, 4->3, 3->1

Bridge example:
  1 --- 2
        |
        5

Edge 2->5 is a bridge because removing it disconnects 5.

Dry Run Walkthrough

Input: Graph with edges: 1-2, 2-3, 3-4, 4-2, 3-5; find bridges

Goal: Identify edges that disconnect the graph if removed

Step 1: Start DFS at node 1, assign discovery time 1 and low 1

Node 1: disc=1, low=1
Stack: [1]
Visited: {1}

Why: We mark when we first visit node 1 to track earliest reachable nodes

Step 2: Move to node 2 from 1, assign disc=2, low=2

Node 2: disc=2, low=2
Stack: [1,2]
Visited: {1,2}

Why: We continue DFS to explore neighbors and track discovery times

Step 3: Move to node 3 from 2, assign disc=3, low=3

Node 3: disc=3, low=3
Stack: [1,2,3]
Visited: {1,2,3}

Why: We keep exploring deeper to find back edges and update lows

Step 4: Move to node 4 from 3, assign disc=4, low=4

Node 4: disc=4, low=4
Stack: [1,2,3,4]
Visited: {1,2,3,4}

Why: We explore node 4 to check for back edges

Step 5: From 4, find back edge to 2, update low[4] = min(low[4], disc[2]) = 2

Node 4: disc=4, low=2
Stack: [1,2,3,4]
Visited: {1,2,3,4}

Why: Back edge shows 4 can reach earlier node 2, so low[4] updates

Step 6: Backtrack to 3, update low[3] = min(low[3], low[4]) = 2

Node 3: disc=3, low=2
Stack: [1,2,3,4]
Visited: {1,2,3,4}

Why: Low of 3 updates because 4 can reach node 2

Step 7: From 3, move to node 5, assign disc=5, low=5

Node 5: disc=5, low=5
Stack: [1,2,3,4,5]
Visited: {1,2,3,4,5}

Why: Explore node 5 to check if it connects back

Step 8: Node 5 has no unvisited neighbors, backtrack to 3, check if low[5] > disc[3]

Node 5: disc=5, low=5
Node 3: disc=3, low=2
Stack: [1,2,3,4,5]

Why: Since low[5] > disc[3], edge 3-5 is a bridge

Result:

Bridges found: 3 -> 5
Graph edges remain connected except removing 3-5 splits node 5

Annotated Code

DSA Java

import java.util.*;

public class TarjanBridges {
    static class Graph {
        int V;
        List<List<Integer>> adj;

        Graph(int V) {
            this.V = V;
            adj = new ArrayList<>();
            for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        }

        void addEdge(int u, int v) {
            adj.get(u).add(v);
            adj.get(v).add(u);
        }
    }

    static int time = 0;

    static void dfs(int u, int parent, int[] disc, int[] low, boolean[] visited, Graph g, List<String> bridges) {
        visited[u] = true;
        disc[u] = low[u] = ++time; // discovery and low time

        for (int v : g.adj.get(u)) {
            if (v == parent) continue; // ignore edge to parent

            if (!visited[v]) {
                dfs(v, u, disc, low, visited, g, bridges); // explore deeper
                low[u] = Math.min(low[u], low[v]); // update low[u] after recursion

                if (low[v] > disc[u]) {
                    bridges.add((u + 1) + " -> " + (v + 1)); // bridge found
                }
            } else {
                low[u] = Math.min(low[u], disc[v]); // update low[u] for back edge
            }
        }
    }

    public static void main(String[] args) {
        Graph g = new Graph(5); // nodes 0 to 4 represent 1 to 5
        g.addEdge(0, 1); // 1-2
        g.addEdge(1, 2); // 2-3
        g.addEdge(2, 3); // 3-4
        g.addEdge(3, 1); // 4-2
        g.addEdge(2, 4); // 3-5

        int[] disc = new int[5];
        int[] low = new int[5];
        boolean[] visited = new boolean[5];
        List<String> bridges = new ArrayList<>();

        for (int i = 0; i < 5; i++) {
            if (!visited[i]) {
                dfs(i, -1, disc, low, visited, g, bridges);
            }
        }

        System.out.println("Bridges found:");
        for (String b : bridges) {
            System.out.println(b);
        }
    }
}

visited[u] = true; disc[u] = low[u] = ++time;

Mark node u as visited and assign discovery and low time

for (int v : g.adj.get(u)) { if (v == parent) continue;

Skip edge back to parent to avoid trivial cycle

if (!visited[v]) { dfs(v, u, disc, low, visited, g, bridges);

Explore unvisited neighbor v recursively

low[u] = Math.min(low[u], low[v]);

Update low[u] based on child's low value

if (low[v] > disc[u]) { bridges.add((u + 1) + " -> " + (v + 1)); }

If child's low is greater than u's discovery, edge u-v is a bridge

else { low[u] = Math.min(low[u], disc[v]); }

Update low[u] for back edge to ancestor

Output

Bridges found:

3 -> 5

Complexity Analysis

Time: O(V + E) because each node and edge is visited once during DFS

Space: O(V) for arrays to store discovery, low, visited states and recursion stack

vs Alternative: Naive approach checks connectivity after removing each edge with O(V*(V+E)) cost; Tarjan's is much faster

Edge Cases

Graph with no edges

No bridges found because no edges exist

DSA Java

for (int v : g.adj.get(u)) { if (v == parent) continue;

Graph with single node

No bridges found as no edges exist

DSA Java

for (int v : g.adj.get(u)) { if (v == parent) continue;

Graph with multiple disconnected components

Algorithm runs DFS on each component separately to find bridges

DSA Java

for (int i = 0; i < 5; i++) { if (!visited[i]) { dfs(i, -1, disc, low, visited, g, bridges); } }

When to Use This Pattern

When asked to find edges that disconnect a graph if removed, use Tarjan's bridge-finding algorithm because it efficiently finds these critical edges in one DFS pass.

Common Mistakes

Mistake: Not updating low[u] with disc[v] for back edges, missing bridges
Fix: Add else clause to update low[u] = min(low[u], disc[v]) when v is visited and not parent

Mistake: Checking low[v] >= disc[u] instead of low[v] > disc[u], incorrectly marking edges
Fix: Use strict greater than (>) to identify bridges correctly

Summary

Finds edges that, if removed, increase the number of disconnected parts in a graph.

Use when you need to identify critical connections in networks or graphs.

The key insight is tracking the earliest visited node reachable from each subtree to detect 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