Shortest Path in Unweighted Graph Using BFS in DSA Rust - Build from Scratch

Shortest Path in Unweighted Graph Using BFS

📖 Scenario: You are working on a navigation system for a small city. The city map is represented as a graph where intersections are nodes and roads are edges. You want to find the shortest path from one intersection to another using a simple method.

🎯 Goal: Build a Rust program that finds the shortest path between two intersections in an unweighted graph using Breadth-First Search (BFS).

📋 What You'll Learn

Create a graph using an adjacency list with exact nodes and edges

Add a start node variable to specify where the path begins

Implement BFS to find the shortest path distances from the start node

Print the shortest distance from the start node to each node

💡 Why This Matters

🌍 Real World

Finding shortest paths in maps, social networks, or any system where connections have equal cost.

💼 Career

Understanding BFS and shortest path algorithms is essential for software engineers working on navigation, networking, and graph-based problems.

1

Create the graph as an adjacency list

Create a variable called graph as a Vec<Vec<usize>> with 5 nodes. Add edges exactly as follows: node 0 connects to nodes 1 and 2, node 1 connects to nodes 0 and 3, node 2 connects to nodes 0 and 3 and 4, node 3 connects to nodes 1 and 2 and 4, node 4 connects to nodes 2 and 3.

DSA Rust

# Your code here

Hint

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

2

Add the start node variable

Add a variable called start and set it to 0 to represent the starting intersection.

DSA Rust

fn main() {
    let graph: Vec> = vec![
        vec![1, 2],    // Node 0
        vec![0, 3],    // Node 1
        vec![0, 3, 4], // Node 2
        vec![1, 2, 4], // Node 3
        vec![2, 3],    // Node 4
    ];
    // Add start node variable here
    # Your code here
}

Hint

Just create a variable start and assign it the value 0.

3

Implement BFS to find shortest distances

Create a mutable vector called distances with length equal to graph.len(), filled with None. Set distances[start] to Some(0). Create a queue using VecDeque and push start. Use a while loop to pop from the front of the queue into current. For each neighbor in graph[current], if distances[neighbor] is None, set it to Some(distances[current].unwrap() + 1) and push neighbor to the queue.

DSA Rust

use std::collections::VecDeque;

fn main() {
    let graph: Vec> = vec![
        vec![1, 2],    // Node 0
        vec![0, 3],    // Node 1
        vec![0, 3, 4], // Node 2
        vec![1, 2, 4], // Node 3
        vec![2, 3],    // Node 4
    ];
    let start = 0;

    // Implement BFS to find shortest distances
    # Your code here
}

Hint

Use Option<usize> to track distances. Use VecDeque as a queue for BFS.

4

Print the shortest distances

Use a for loop with variables node and distance to iterate over distances.iter().enumerate(). Inside the loop, print exactly: "Node {node} is at distance {distance}" where distance is distance.unwrap().

DSA Rust

use std::collections::VecDeque;

fn main() {
    let graph: Vec> = vec![
        vec![1, 2],    // Node 0
        vec![0, 3],    // Node 1
        vec![0, 3, 4], // Node 2
        vec![1, 2, 4], // Node 3
        vec![2, 3],    // Node 4
    ];
    let start = 0;

    let mut distances: Vec> = vec![None; graph.len()];
    distances[start] = Some(0);

    let mut queue = VecDeque::new();
    queue.push_back(start);

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

    // Print shortest distances
    # Your code here
}

Hint

Use println!("Node {} is at distance {}", node, distance.unwrap()) inside a for loop.

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