BFS Breadth First Search on Graph in DSA Rust

Mental Model

BFS explores all neighbors of a node before moving to the next level, like spreading out evenly in waves.

Analogy: Imagine you are in a building and want to visit every room floor by floor, starting from the entrance. You first visit all rooms on the first floor, then all rooms on the second floor, and so on.

Graph:
  1 -> 2 -> 3
  ↓    ↓
  4    5

Queue: []
Visited: {}

Dry Run Walkthrough

Input: Graph edges: 1->2, 1->4, 2->3, 2->5; Start BFS from node 1

Goal: Visit all nodes reachable from node 1 in order of their distance from 1

Step 1: Start BFS at node 1, enqueue it and mark visited

Queue: [1]
Visited: {1}

Why: We begin from the start node to explore its neighbors

Step 2: Dequeue node 1, enqueue its neighbors 2 and 4, mark them visited

Queue: [2, 4]
Visited: {1, 2, 4}

Why: Visit all neighbors of node 1 before moving deeper

Step 3: Dequeue node 2, enqueue its neighbors 3 and 5, mark them visited

Queue: [4, 3, 5]
Visited: {1, 2, 3, 4, 5}

Why: Explore neighbors of node 2 next, continuing level order

Step 4: Dequeue node 4, it has no unvisited neighbors

Queue: [3, 5]
Visited: {1, 2, 3, 4, 5}

Why: No new nodes to add, continue with next in queue

Step 5: Dequeue node 3, it has no unvisited neighbors

Queue: [5]
Visited: {1, 2, 3, 4, 5}

Why: No new nodes to add, continue with next in queue

Step 6: Dequeue node 5, it has no unvisited neighbors

Queue: []
Visited: {1, 2, 3, 4, 5}

Why: Queue empty, BFS complete

Result:

Visited order: 1 -> 2 -> 4 -> 3 -> 5

Annotated Code

DSA Rust

use std::collections::{VecDeque, HashSet, HashMap};

fn bfs(graph: &HashMap<i32, Vec<i32>>, start: i32) -> Vec<i32> {
    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();
    let mut order = Vec::new();

    visited.insert(start); // mark start visited
    queue.push_back(start); // enqueue start

    while let Some(node) = queue.pop_front() {
        order.push(node); // visit node
        if let Some(neighbors) = graph.get(&node) {
            for &neighbor in neighbors {
                if !visited.contains(&neighbor) {
                    visited.insert(neighbor); // mark neighbor visited
                    queue.push_back(neighbor); // enqueue neighbor
                }
            }
        }
    }
    order
}

fn main() {
    let mut graph = HashMap::new();
    graph.insert(1, vec![2, 4]);
    graph.insert(2, vec![3, 5]);
    graph.insert(3, vec![]);
    graph.insert(4, vec![]);
    graph.insert(5, vec![]);

    let bfs_order = bfs(&graph, 1);
    for node in bfs_order {
        print!("{} -> ", node);
    }
    print!("null\n");
}

visited.insert(start); // mark start visited queue.push_back(start); // enqueue start

Initialize BFS by marking start node visited and enqueueing it

