Shortest Path in Unweighted Graph Using BFS in DSA Rust - Execution Trace

Concept Flow - Shortest Path in Unweighted Graph Using BFS

Start at source node

↓

Initialize queue with source

↓

While queue not empty

↓

Dequeue current node

↓

For each neighbor

↓

If neighbor not visited

↓

Mark visited, set distance, enqueue

↓

Repeat until all reachable nodes processed

↓

Distances represent shortest paths

Start from the source node, explore neighbors level by level using a queue, marking distances as shortest paths.

Execution Sample

DSA Rust

fn bfs_shortest_path(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] {
            if dist[v].is_none() {
                dist[v] = Some(dist[u].unwrap() + 1);
                queue.push_back(v);
            }
        }
    }
    dist
}

This BFS finds shortest distances from start node to all others in an unweighted graph.

Execution Table

Step	Operation	Current Node	Queue State	Distance Array	Visual State
1	Initialize	-	[0]	[0, None, None, None, None]	Graph nodes: 0-4, start=0
2	Dequeue	0	[]	[0, None, None, None, None]	Visit neighbors of 0: 1, 2
3	Enqueue neighbors	-	[1, 2]	[0, 1, 1, None, None]	Distances updated for 1 and 2
4	Dequeue	1	[2]	[0, 1, 1, None, None]	Visit neighbors of 1: 0, 3
5	Enqueue neighbor 3	-	[2, 3]	[0, 1, 1, 2, None]	Distance updated for 3
6	Dequeue	2	[3]	[0, 1, 1, 2, None]	Visit neighbors of 2: 0, 3, 4
7	Enqueue neighbor 4	-	[3, 4]	[0, 1, 1, 2, 2]	Distance updated for 4
8	Dequeue	3	[4]	[0, 1, 1, 2, 2]	Visit neighbors of 3: 1, 2
9	No new enqueue	-	[4]	[0, 1, 1, 2, 2]	Neighbors already visited
10	Dequeue	4	[]	[0, 1, 1, 2, 2]	Visit neighbors of 4: 2
11	No new enqueue	-	[]	[0, 1, 1, 2, 2]	Neighbors already visited
12	End	-	[]	[0, 1, 1, 2, 2]	Queue empty, BFS complete

💡 Queue is empty, all reachable nodes processed

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 12
queue	[0]	[1, 2]	[2, 3]	[3, 4]	[]
dist	[0, None, None, None, None]	[0, 1, 1, None, None]	[0, 1, 1, 2, None]	[0, 1, 1, 2, 2]	[0, 1, 1, 2, 2]
current_node	-	0	1	2	4

Key Moments - 3 Insights

Why do we mark a node as visited only when we enqueue it, not when we dequeue it?

Marking visited when enqueuing (see Step 3, 5, 7) prevents adding the same node multiple times to the queue, ensuring BFS explores each node once.

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

Because BFS explores nodes level by level (distance increments by 1 each time), the first time we visit a node is via the shortest path (see distance updates in Steps 3, 5, 7).

What happens if the graph has disconnected nodes?

Nodes unreachable from the start remain with distance None (not visited), as BFS only explores connected components (not shown in this example but implied by None values).

Visual Quiz - 3 Questions

Look at the execution table at Step 7, what is the distance assigned to node 4?

A 2

B 1

C 3

D None

💡 Hint

Check the Distance Array column in Step 7 of the execution_table

At which step does the queue become empty, ending the BFS?

A Step 10

B Step 9

C Step 12

D Step 8

💡 Hint

Look at the Queue State column and exit_note in execution_table

If node 3 had an additional neighbor 5 not connected to others, what would happen to the distance of node 5?

A It would remain None if not connected to start

B It would be set to 3 when visited

C It would be set to 1 immediately

D It would cause an infinite loop

💡 Hint

Neighbors are enqueued with distance = current node distance + 1 (see Steps 5 and 7)

Concept Snapshot

Shortest Path in Unweighted Graph Using BFS:
- Use a queue to explore nodes level by level
- Mark distances when first visiting nodes
- Distance increments by 1 per edge
- Visited nodes are enqueued once
- BFS guarantees shortest path in unweighted graphs

Full Transcript

This visualization shows how BFS finds shortest paths in an unweighted graph. Starting from the source node, BFS uses a queue to explore neighbors level by level. Each node's distance is set when it is first enqueued, ensuring the shortest path is recorded. The queue processes nodes in order, and once empty, BFS completes with distances representing shortest paths. Nodes unreachable from the start remain with no distance assigned. Key points include marking nodes visited when enqueued to avoid repeats and BFS's level-wise exploration guaranteeing shortest paths.

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