BFS Breadth First Search on Graph in DSA Rust - Execution Trace

Concept Flow - BFS Breadth First Search on Graph

Start at source node

↓

Mark node visited

↓

Add neighbors to queue

↓

Dequeue next node

↓

If queue empty?

Yes→End

No↓

Repeat: Mark visited, enqueue neighbors

BFS starts at a node, visits it, adds neighbors to a queue, then visits nodes in queue order until all reachable nodes are visited.

Execution Sample

DSA Rust

graph = {
  'A': ['B', 'D'],
  'B': ['A', 'C'],
  'C': ['B', 'F'],
  'D': ['A', 'E'],
  'E': ['D', 'F'],
  'F': ['C', 'E']
}

bfs('A')

Perform BFS starting from node 'A' on the given graph.

Execution Table

Step	Operation	Current Node	Visited Set	Queue	Visual State
1	Start BFS	A	{}	[]	Graph: A-B-C-F, D-E-F connections
2	Visit node	A	{A}	[]	Visited: A
3	Enqueue neighbors	A	{A}	[B, D]	Queue: B, D
4	Dequeue next	B	{A}	[D]	Queue after dequeue: D
5	Visit node	B	{A, B}	[D]	Visited: A, B
6	Enqueue neighbors	B	{A, B}	[D, C]	Queue: D, C (C added)
7	Dequeue next	D	{A, B}	[C]	Queue after dequeue: C
8	Visit node	D	{A, B, D}	[C]	Visited: A, B, D
9	Enqueue neighbors	D	{A, B, D}	[C, E]	Queue: C, E (E added)
10	Dequeue next	C	{A, B, D}	[E]	Queue after dequeue: E
11	Visit node	C	{A, B, C, D}	[E]	Visited: A, B, C, D
12	Enqueue neighbors	C	{A, B, C, D}	[E, F]	Queue: E, F (F added)
13	Dequeue next	E	{A, B, C, D}	[F]	Queue after dequeue: F
14	Visit node	E	{A, B, C, D, E}	[F]	Visited: A, B, C, D, E
15	Enqueue neighbors	E	{A, B, C, D, E}	[F]	Neighbors D, F; D visited, F already in queue
16	Dequeue next	F	{A, B, C, D, E}	[]	Queue after dequeue: empty
17	Visit node	F	{A, B, C, D, E, F}	[]	Visited all nodes
18	Enqueue neighbors	F	{A, B, C, D, E, F}	[]	Neighbors C, E visited, no new enqueue
19	Check queue empty	-	{A, B, C, D, E, F}	[]	Queue empty, BFS ends

💡 Queue is empty, all reachable nodes visited.

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 12	After Step 15	After Step 18	Final
Visited Set	{}	{A}	{A, B}	{A, B, D}	{A, B, C, D}	{A, B, C, D, E}	{A, B, C, D, E, F}	{A, B, C, D, E, F}
Queue	[]	[B, D]	[D, C]	[C, E]	[E, F]	[F]	[]	[]
Current Node	None	A	B	D	C	E	F	None

Key Moments - 3 Insights

Why do we add neighbors to the queue only if they are not visited?

Because adding visited nodes again would cause repeated visits and possibly infinite loops. See steps 15 and 18 where neighbors already visited are not enqueued again.

Why does BFS use a queue instead of a stack?

A queue ensures nodes are visited in the order they are discovered, exploring neighbors level by level. This is shown in the queue updates at steps 3, 6, 9, and 12.

What happens when the queue becomes empty?

When the queue is empty (step 19), BFS ends because there are no more nodes to visit. All reachable nodes have been processed.

Visual Quiz - 3 Questions

Look at the execution table, what is the queue after step 6?

A [B, D]

B [C, E]

C [D, C]

D [E, F]

💡 Hint

Check the 'Queue' column in the execution table row for step 6.

At which step does BFS visit node 'E'?

A Step 9

B Step 14

C Step 12

D Step 17

💡 Hint

Look for 'Visit node' operation with current node 'E' in the execution table.

If node 'F' was not connected to any node, how would the visited set change?

A It would never include 'F'

B It would include 'F' at the end

C It would include 'F' immediately

D It would include 'F' after 'A'

💡 Hint

Refer to the variable_tracker for visited nodes and consider connectivity.

Concept Snapshot

BFS uses a queue to visit nodes level by level.
Start at source, mark visited, enqueue neighbors.
Dequeue nodes, visit, enqueue unvisited neighbors.
Stop when queue is empty.
Prevents revisiting nodes by tracking visited set.

Full Transcript

Breadth First Search (BFS) explores a graph by visiting nodes in layers. Starting from a source node, it marks the node visited and adds all its neighbors to a queue. Then it repeatedly dequeues the next node, visits it, and enqueues its unvisited neighbors. This process continues until the queue is empty, meaning all reachable nodes have been visited. The queue ensures nodes are visited in the order they are discovered, exploring neighbors level by level. The visited set prevents revisiting nodes and infinite loops. This example shows BFS starting at node 'A' and visiting nodes in order: A, B, D, C, E, F.

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