Bridges in Graph Tarjan's Algorithm in DSA C#

Mental Model

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

Analogy: Imagine a network of islands connected by bridges. Some bridges are the only way to reach certain islands. If you remove such a bridge, the islands get separated. Tarjan's algorithm finds these critical bridges by walking through the islands and remembering the earliest island reachable from each path.

Graph nodes connected:
1 -> 2 -> 3
↑    ↓
4 ← 5

Edges:
1-2, 2-3, 2-5, 5-4
Bridge example: edge 2-3 is a bridge because removing it disconnects node 3.

Dry Run Walkthrough

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

Goal: Find all bridges in the graph using Tarjan's algorithm

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

Node 1: disc=1, low=1
Visited: {1}

Why: We begin exploring from node 1 to cover the graph

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

Node 1: disc=1, low=1
Node 2: disc=2, low=2
Visited: {1,2}

Why: Explore neighbors to find earliest reachable nodes

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

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

Why: Continue DFS deeper to find bridges

Step 4: Node 3 has no unvisited neighbors, backtrack to node 2, update low[2] = min(low[2], low[3]) = 2

Node 2: disc=2, low=2
Node 3: disc=3, low=3

Why: Update low value to reflect earliest reachable ancestor

Step 5: Check if edge 2-3 is a bridge: low[3] > disc[2] (3 > 2) -> yes, record bridge (2,3)

Bridge found: (2,3)

Why: If low of child > disc of parent, edge is a bridge

Step 6: From node 2, move to node 5, assign disc=4, low=4

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

Why: Explore next neighbor to find more bridges

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

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

Why: Continue DFS to leaf nodes

Step 8: Node 4 has no unvisited neighbors, backtrack to node 5, update low[5] = min(low[5], low[4]) = 4

Node 5: disc=4, low=4
Node 4: disc=5, low=5

Why: Update low value after backtracking

Step 9: Check if edge 5-4 is a bridge: low[4] > disc[5] (5 > 4) -> yes, record bridge (5,4)

Bridge found: (5,4)

Why: Edge 5-4 is a bridge by the same rule

Step 10: Backtrack to node 2, update low[2] = min(low[2], low[5]) = 2

Node 2: disc=2, low=2
Node 5: disc=4, low=4

Why: Update low value to earliest reachable ancestor

Step 11: Backtrack to node 1, update low[1] = min(low[1], low[2]) = 1

Node 1: disc=1, low=1
Node 2: disc=2, low=2

Why: Complete DFS and low updates

Result:

Bridges found: (2,3), (5,4)

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    private int V;
    private List<int>[] adj;
    private int time = 0;

    public Graph(int vertices) {
        V = vertices;
        adj = new List<int>[V + 1];
        for (int i = 0; i <= V; i++) {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int u, int v) {
        adj[u].Add(v);
        adj[v].Add(u);
    }

    private void BridgeUtil(int u, bool[] visited, int[] disc, int[] low, int parent, List<(int,int)> bridges) {
        visited[u] = true;
        disc[u] = low[u] = ++time; // discovery time and low value

        foreach (int v in adj[u]) {
            if (!visited[v]) {
                BridgeUtil(v, visited, disc, low, u, bridges); // DFS deeper
                low[u] = Math.Min(low[u], low[v]); // update low[u]

                if (low[v] > disc[u]) {
                    bridges.Add((u, v)); // found a bridge
                }
            } else if (v != parent) {
                low[u] = Math.Min(low[u], disc[v]); // update low[u] for back edge
            }
        }
    }

    public List<(int,int)> FindBridges() {
        bool[] visited = new bool[V + 1];
        int[] disc = new int[V + 1];
        int[] low = new int[V + 1];
        List<(int,int)> bridges = new List<(int,int)>();

        for (int i = 1; i <= V; i++) {
            if (!visited[i]) {
                BridgeUtil(i, visited, disc, low, -1, bridges);
            }
        }
        return bridges;
    }
}

