Bridges in Graph Tarjan's Algorithm in DSA Java - Build from Scratch

Bridges in Graph using Tarjan's Algorithm

📖 Scenario: Imagine you are a city planner checking a road network. Some roads are very important because if they break, parts of the city get disconnected. These special roads are called bridges. You want to find all such bridges in the city map.

🎯 Goal: You will build a program in Java that finds all the bridges in a given road network using Tarjan's algorithm. The program will show which roads are critical connections.

📋 What You'll Learn

Create a graph using adjacency lists with given edges

Use arrays to track discovery times and low values for each node

Implement Tarjan's DFS to find bridges

Print all bridges as pairs of nodes

💡 Why This Matters

🌍 Real World

Finding bridges in networks helps identify critical connections that keep systems connected, such as roads, communication lines, or social networks.

💼 Career

Understanding Tarjan's algorithm and graph traversal is important for software engineers working on network reliability, cybersecurity, and infrastructure planning.

1

Create the graph data structure

Create an integer variable n with value 5 for the number of nodes. Create an adjacency list called graph as an array of ArrayList<Integer> with size n. Add edges to graph exactly as follows: connect node 0 with 1, node 1 with 2, node 2 with 0, node 1 with 3, and node 3 with 4. Use undirected edges (add both directions).

DSA Java

// Create variable n and adjacency list graph
// Add edges as described

Hint

Use a loop to initialize each ArrayList in graph. Add edges in both directions for undirected graph.

2

Add arrays for discovery and low times

Create two integer arrays called disc and low of size n. Create a boolean array called visited of size n. Create an integer variable time and set it to 0.

DSA Java

import java.util.ArrayList;

public class BridgesTarjan {
    static int n = 5;
    static ArrayList[] graph = new ArrayList[n];

    public static void main(String[] args) {
        for (int i = 0; i ();
        }
        graph[0].add(1);
        graph[1].add(0);

        graph[1].add(2);
        graph[2].add(1);

        graph[2].add(0);
        graph[0].add(2);

        graph[1].add(3);
        graph[3].add(1);

        graph[3].add(4);
        graph[4].add(3);

        // Create disc, low, visited arrays and time variable
        // Your code here
    }
}

Hint

Use new int[n] for integer arrays and new boolean[n] for boolean array.

3

Implement Tarjan's DFS to find bridges

Create a static method dfs with parameters int u and int parent. Inside dfs, mark visited[u] as true. Set disc[u] and low[u] to time, then increment time. For each v in graph[u], if v is not visited, call dfs(v, u), then update low[u] to minimum of low[u] and low[v]. If low[v] > disc[u], print "Bridge found: u - v". Else if v is not parent, update low[u] to minimum of low[u] and disc[v]. In main, call dfs(0, -1).

DSA Java

import java.util.ArrayList;

public class BridgesTarjan {
    static int n = 5;
    static ArrayList[] graph = new ArrayList[n];
    static int[] disc = new int[n];
    static int[] low = new int[n];
    static boolean[] visited = new boolean[n];
    static int time = 0;

    public static void main(String[] args) {
        for (int i = 0; i ();
        }
        graph[0].add(1);
        graph[1].add(0);

        graph[1].add(2);
        graph[2].add(1);

        graph[2].add(0);
        graph[0].add(2);

        graph[1].add(3);
        graph[3].add(1);

        graph[3].add(4);
        graph[4].add(3);

        // Call dfs starting from node 0
        // Your code here
    }

    // Implement dfs method here
    // Your code here
}

Hint

Follow the Tarjan's algorithm steps carefully. Use recursion and update low and disc arrays. Print bridges when condition matches.

4

Print all bridges found

Run the program and observe the printed output. The program should print all bridges in the graph as lines like Bridge found: 1 - 3 and Bridge found: 3 - 4.

DSA Java

// Run the program and check output
// Your code here

Hint

The output should list all bridges found by the algorithm. Check console output carefully.

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