Bridges in Graph Tarjan's Algorithm in DSA Rust

Mental Model

A bridge is an edge that, if removed, splits the graph into more parts. Tarjan's algorithm finds these by tracking when nodes can reach earlier nodes through other paths.

Analogy: Imagine a city connected by roads. A bridge road is one that, if closed, cuts off some neighborhoods from others. Tarjan's algorithm finds these critical roads by exploring all paths and seeing which roads are the only way to get back to earlier places.

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

Bridges:
Edges that if removed, split the graph.
Example: Edge 2-4 might be a bridge if no other path connects 2 and 4.

Dry Run Walkthrough

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

Goal: Find all bridges (edges that disconnect the graph if removed)

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

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

Why: We begin exploring from node 1 to find bridges

Step 2: Visit 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 back edges and update low values

Step 3: Visit 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 to explore all nodes

Step 4: From node 3, find back edge to node 1, update low[3] = min(low[3], disc[1]) = 1

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

Why: Back edge shows node 3 can reach node 1 earlier, so low value updates

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

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

Why: Low value of node 2 updates based on child node 3

Step 6: Visit node 4 from node 2, assign disc=4, low=4

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

Why: Explore new node 4 from node 2

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

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

Why: Update low value of node 2 after exploring node 4

Step 8: Check edge 2-4: since low[4] > disc[2], edge 2-4 is a bridge

Bridge found: 2 - 4

Why: If child's low is greater than parent's discovery time, edge is a bridge

Result:

Bridges: 2 - 4

Annotated Code

DSA Rust

use std::collections::HashMap;

struct Graph {
    adj: HashMap<usize, Vec<usize>>,
    time: usize,
    disc: Vec<usize>,
    low: Vec<usize>,
    visited: Vec<bool>,
    bridges: Vec<(usize, usize)>,
}

impl Graph {
    fn new(n: usize) -> Self {
        Graph {
            adj: HashMap::new(),
            time: 0,
            disc: vec![0; n + 1],
            low: vec![0; n + 1],
            visited: vec![false; n + 1],
            bridges: Vec::new(),
        }
    }

    fn add_edge(&mut self, u: usize, v: usize) {
        self.adj.entry(u).or_default().push(v);
        self.adj.entry(v).or_default().push(u);
    }

    fn dfs(&mut self, u: usize, parent: Option<usize>) {
        self.time += 1;
        self.disc[u] = self.time;
        self.low[u] = self.time;
        self.visited[u] = true;

        for &v in self.adj.get(&u).unwrap_or(&Vec::new()) {
            if Some(v) == parent {
                continue; // skip the edge to parent
            }
            if !self.visited[v] {
                self.dfs(v, Some(u)); // explore child
                self.low[u] = self.low[u].min(self.low[v]); // update low[u]

                if self.low[v] > self.disc[u] {
                    self.bridges.push((u, v)); // found bridge
                }
            } else {
                self.low[u] = self.low[u].min(self.disc[v]); // back edge
            }
        }
    }

    fn find_bridges(&mut self, n: usize) -> Vec<(usize, usize)> {
        for i in 1..=n {
            if !self.visited[i] {
                self.dfs(i, None);
            }
        }
        self.bridges.clone()
    }
}

fn main() {
    let n = 4;
    let edges = vec![(1, 2), (1, 3), (2, 3), (2, 4)];

    let mut graph = Graph::new(n);
    for (u, v) in edges {
        graph.add_edge(u, v);
    }

    let bridges = graph.find_bridges(n);
    for (u, v) in bridges {
        println!("{} - {}", u, v);
    }
}

self.time += 1; self.disc[u] = self.time; self.low[u] = self.time; self.visited[u] = true;

Assign discovery time and low value to node u and mark visited

if Some(v) == parent { continue; }

Skip edge leading back to parent to avoid trivial cycle