class Program {
    static void Main() {
        Graph g = new Graph(5);
        g.AddEdge(1, 2);
        g.AddEdge(2, 3);
        g.AddEdge(2, 5);
        g.AddEdge(5, 4);

        var bridges = g.FindBridges();
        foreach (var bridge in bridges) {
            Console.WriteLine($"Bridge found between nodes {bridge.Item1} and {bridge.Item2}");
        }
    }
}

disc[u] = low[u] = ++time; // discovery time and low value

Assign discovery time and initialize low value for node u

BridgeUtil(v, visited, disc, low, u, bridges); // DFS deeper

Recursively visit unvisited neighbor v

low[u] = Math.Min(low[u], low[v]); // update low[u]

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

if (low[v] > disc[u]) { bridges.Add((u, v)); }

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

else if (v != parent) { low[u] = Math.Min(low[u], disc[v]); }

Update low[u] for back edge to ancestor

for (int i = 1; i <= V; i++) { if (!visited[i]) { BridgeUtil(i, visited, disc, low, -1, bridges); } }

Start DFS from each unvisited node to cover disconnected graph

Output

Bridge found between nodes 2 and 3

Bridge found between nodes 5 and 4

Complexity Analysis

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

Space: O(V) for arrays to store discovery times, low values, and visited flags

vs Alternative: Naive approach checks connectivity after removing each edge, costing O(V*(V+E)) which is much slower

Edge Cases

Empty graph with no edges

No bridges found, algorithm handles gracefully

DSA C#

for (int i = 1; i <= V; i++) { if (!visited[i]) { BridgeUtil(i, visited, disc, low, -1, bridges); } }

Graph with a single node

No edges, so no bridges found

DSA C#

for (int i = 1; i <= V; i++) { if (!visited[i]) { BridgeUtil(i, visited, disc, low, -1, bridges); } }

Graph with cycles and no bridges

No edges satisfy low[v] > disc[u], so no bridges recorded

DSA C#

if (low[v] > disc[u]) { bridges.Add((u, v)); }

When to Use This Pattern

When asked to find edges whose removal disconnects the graph, use Tarjan's bridge-finding algorithm because it efficiently finds these critical edges in one DFS pass.

Common Mistakes

Mistake: Not updating low[u] for back edges to ancestors
Fix: Add else if condition to update low[u] with disc[v] when v is not parent

Mistake: Checking bridge condition incorrectly as low[v] >= disc[u]
Fix: Use strict greater than (low[v] > disc[u]) to identify bridges correctly

Summary

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

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

The key insight is tracking the earliest reachable ancestor node during DFS to detect bridges.

Practice

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

easy

A. To sort nodes in topological order

B. To find the shortest path between two nodes

C. To detect cycles in a graph

D. To find edges that, if removed, increase the number of connected components

Solution

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

   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 finds such edges efficiently by using depth-first search and tracking discovery and low times.

3. Final Answer:

   To find edges that, if removed, increase the number of connected components -> Option D

4. Quick Check:

   Bridges = edges increasing components when removed [OK]

Hint: Bridges disconnect graph if removed [OK]

Common Mistakes:

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

2. Which of the following is the correct way to declare the arrays used for discovery and low times in C# for Tarjan's algorithm?

easy

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

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

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

D. int[] disc, low = new int[n];

Solution

1. Step 1: Recall C# array declaration syntax

   In C#, arrays are declared as type[] name = new type[size];

2. Step 2: Check each option

   int[] disc = new int[n]; int[] low = new int[n]; uses correct syntax for both arrays. int disc[] = new int[n]; int low[] = new int[n]; uses Java-style syntax, invalid in C#. int disc = new int[n]; int low = new int[n]; misses [] for arrays. int[] disc, low = new int[n]; declares only low as array, disc is just a variable.

3. Final Answer:

   int[] disc = new int[n]; int[] low = new int[n]; -> Option B

