BFS Breadth First Search on Graph in DSA Rust - Build from Scratch

BFS Breadth First Search on Graph

📖 Scenario: You are working with a simple map of connected cities. You want to explore all cities reachable from a starting city using a method called Breadth First Search (BFS). BFS visits neighbors level by level, like checking all nearby cities before moving further.

🎯 Goal: Build a Rust program that uses BFS to visit all cities connected to a starting city and prints the order in which cities are visited.

📋 What You'll Learn

Create a graph using a Rust HashMap<String, Vec<String>> where keys are city names and values are lists of connected cities.

Create a queue to help with BFS traversal.

Use a HashSet<String> to keep track of visited cities.

Implement BFS starting from a given city and collect the order of visited cities.

Print the visited cities in BFS order separated by arrows.

💡 Why This Matters

🌍 Real World

Graph traversal like BFS is used in social networks to find friends of friends, in maps to find shortest paths, and in web crawlers to explore websites.

💼 Career

Understanding BFS is essential for software engineers working on search algorithms, network analysis, and many algorithmic problem-solving tasks.

1

Create the graph data structure

Create a HashMap<String, Vec<String>> called graph with these exact entries: "A" connected to ["B", "C"], "B" connected to ["A", "D", "E"], "C" connected to ["A", "F"], "D" connected to ["B"], "E" connected to ["B", "F"], and "F" connected to ["C", "E"].

DSA Rust

# Create the graph HashMap with the given city connections
# Your code here

Hint

Use HashMap::new() to create the graph. Use insert to add each city and its neighbors as Vec<String>.

2

Set up BFS helper variables

Add a VecDeque<String> called queue and a HashSet<String> called visited. Initialize queue with the starting city "A".to_string() and add "A".to_string() to visited.

DSA Rust

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

use std::collections::HashMap;

fn main() {
    let mut graph: HashMap> = HashMap::new();
    graph.insert("A".to_string(), vec!["B".to_string(), "C".to_string()]);
    graph.insert("B".to_string(), vec!["A".to_string(), "D".to_string(), "E".to_string()]);
    graph.insert("C".to_string(), vec!["A".to_string(), "F".to_string()]);
    graph.insert("D".to_string(), vec!["B".to_string()]);
    graph.insert("E".to_string(), vec!["B".to_string(), "F".to_string()]);
    graph.insert("F".to_string(), vec!["C".to_string(), "E".to_string()]);

    // Create queue and visited set for BFS
    // Your code here
}

Hint

Use VecDeque::new() for the queue and HashSet::new() for visited. Add "A".to_string() to both.

3

Implement BFS traversal logic

Write a while loop that runs while queue is not empty. Inside the loop, remove the front city from queue into a variable current. For each neighbor of current in graph, if the neighbor is not in visited, add it to visited and push it to the back of queue. Collect the visited cities in a Vec<String> called order in the order they are visited.

DSA Rust

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

fn main() {
    let mut graph: HashMap> = HashMap::new();
    graph.insert("A".to_string(), vec!["B".to_string(), "C".to_string()]);
    graph.insert("B".to_string(), vec!["A".to_string(), "D".to_string(), "E".to_string()]);
    graph.insert("C".to_string(), vec!["A".to_string(), "F".to_string()]);
    graph.insert("D".to_string(), vec!["B".to_string()]);
    graph.insert("E".to_string(), vec!["B".to_string(), "F".to_string()]);
    graph.insert("F".to_string(), vec!["C".to_string(), "E".to_string()]);

    let mut queue: VecDeque = VecDeque::new();
    let mut visited: HashSet = HashSet::new();

    queue.push_back("A".to_string());
    visited.insert("A".to_string());

    let mut order: Vec = Vec::new();

    // Use a while loop to process the queue
    // Your code here
}

Hint

Use while let Some(current) = queue.pop_front() to loop. Add current to order. For each neighbor, check if not visited, then add to visited and queue.

4

Print the BFS traversal order

Print the cities in order separated by arrows " -> ". Use println!("{}", order.join(" -> ")).

DSA Rust

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

fn main() {
    let mut graph: HashMap> = HashMap::new();
    graph.insert("A".to_string(), vec!["B".to_string(), "C".to_string()]);
    graph.insert("B".to_string(), vec!["A".to_string(), "D".to_string(), "E".to_string()]);
    graph.insert("C".to_string(), vec!["A".to_string(), "F".to_string()]);
    graph.insert("D".to_string(), vec!["B".to_string()]);
    graph.insert("E".to_string(), vec!["B".to_string(), "F".to_string()]);
    graph.insert("F".to_string(), vec!["C".to_string(), "E".to_string()]);

    let mut queue: VecDeque = VecDeque::new();
    let mut visited: HashSet = HashSet::new();

    queue.push_back("A".to_string());
    visited.insert("A".to_string());

    let mut order: Vec = Vec::new();

    while let Some(current) = queue.pop_front() {
        order.push(current.clone());
        if let Some(neighbors) = graph.get(&current) {
            for neighbor in neighbors {
                if !visited.contains(neighbor) {
                    visited.insert(neighbor.clone());
                    queue.push_back(neighbor.clone());
                }
            }
        }
    }

    // Print the BFS order
    // Your code here
}

Hint

Use println!("{}", order.join(" -> ")) to print the visited cities separated by arrows.

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