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

Bridges in Graph using Tarjan's Algorithm

📖 Scenario: You are working as a network engineer. You want to find critical connections (bridges) in a network. A bridge is a connection that, if removed, will increase the number of disconnected parts in the network.This helps you find weak points in the network that need extra protection.

🎯 Goal: Build a Rust program that finds all bridges in an undirected graph using Tarjan's algorithm.You will create the graph, set up helper variables, implement the core DFS logic, and finally print the list of bridges.

📋 What You'll Learn

Create a graph as an adjacency list with exact edges

Create helper vectors for discovery times and low values

Implement Tarjan's DFS to find bridges

Print the list of bridges as pairs of nodes

💡 Why This Matters

🌍 Real World

Network engineers use bridge detection to find weak points in communication networks that can cause failures if disconnected.

💼 Career

Understanding Tarjan's algorithm and graph traversal is important for roles in network design, cybersecurity, and software engineering involving graph data.

1

Create the graph as adjacency list

Create a variable called graph as a Vec<Vec<usize>> with 5 nodes (0 to 4) and these exact edges:
0 - 1, 1 - 2, 2 - 0, 1 - 3, 3 - 4.
Use zero-based indexing and undirected edges.

DSA Rust

# Your code here

Hint

Use a Vec<Vec<usize>> to represent the graph. Each inner vector holds neighbors of that node.

2

Create helper vectors for Tarjan's algorithm

Create two vectors called disc and low of type Vec<Option<usize>> with length 5, initialized with None. Also create a mutable vector called bridges of type Vec<(usize, usize)> to store the bridges.

DSA Rust

let graph: Vec> = vec![
    vec![1, 2],    // edges from node 0
    vec![0, 2, 3], // edges from node 1
    vec![0, 1],    // edges from node 2
    vec![1, 4],    // edges from node 3
    vec![3],       // edges from node 4
];
# Your code here

Hint

Use Option<usize> to mark discovery and low times as None initially.

3

Implement Tarjan's DFS to find bridges

Write a recursive function called dfs with parameters u: usize, parent: Option<usize>, time: &mut usize, graph: &Vec<Vec<usize>>, disc: &mut Vec<Option<usize>>, low: &mut Vec<Option<usize>>, and bridges: &mut Vec<(usize, usize)>. Inside, set discovery and low time for u, then for each neighbor v of u, if v is not visited, recursively call dfs on v. Update low values and if low[v] > disc[u], add (u, v) to bridges. If v is visited and not parent, update low[u]. Then call dfs starting from node 0 with parent = None and time = 0.

DSA Rust

let graph: Vec> = vec![
    vec![1, 2],    // edges from node 0
    vec![0, 2, 3], // edges from node 1
    vec![0, 1],    // edges from node 2
    vec![1, 4],    // edges from node 3
    vec![3],       // edges from node 4
];

let mut disc: Vec> = vec![None; 5];
let mut low: Vec> = vec![None; 5];
let mut bridges: Vec = Vec::new();

// Write dfs function and call it starting from node 0
# Your code here

Hint

Use Option<usize> unwrap carefully. Update low[u] after recursive calls and check condition for bridges.

4

Print the list of bridges

Write a println! statement to print the bridges vector.

DSA Rust

let graph: Vec> = vec![
    vec![1, 2],    // edges from node 0
    vec![0, 2, 3], // edges from node 1
    vec![0, 1],    // edges from node 2
    vec![1, 4],    // edges from node 3
    vec![3],       // edges from node 4
];

let mut disc: Vec> = vec![None; 5];
let mut low: Vec> = vec![None; 5];
let mut bridges: Vec = Vec::new();

fn dfs(
    u: usize,
    parent: Option,
    time: &mut usize,
    graph: &Vec>,
    disc: &mut Vec>,
    low: &mut Vec>,
    bridges: &mut Vec,
) {
    *time += 1;
    disc[u] = Some(*time);
    low[u] = Some(*time);

    for &v in &graph[u] {
        if disc[v].is_none() {
            dfs(v, Some(u), time, graph, disc, low, bridges);
            low[u] = Some(low[u].unwrap().min(low[v].unwrap()));
            if low[v].unwrap() > disc[u].unwrap() {
                bridges.push((u, v));
            }
        } else if Some(v) != parent {
            low[u] = Some(low[u].unwrap().min(disc[v].unwrap()));
        }
    }
}

let mut time = 0;
dfs(0, None, &mut time, &graph, &mut disc, &mut low, &mut bridges);

// Print the bridges vector
# Your code here

Hint

Use println!("{:?}", bridges); to print the vector of 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