Shortest Path in Unweighted Graph Using BFS in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS Shortest Path Distance Array

What is the output of the distance array after running BFS from node 0 on this graph?

DSA Rust

use std::collections::VecDeque;

fn bfs_shortest_path(graph: &Vec<Vec<usize>>, start: usize) -> Vec<Option<usize>> {
    let mut dist = vec![None; graph.len()];
    let mut queue = VecDeque::new();
    dist[start] = Some(0);
    queue.push_back(start);

    while let Some(u) = queue.pop_front() {
        for &v in &graph[u] {
            if dist[v].is_none() {
                dist[v] = Some(dist[u].unwrap() + 1);
                queue.push_back(v);
            }
        }
    }
    dist
}

fn main() {
    let graph = vec![
        vec![1, 2],    // 0
        vec![0, 3],    // 1
        vec![0, 3, 4], // 2
        vec![1, 2, 5], // 3
        vec![2],       // 4
        vec![3],       // 5
    ];
    let dist = bfs_shortest_path(&graph, 0);
    println!("{:?}", dist);
}

A [Some(0), None, Some(1), Some(2), Some(2), Some(3)]

B [Some(0), Some(1), Some(1), Some(2), Some(2), Some(3)]

C [Some(0), Some(1), Some(2), Some(2), Some(3), Some(4)]

D [Some(0), Some(1), Some(1), Some(1), Some(2), Some(3)]

💡 Hint

Trace BFS levels starting from node 0. Nodes directly connected to 0 have distance 1.

Starting from node 0 with distance 0, nodes 1 and 2 are at distance 1. Node 3 is connected to 1 and 2, so distance 2. Node 4 is connected to 2, distance 2. Node 5 is connected to 3, distance 3.

🧠 Conceptual

intermediate

Why BFS Finds Shortest Path in Unweighted Graph

Why does BFS guarantee the shortest path in an unweighted graph?

A Because BFS marks nodes as visited only after exploring all neighbors.

B Because BFS uses a stack to explore nodes deeply before breadth.

C Because BFS uses random traversal to find the shortest path.

D Because BFS explores nodes in order of increasing distance from the start node.

💡 Hint

Think about the order in which BFS visits nodes.

BFS visits nodes level by level, so the first time it reaches a node, it is via the shortest path from the start node.

🔧 Debug

advanced

Identify the Bug in BFS Implementation

What is the bug in this BFS shortest path code snippet?

DSA Rust

fn bfs_bug(graph: &Vec<Vec<usize>>, start: usize) -> Vec<Option<usize>> {
    let mut dist = vec![None; graph.len()];
    let mut queue = std::collections::VecDeque::new();
    dist[start] = Some(0);
    queue.push_back(start);

    while let Some(u) = queue.pop_front() {
        for &v in &graph[u] {
            dist[v] = Some(dist[u].unwrap() + 1);
            queue.push_back(v);
        }
    }
    dist
}

A It updates distance for all neighbors without checking if visited, causing infinite loop or wrong distances.

B It uses a stack instead of a queue, so BFS is not performed.

C It initializes distance vector with zeros instead of None.

D It never pushes the start node into the queue.

💡 Hint

Check if the code prevents revisiting nodes.

The code assigns distance to neighbors without checking if they were visited before, so nodes can be revisited multiple times, causing incorrect distances or infinite loops.

🚀 Application

advanced

Shortest Path Reconstruction Using BFS

Which code snippet correctly reconstructs the shortest path from start to target after BFS?

DSA Rust

Assume BFS fills a parent array where parent[v] = u means u is predecessor of v in shortest path.

A

let mut path = vec![];
let mut current = target;
while current != start {
    current = parent[current].unwrap();
    path.push(current);
}
path.reverse();

B

let mut path = vec![];
let mut current = start;
while current != target {
    path.push(current);
    current = parent[current].unwrap();
}
path.push(target);

C

let mut path = vec![];
let mut current = target;
while current != start {
    path.push(current);
    current = parent[current].unwrap();
}
path.push(start);
path.reverse();

D