4. Quick Check:

   C# arrays = type[] name = new type[size] [OK]

Hint: Use type[] name = new type[size] in C# [OK]

Common Mistakes:

• Using Java array syntax in C#
• Forgetting [] in declaration
• Declaring multiple arrays incorrectly

3. Given the following graph edges and Tarjan's algorithm code snippet, what is the output list of bridges?

Edges: (0-1), (1-2), (2-0), (1-3)

// Assume graph is adjacency list
// Tarjan's algorithm finds bridges

Output bridges:

medium

A. [(0, 1)]

B. [(0, 1), (1, 3)]

C. [(1, 3)]

D. []

Solution

1. Step 1: Analyze the graph structure

   The edges (0-1), (1-2), and (2-0) form a cycle. The edge (1-3) connects node 3 to the cycle.

2. Step 2: Identify bridges

   Edges in a cycle are not bridges because removing them does not disconnect the graph. The edge (1-3) is a bridge because removing it disconnects node 3.

3. Final Answer:

   [(1, 3)] -> Option C

4. Quick Check:

   Only edge (1-3) disconnects graph [OK]

Hint: Edges in cycles are not bridges [OK]

Common Mistakes:

• Marking cycle edges as bridges
• Ignoring leaf edges as bridges
• Confusing nodes and edges

4. Identify the bug in this Tarjan's algorithm snippet for finding bridges in C#:

void DFS(int u, int parent) {
  disc[u] = time;
  low[u] = time;
  time++;
  foreach (int v in graph[u]) {
    if (disc[v] == -1) {
      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]);
    }
  }
}

medium

A. The check 'if (v == parent) continue;' is missing

B. The 'disc[u]' and 'low[u]' are not initialized before DFS

C. The 'time' variable is not incremented correctly

D. The condition 'if (low[v] > disc[u])' should be 'if (low[v] >= disc[u])'

Solution

1. Step 1: Examine the DFS traversal logic

   The code lacks 'if (v == parent) continue;' after foreach. This check prevents processing the parent edge as a back edge, which would incorrectly lower low[u] and miss bridges.

2. Step 2: Rule out other options

   The condition 'if (low[v] > disc[u])' should be 'if (low[v] >= disc[u])': 'low[v] > disc[u]' is correct for bridges (strict >). The 'disc[u]' and 'low[u]' are not initialized before DFS: disc[u] and low[u] are set inside DFS. The 'time' variable is not incremented correctly: time++ follows assignment correctly.

3. Final Answer:

   The check 'if (v == parent) continue;' is missing -> Option A

4. Quick Check:

   Parent check avoids revisiting parent [OK]

Hint: Always skip parent node in DFS to avoid false bridges [OK]

Common Mistakes:

• Forgetting to skip parent node
• Using wrong comparison operator for bridges
• Not initializing discovery times

5. You have a graph with nodes 0 to 5 and edges: (0-1), (1-2), (2-0), (1-3), (3-4), (4-5), (5-3). Using Tarjan's algorithm, which edges are bridges?

hard

A. [(1, 3)]

B. [(1, 3), (3, 4)]

C. [(1, 3), (4, 5)]

D. []

Solution

1. Step 1: Analyze graph cycles and connections

   Edges (0-1), (1-2), (2-0) form a cycle. Edges (3-4), (4-5), (5-3) form another cycle. Edge (1-3) connects these two cycles.

2. Step 2: Identify bridges

   Only edge (1-3) is a bridge; removing it disconnects {0,1,2} from {3,4,5}. Cycle edges like (3-4) are not bridges (path 3-5-4 remains), similarly for others.

3. Final Answer:

   [(1, 3)] -> Option A

4. Quick Check:

   Only edge (1-3) disconnects graph [OK]

Hint: Bridges connect cycles or leaf nodes [OK]

Common Mistakes:

• Missing bridges inside connected components
• Confusing cycle edges as bridges
• Ignoring multi-cycle connections