while let Some(node) = queue.pop_front() {

Process nodes in queue until empty

order.push(node); // visit node

Record the current node as visited in BFS order

if let Some(neighbors) = graph.get(&node) {

Get neighbors of current node

for &neighbor in neighbors { if !visited.contains(&neighbor) { visited.insert(neighbor); queue.push_back(neighbor); } }

Enqueue unvisited neighbors and mark them visited

Output

1 -> 2 -> 4 -> 3 -> 5 -> null

Complexity Analysis

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

Space: O(V) for storing visited nodes and the queue in worst case

vs Alternative: Compared to DFS which uses a stack and explores depth first, BFS uses a queue and explores level by level, useful for shortest path in unweighted graphs

Edge Cases

Empty graph

Visits only the start node since no other nodes or edges exist

DSA Rust

visited.insert(start); // mark start visited

Start node not in graph

Visits only the start node since no neighbors exist

DSA Rust

if let Some(neighbors) = graph.get(&node) {

Graph with isolated nodes

Only nodes reachable from start are visited

DSA Rust

if !visited.contains(&neighbor) { visited.insert(neighbor); queue.push_back(neighbor); }

When to Use This Pattern

When you need to explore nodes in order of their distance from a start node, use BFS because it visits nodes level by level.

Common Mistakes

Mistake: Not marking nodes as visited before enqueueing, causing repeated visits
Fix: Mark nodes visited immediately when enqueueing to avoid duplicates

Summary

BFS visits all nodes reachable from a start node in order of their distance using a queue.

Use BFS when you want to find shortest paths or explore nodes level by level.

The key insight is to explore neighbors of all nodes at the current level before moving deeper.

Practice

1. What does BFS (Breadth First Search) primarily use to keep track of nodes to visit next in a graph?

easy

A. A hash map

B. A stack data structure

C. A priority queue

D. A queue data structure

Solution

1. Step 1: Understand BFS traversal method

   BFS explores nodes level by level, visiting all neighbors before moving deeper.

2. Step 2: Identify the data structure used

   To achieve level order traversal, BFS uses a queue to process nodes in the order they are discovered.

3. Final Answer:

   A queue data structure -> Option D

4. Quick Check:

   BFS uses queue = C [OK]

Hint: BFS uses queue to explore neighbors level-wise [OK]

Common Mistakes:

• Confusing BFS with DFS which uses stack
• Thinking BFS uses priority queue
• Assuming BFS uses hash map for traversal order

2. Which of the following Rust code snippets correctly initializes a queue for BFS traversal using the standard library?

easy

A. let mut queue = HashMap::new();

B. let mut queue = Vec::new();

C. let mut queue = VecDeque::new();

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

Solution

1. Step 1: Identify the correct queue type in Rust

   Rust's standard library provides VecDeque for efficient queue operations (push_back, pop_front).

2. Step 2: Check each option

   let mut queue = VecDeque::new(); uses VecDeque::new(), which is correct. Vec is a dynamic array, not ideal for queue. HashMap and BinaryHeap are not queues.

3. Final Answer:

   let mut queue = VecDeque::new(); -> Option C

4. Quick Check:

   VecDeque is queue in Rust [OK]

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

Common Mistakes:

• Using Vec which is not efficient for queue
• Using HashMap which is for key-value pairs
• Using BinaryHeap which is a priority queue

3. Given the following Rust code for BFS on a graph represented as adjacency list, what is the order of nodes visited starting from node 0?

use std::collections::VecDeque;

fn bfs(graph: &Vec, start: usize) -> Vec<usize> {
    let mut visited = vec![false; graph.len()];
    let mut queue = VecDeque::new();
    let mut order = Vec::new();

    visited[start] = true;
    queue.push_back(start);

    while let Some(node) = queue.pop_front() {
        order.push(node);
        for &neighbor in &graph[node] {
            if !visited[neighbor] {
                visited[neighbor] = true;
                queue.push_back(neighbor);
            }
        }
    }
    order
}

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

medium

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

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

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

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

Solution

1. Step 1: Start BFS from node 0

   Visit node 0, enqueue neighbors 1 and 2.

2. Step 2: Visit nodes in queue order

   Dequeue 1, visit it, enqueue neighbor 3 (0 already visited). Dequeue 2, visit it, enqueue neighbor 4.

3. Step 3: Continue visiting remaining nodes

   Dequeue 3, visit it (neighbor 1 visited). Dequeue 4, visit it (neighbor 2 visited).

4. Final Answer:

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

5. Quick Check:

   BFS order from 0 = [0,1,2,3,4] [OK]

Hint: BFS visits neighbors level-wise in order discovered [OK]

Common Mistakes:

• Mixing BFS with DFS order
• Visiting neighbors out of order
• Forgetting to mark visited nodes

4. The following Rust BFS code has a bug causing it to panic at runtime. What is the error?

use std::collections::VecDeque;

fn bfs(graph: &Vec, start: usize) -> Vec<usize> {
    let mut visited = vec![false; graph.len()];
    let mut queue = VecDeque::new();
    let mut order = Vec::new();

    visited[start] = true;
    queue.push_back(start);

    while let Some(node) = queue.pop_front() {
        order.push(node);
        for &neighbor in &graph[node] {
            if !visited[neighbor] {
                queue.push_back(neighbor);
            }
        }
    }
    order
}

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

medium

A. Missing visited[neighbor] = true; causes infinite loop

B. Queue is not initialized properly

C. Graph adjacency list is empty

D. Start node index is out of bounds

Solution

1. Step 1: Analyze BFS loop and visited marking

   The code pushes neighbors to queue but never marks them visited.

2. Step 2: Understand consequence of missing visited update

   Without marking visited, neighbors get re-added repeatedly causing infinite loop or panic.

3. Final Answer:

   Missing visited[neighbor] = true; causes infinite loop -> Option A

4. Quick Check:

   Mark visited before enqueue = prevent infinite loop [OK]

Hint: Always mark visited before enqueueing neighbors [OK]

Common Mistakes:

• Forgetting to mark nodes visited before enqueue
• Assuming queue initialization causes panic
• Ignoring start node validity

5. You want to find the shortest path length from node 0 to node 4 in an unweighted graph using BFS. Which modification to the BFS code below will correctly compute the shortest distance?

use std::collections::VecDeque;

fn shortest_path_length(graph: &Vec, start: usize, target: usize) -> Option<usize> {
    let mut visited = vec![false; graph.len()];
    let mut distance = vec![0; graph.len()];
    let mut queue = VecDeque::new();

    visited[start] = true;
    queue.push_back(start);

    while let Some(node) = queue.pop_front() {
        if node == target {
            return Some(distance[node]);
        }
        for &neighbor in &graph[node] {
            if !visited[neighbor] {
                visited[neighbor] = true;
                queue.push_back(neighbor);
                // What to add here?
            }
        }
    }
    None
}

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

hard

A. distance[neighbor] = 1;

B. distance[neighbor] = distance[node] + 1;

C. distance[neighbor] += 1;

D. distance[neighbor] = distance[node];

Solution

1. Step 1: Understand BFS distance tracking

   Distance to neighbor is distance to current node plus one edge.

2. Step 2: Choose correct distance update

   Assign distance[neighbor] = distance[node] + 1 to track shortest path length.

3. Final Answer:

   distance[neighbor] = distance[node] + 1; -> Option B

4. Quick Check:

   Distance increments by 1 per edge [OK]

Hint: Set neighbor distance = current node distance + 1 [OK]

Common Mistakes:

• Not updating distance correctly
• Using += 1 without initialization
• Setting distance to constant 1 always