let mut path = vec![];
let mut current = target;
while current != start {
    path.push(current);
    current = parent[current];
}
path.push(start);
path.reverse();

💡 Hint

Trace path from target back to start using parent, then reverse.

Option C correctly pushes nodes from target to start, then reverses to get path from start to target. It unwraps Option safely. Option C goes forward incorrectly. Option C misses pushing start. Option C misses unwrap causing compile error.

❓ Predict Output

expert

Output of BFS Distances with Disconnected Nodes

What is the output of the distance vector after running BFS from node 0 on this graph with disconnected nodes?

DSA Rust

use std::collections::VecDeque;

fn bfs(graph: &Vec<Vec<usize>>, start: usize) -> Vec<Option<usize>> {
    let mut dist = vec![None; graph.len()];
    let mut queue = VecDeque::new();
    dist[start] = Some(0);
    queue.push_back(start);

    while let Some(u) = queue.pop_front() {
        for &v in &graph[u] {
            if dist[v].is_none() {
                dist[v] = Some(dist[u].unwrap() + 1);
                queue.push_back(v);
            }
        }
    }
    dist
}

fn main() {
    let graph = vec![
        vec![1],      // 0
        vec![0, 2],   // 1
        vec![1],      // 2
        vec![4],      // 3 disconnected component
        vec![3],      // 4
    ];
    let dist = bfs(&graph, 0);
    println!("{:?}", dist);
}

A [Some(0), Some(1), Some(2), None, None]

B [Some(0), Some(1), Some(2), Some(3), Some(4)]

C [None, Some(1), Some(2), None, None]

D [Some(0), Some(1), None, Some(1), Some(2)]

💡 Hint

Nodes 3 and 4 are disconnected from start node 0.

BFS only visits nodes reachable from start. Nodes 3 and 4 are disconnected, so their distances remain None.

Practice

1. What does BFS (Breadth-First Search) find in an unweighted graph when used from a start node?

easy

A. A random path to any node

B. The longest path in the graph

C. The path with the maximum sum of edge weights

D. The shortest path in terms of number of edges to all reachable nodes

Solution

1. Step 1: Understand BFS traversal

   BFS explores nodes level by level, starting from the source node, visiting all neighbors before moving deeper.

2. Step 2: BFS finds shortest paths in unweighted graphs

   Because BFS visits nodes in order of increasing distance (edges), it finds the shortest path in terms of edge count.

3. Final Answer:

   The shortest path in terms of number of edges to all reachable nodes -> Option D

4. Quick Check:

   BFS = shortest path in unweighted graph [OK]

Hint: BFS finds shortest paths by layers in unweighted graphs [OK]

Common Mistakes:

• Confusing BFS with DFS for shortest path
• Thinking BFS finds longest paths
• Assuming BFS works for weighted graphs without modification

2. Which Rust code snippet correctly initializes a queue for BFS traversal?

easy

A. let queue = Vec::new();

B. let mut queue = std::collections::VecDeque::new();

C. let mut queue = std::collections::HashMap::new();

D. let mut queue = std::collections::BinaryHeap::new();

Solution

1. Step 1: Identify the correct queue type for BFS

   BFS requires a FIFO queue; VecDeque in Rust supports efficient push/pop from both ends.

2. Step 2: Check each option's suitability

   let mut queue = std::collections::VecDeque::new(); uses VecDeque which is correct; Vec (A) is not efficient as a queue; HashMap (C) is a map, not a queue; BinaryHeap (D) is a priority queue, not FIFO.

3. Final Answer:

   let mut queue = std::collections::VecDeque::new(); -> Option B

4. Quick Check:

   VecDeque = correct BFS queue [OK]

Hint: Use VecDeque for BFS queue in Rust [OK]

Common Mistakes:

• Using Vec instead of VecDeque for queue
• Using HashMap or BinaryHeap incorrectly
• Not mutably declaring the queue

3. Given the following Rust code snippet for BFS on an unweighted graph, what is the output distance vector?

