Bridges in Graph Tarjan's Algorithm in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Tarjan's Algorithm for Bridges

What is the output (list of bridges) of the following Java code implementing Tarjan's algorithm on the given graph?

DSA Java

import java.util.*;

public class BridgesTarjan {
    private int time = 0;
    private List<List<Integer>> graph;
    private int[] disc, low;
    private boolean[] visited;
    private List<String> bridges;

    public BridgesTarjan(int n) {
        graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        disc = new int[n];
        low = new int[n];
        visited = new boolean[n];
        bridges = new ArrayList<>();
    }

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

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

    public List<String> findBridges() {
        for (int i = 0; i < graph.size(); i++) {
            if (!visited[i]) dfs(i, -1);
        }
        Collections.sort(bridges);
        return bridges;
    }

    public static void main(String[] args) {
        BridgesTarjan bt = new BridgesTarjan(5);
        bt.addEdge(0, 1);
        bt.addEdge(1, 2);
        bt.addEdge(2, 0);
        bt.addEdge(1, 3);
        bt.addEdge(3, 4);
        List<String> result = bt.findBridges();
        System.out.println(result);
    }
}

A ["1-3", "3-4"]

B ["0-1", "1-3", "3-4"]

C ["0-1", "2-0"]

D ["1-2", "2-0"]

💡 Hint

Focus on edges whose removal increases the number of connected components.

Edges 1-3 and 3-4 are bridges because removing them disconnects the graph. The triangle 0-1-2 has no bridges.

🧠 Conceptual

intermediate

Understanding Low and Discovery Times

In Tarjan's algorithm for finding bridges, what does the 'low' array represent for each node?

A The number of edges connected to the node

B The earliest discovery time reachable from the node including back edges

C The depth of the node in the DFS tree

D The total number of nodes reachable from the node

💡 Hint

Think about how 'low' helps detect back edges.

'Low' stores the smallest discovery time reachable from the node by traversing zero or more tree edges and then possibly one back edge.

🔧 Debug

advanced

Identify the Bug in Bridge Detection Code

What error will the following code cause when running Tarjan's algorithm for bridges?

DSA Java

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

A It will cause an infinite recursion

B It will cause a runtime NullPointerException

C It will correctly identify all bridges

D It will incorrectly identify articulation points instead of bridges

💡 Hint

Check the condition for bridges vs articulation points.

The condition 'low[v] >= disc[u]' is used for articulation points, not bridges. Bridges require 'low[v] > disc[u]'.

❓ Predict Output

advanced

Output of Bridges in a Disconnected Graph

What is the output of the following code that finds bridges in a disconnected graph?

DSA Java

import java.util.*;

public class BridgesTarjan {
    private int time = 0;
    private List<List<Integer>> graph;
    private int[] disc, low;
    private boolean[] visited;
    private List<String> bridges;

    public BridgesTarjan(int n) {
        graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        disc = new int[n];
        low = new int[n];
        visited = new boolean[n];
        bridges = new ArrayList<>();
    }

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

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

    public List<String> findBridges() {
        for (int i = 0; i < graph.size(); i++) {
            if (!visited[i]) dfs(i, -1);
        }
        Collections.sort(bridges);
        return bridges;
    }

    public static void main(String[] args) {
        BridgesTarjan bt = new BridgesTarjan(6);
        bt.addEdge(0, 1);
        bt.addEdge(1, 2);
        bt.addEdge(3, 4);
        bt.addEdge(4, 5);
        List<String> result = bt.findBridges();
        System.out.println(result);
    }
}

A ["3-4", "4-5"]

B ["0-1", "1-2"]

C ["0-1", "1-2", "3-4", "4-5"]

D []

💡 Hint

Consider each disconnected component separately.

Each edge in the two disconnected chains is a bridge because removing it increases components.

🧠 Conceptual

expert

Why Tarjan's Algorithm Uses DFS Time Stamps

Why does Tarjan's algorithm assign discovery times to nodes during DFS when finding bridges?

A To track the order nodes are visited and detect back edges to ancestors

B To count the total number of nodes in the graph

C To assign unique IDs for printing results

D To measure the distance from the root node

💡 Hint

Think about how the algorithm detects cycles and connectivity.

Discovery times help identify back edges to ancestors, which is essential to find if an edge is a bridge.

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