if !self.visited[v] { self.dfs(v, Some(u)); self.low[u] = self.low[u].min(self.low[v]);

Explore unvisited child v and update low[u] after recursion

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

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

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

Update low[u] for back edge to ancestor v

Output

2 - 4

Complexity Analysis

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

Space: O(V + E) for adjacency list and auxiliary arrays to store discovery, low, and visited

vs Alternative: Naive approach checks connectivity after removing each edge, costing O(E*(V+E)), much slower than Tarjan's O(V+E)

Edge Cases

Graph with no edges

No bridges found because no edges exist

DSA Rust

for i in 1..=n { if !self.visited[i] { self.dfs(i, None); } }

Graph with a single node

No bridges found as no edges exist

DSA Rust

for i in 1..=n { if !self.visited[i] { self.dfs(i, None); } }

Graph with multiple disconnected components

Algorithm runs DFS on each component separately to find bridges in all parts

DSA Rust

for i in 1..=n { if !self.visited[i] { self.dfs(i, None); } }

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 all such edges in one DFS pass.

Common Mistakes

Mistake: Not updating low[u] with disc[v] on back edges, missing critical back connections
Fix: Update low[u] = min(low[u], disc[v]) when encountering a back edge to ancestor v

Mistake: Considering the edge to parent as a back edge, causing incorrect low values
Fix: Skip the edge leading back to parent node during DFS

Summary

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

Use when you need to identify critical connections that keep the graph connected.

The key insight is tracking the earliest reachable ancestor from each node to detect bridges.

Practice

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

easy

A. To detect cycles in a graph

B. To find the shortest path between two nodes

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

D. To sort nodes in topological order

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 DFS and tracking discovery and low times.

3. Final Answer:

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

4. Quick Check:

   Bridges = edges increasing components [OK]

Hint: Bridges break connectivity when removed [OK]

Common Mistakes:

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

2. Which of the following Rust code snippets correctly declares a vector to store adjacency lists for a graph with 5 nodes?

easy

A. let graph: Vec = vec![vec![0]; 5];

B. let graph: Vec<usize> = vec![0; 5];

C. let graph: Vec = vec![vec![]; 4];

D. let graph: Vec = vec![vec![]; 5];

Solution

1. Step 1: Understand adjacency list representation

   Each node has a vector of neighbors, so graph is a vector of vectors.

2. Step 2: Check vector initialization for 5 nodes

   vec![vec![]; 5] creates 5 empty vectors, one per node.

3. Final Answer:

   let graph: Vec = vec![vec![]; 5]; -> Option D

4. Quick Check:

   Adjacency list for 5 nodes = vec![vec![]; 5] [OK]

Hint: Use vec![vec![]; n] for adjacency lists [OK]

Common Mistakes:

• Using wrong vector type (Vec<usize> instead of Vec)
• Initializing with wrong size
• Filling inner vectors with zeros instead of empty

3. Given the following Rust code snippet implementing part of Tarjan's algorithm, what will be printed as bridges for the graph edges?

let edges = vec![(0,1), (1,2), (2,0), (1,3)];
// Graph: triangle 0-1-2 and a bridge edge 1-3
// After running Tarjan's algorithm, which edges are bridges?
println!("Bridges: {:?}", vec![(1,3)]);

medium

A. Bridges: [(1, 3)]

B. Bridges: [(0, 1), (1, 2), (2, 0)]

C. Bridges: []

D. Bridges: [(0, 3)]

Solution

1. Step 1: Analyze the graph structure

   The edges (0,1), (1,2), (2,0) form a cycle (triangle), so none are bridges.

2. Step 2: Identify the bridge edge

   The edge (1,3) connects node 3 to the triangle and is a bridge because removing it disconnects node 3.

3. Final Answer:

   Bridges: [(1, 3)] -> Option A

4. Quick Check:

   Only edge (1,3) breaks connectivity [OK]

Hint: Edges in cycles are not bridges [OK]

Common Mistakes:

• Marking cycle edges as bridges
• Ignoring leaf node connections
• Confusing bridge edges with articulation points

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

fn dfs(u: usize, parent: usize, graph: &Vec, disc: &mut Vec<usize>, low: &mut Vec<usize>, time: &mut usize, bridges: &mut Vec<(usize, usize)>) {
    disc[u] = *time;
    low[u] = *time;
    *time += 1;
    for &v in &graph[u] {
        if v == parent {
            continue;
        }
        if disc[v] == 0 {
            dfs(v, u, graph, disc, low, time, bridges);
            low[u] = low[u].min(low[v]);
            if low[v] > disc[u] {
                bridges.push((u, v));
            }
        } else {
            low[u] = low[u].min(disc[v]);
        }
    }
}

medium

A. disc and low arrays are not initialized with zeros

B. The parent check should be if v != parent instead of v == parent

C. The time variable should be passed by value, not mutable reference

D. The condition low[v] > disc[u] should be low[v] < disc[u]

Solution

1. Step 1: Check initialization of disc and low arrays

   disc and low must be initialized with zeros to detect unvisited nodes (disc[v] == 0).

2. Step 2: Verify other logic correctness

   Parent check and time passing are correct; condition low[v] > disc[u] is correct for bridges.

3. Final Answer:

   disc and low arrays are not initialized with zeros -> Option A

4. Quick Check:

   Uninitialized disc causes wrong visited checks [OK]

Hint: Initialize disc and low with zeros before DFS [OK]

Common Mistakes:

• Not initializing disc and low arrays
• Wrong parent check condition
• Passing time by value instead of mutable reference

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

hard

A. [(3, 4), (4, 5), (5, 3)]

B. [(1, 3)]

C. [(0, 1), (1, 2), (2, 0)]

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

Solution

1. Step 1: Analyze graph components

   Nodes 0,1,2 form a cycle (triangle), so edges among them are not bridges. Nodes 3,4,5 form a cycle, so edges among them are not bridges.

2. Step 2: Identify bridge edges

   The edge (1,3) connects the two cycles. Removing (1,3) disconnects the graph, so it is a bridge.

3. Final Answer:

   [(1, 3)] -> Option B

4. Quick Check:

   Only edge connecting components is bridge [OK]

Hint: Bridges connect separate cycles or components [OK]

Common Mistakes:

• Marking cycle edges as bridges
• Ignoring connectivity between components
• Confusing bridges with articulation points