let graph = vec![
    vec![1, 2],
    vec![0, 3],
    vec![0, 3],
    vec![1, 2, 4],
    vec![3]
];
let start = 0;
let mut dist = vec![-1; 5];
dist[start] = 0;
let mut queue = std::collections::VecDeque::new();
queue.push_back(start);

while let Some(u) = queue.pop_front() {
    for &v in &graph[u] {
        if dist[v] == -1 {
            dist[v] = dist[u] + 1;
            queue.push_back(v);
        }
    }
}
println!("{:?}", dist);

medium

A. 0, 1, 1, 2, 3

B. 0, 1, 2, 1, 2

C. 0, 1, 1, 1, 2

D. 0, 2, 2, 3, 4

Solution

1. Step 1: Trace BFS distances from start node 0

   Start at node 0 (distance 0). Neighbors 1 and 2 get distance 1. Then from 1 and 2, node 3 gets distance 2. From 3, node 4 gets distance 3.

2. Step 2: Confirm final distance vector

   Distances: node0=0, node1=1, node2=1, node3=2, node4=3.

3. Final Answer:

   0, 1, 1, 2, 3 -> Option A

4. Quick Check:

   BFS distances = [0,1,1,2,3] [OK]

Hint: Track BFS levels to assign distances [OK]

Common Mistakes:

• Mixing up node indices and distances
• Assigning wrong distances to nodes visited later
• Forgetting to initialize distances with -1

4. Identify the bug in this BFS Rust code snippet that causes it to panic or produce incorrect distances:

let graph = vec![vec![1], vec![0, 2], vec![1]];
let start = 0;
let mut dist = vec![0; 3];
let mut queue = std::collections::VecDeque::new();
queue.push_back(start);

while let Some(u) = queue.pop_front() {
    for &v in &graph[u] {
        if dist[v] == 0 {
            dist[v] = dist[u] + 1;
            queue.push_back(v);
        }
    }
}
println!("{:?}", dist);

medium

A. Loop condition is incorrect

B. Queue is not mutable

C. Distance vector initialized with zeros causes confusion with unvisited nodes

D. Graph adjacency list is empty

Solution

1. Step 1: Check distance vector initialization

   Distances initialized to 0 means unvisited nodes and start node share same value, causing logic errors.

2. Step 2: Explain impact on BFS logic

   Condition 'if dist[v] == 0' fails to distinguish unvisited nodes, so some nodes never get updated or cause infinite loops.

3. Final Answer:

   Distance vector initialized with zeros causes confusion with unvisited nodes -> Option C

4. Quick Check:

   Use -1 for unvisited distances [OK]

Hint: Initialize distances with -1 to mark unvisited [OK]

Common Mistakes:

• Using 0 as initial distance for all nodes
• Not marking start node distance before BFS
• Ignoring mutability of queue

5. You want to find the shortest path length from node 0 to node 5 in this unweighted graph using BFS. The graph edges are:

0 - 1, 0 - 2, 1 - 3, 2 - 3, 3 - 4, 4 - 5

Which BFS distance array after traversal correctly shows the shortest distance to each node from 0? Assume nodes are 0 to 5 and unreachable nodes have distance -1.

hard

A. [0, 1, 1, 2, 3, 4]

B. [0, 1, 2, 3, 4, 5]

C. [0, 1, 1, 1, 2, 3]

D. [0, -1, -1, -1, -1, -1]

Solution

1. Step 1: Map shortest paths from node 0

   From 0: nodes 1 and 2 are 1 edge away; node 3 is 2 edges away (via 1 or 2); node 4 is 3 edges away; node 5 is 4 edges away.

2. Step 2: Confirm distances array

   Distances: 0=0, 1=1, 2=1, 3=2, 4=3, 5=4 matches [0, 1, 1, 2, 3, 4].

3. Final Answer:

   [0, 1, 1, 2, 3, 4] -> Option A

4. Quick Check:

   Shortest path distances = [0,1,1,2,3,4] [OK]

Hint: Count edges from start node to each node [OK]

Common Mistakes:

• Counting nodes instead of edges
• Mislabeling unreachable nodes
• Confusing path length with node values