Activity 36: Implement BFS

Format: Rust playground, submit on gradescope

Task: Complete the BFS implementation to find shortest paths in a graph

Part 1: Understanding the Setup

The graph is represented as an adjacency list:

  • graph[i] contains a vector of all neighbors of vertex i
  • Example: graph[0] = vec![1, 2] means vertex 0 connects to vertices 1 and 2

Data structures used:

  • queue: VecDeque - BFS explores vertices level by level (FIFO)
  • visited: HashSet - Track which vertices we've already seen
  • parent: HashMap - Track how we reached each vertex (for path reconstruction)

Part 2: Complete the Implementation

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

fn bfs_shortest_path(
    graph: &Vec<Vec<usize>>,
    start: usize,
    end: usize
) -> Option<Vec<usize>> {
    // Initialize data structures for BFS
    let mut queue = VecDeque::new();
    let mut visited = HashSet::new();
    let mut parent: HashMap<usize, usize> = HashMap::new();

    // Start BFS from the start vertex
    // TODO: Add start to queue
    // TODO: Add start to visited

    // BFS main loop: explore vertices level by level
    while !queue.is_empty() {
        // TODO: let vertex = the next value coming from the queue

        if vertex == end {
            // Found the destination! Now reconstruct the path
            // The path goes: start -> ... -> end
            // We need to follow parent pointers backward from end to start

            // TODO: Create an empty vector called 'path'

            // TODO: Create a variable 'current' and set it to 'end'

            // TODO: Write a loop that continues while 'current' is in the parent map
            // Inside the loop:
            //   1. Push 'current' to the path vector
            //   2. Update 'current' to be the parent of current

            // TODO: Push 'start' to the path (it won't be in the parent map)

            // TODO: Reverse the path (we built it backward!)
            // Hint: use path.reverse()

            // TODO: Return Some(path)
        }

        // If we're not done yet - explore all neighbors of current vertex
        for &neighbor in &graph[vertex] {
            //TODO: if visited contains &neighbor, skip (continue)
            //TODO: add neighbor to visited
            //TODO: add the neighbor-vertex pair to the parent hashmap
            //TODO: add neighbor to the queue
        }
    }

    None  // No path exists from start to end
}

fn main() {
    // Example graph structure:
    //     0 --- 1 --- 4
    //     |     |
    //     2 --- 3 --- 5
    //           |
    //           6
    let graph = vec![
        vec![1, 2],       // 0 connects to 1, 2
        vec![0, 3, 4],    // 1 connects to 0, 3, 4
        vec![0, 3],       // 2 connects to 0, 3
        vec![1, 2, 5, 6], // 3 connects to 1, 2, 5, 6
        vec![1],          // 4 connects to 1
        vec![3],          // 5 connects to 3
        vec![3],          // 6 connects to 3
    ];

    println!("=== BFS Shortest Path Tests ===\n");

    // Test 1: Simple path
    if let Some(path) = bfs_shortest_path(&graph, 0, 4) {
        println!("Path from 0 to 4: {:?}", path);
        println!("Expected: [0, 1, 4]");
        println!("Length: {}\n", path.len());
    }

    // Test 2: Longer path
    if let Some(path) = bfs_shortest_path(&graph, 0, 6) {
        println!("Path from 0 to 6: {:?}", path);
        println!("Expected: [0, 1, 3, 6] or [0, 2, 3, 6]");
        println!("Length: {}\n", path.len());
    }

    // Test 3: Path to adjacent vertex
    if let Some(path) = bfs_shortest_path(&graph, 3, 5) {
        println!("Path from 3 to 5: {:?}", path);
        println!("Expected: [3, 5]");
        println!("Length: {}\n", path.len());
    }

    // Test 4: Start equals end
    if let Some(path) = bfs_shortest_path(&graph, 2, 2) {
        println!("Path from 2 to 2: {:?}", path);
        println!("Expected: [2]");
        println!("Length: {}\n", path.len());
    }

    // Test 5: Disconnected graph (no path exists)
    let disconnected = vec![
        vec![1],    // 0 connects to 1
        vec![0],    // 1 connects to 0
        vec![3],    // 2 connects to 3 (separate component)
        vec![2],    // 3 connects to 2
    ];

    match bfs_shortest_path(&disconnected, 0, 3) {
        Some(path) => println!("Path from 0 to 3: {:?} (unexpected!)", path),
        None => println!("No path from 0 to 3 (correct - graph is disconnected)"),
    }
}

Expected Output

=== BFS Shortest Path Tests ===

Path from 0 to 4: [0, 1, 4]
Expected: [0, 1, 4]
Length: 3

Path from 0 to 6: [0, 1, 3, 6]
Expected: [0, 1, 3, 6] or [0, 2, 3, 6]
Length: 4

Path from 3 to 5: [3, 5]
Expected: [3, 5]
Length: 2

Path from 2 to 2: [2]
Expected: [2]
Length: 1

No path from 0 to 3 (correct - graph is disconnected)

Questions for Reflection

  1. Why does BFS find the shortest path?
  2. What would happen if we used a stack (DFS) instead of a queue?
  3. What is the time complexity of BFS? (Think about V vertices and E edges)
  4. Why do we need the visited set? What would happen without it?