Step 2 of 7

Breadth-first search with VecDeque

Breadth-first search (BFS) explores a graph in layers: first the start node, then every node one edge away, then every node two edges away, and so on, like ripples in a pond. To visit nodes in that order it uses a FIFO queue, a VecDeque.

Because it goes layer by layer, the first time BFS reaches a node it got there with the fewest possible edges. So in an unweighted graph BFS finds shortest paths (fewest hops): the fewest network hops between servers, the fewest moves in a puzzle, the "degrees of separation" between two people.

use std::collections::VecDeque;

fn bfs(adj: &[Vec<usize>], start: usize) -> Vec<Option<usize>> {
    let mut dist = vec![None; adj.len()];
    let mut queue = VecDeque::new();
    dist[start] = Some(0);
    queue.push_back((start, 0));
    while let Some((u, d)) = queue.pop_front() {
        for &v in &adj[u] {
            if dist[v].is_none() {
                dist[v] = Some(d + 1); // mark when you push, not when you pop
                queue.push_back((v, d + 1));
            }
        }
    }
    dist
}

fn main() {
    // the stations from the last step, plus station 5 with no tracks
    let adj = vec![vec![1, 2], vec![0, 3], vec![0, 3], vec![1, 2, 4], vec![3], vec![]];
    for (station, d) in bfs(&adj, 0).iter().enumerate() {
        match d {
            Some(hops) => println!("station {station}: distance {hops}"),
            None => println!("station {station}: unreachable"),
        }
    }
}

station 0: distance 0
station 1: distance 1
station 2: distance 1
station 3: distance 2
station 4: distance 3
station 5: unreachable

• dist doubles as the "visited" marker: None means not reached yet.
• Each node enters the queue at most once and each edge is looked at once (twice when undirected): O(V + E).

Grids are graphs too

In a maze or a map, every open cell is a node and its neighbors are the cells up, down, left and right. You don't build adjacency lists; you compute the neighbors on the fly. With usize coordinates, r - 1 panics at row 0, so a common trick is r.wrapping_sub(1): at 0 it wraps around to a huge number, which then fails the bounds check (grid.get(r) returns None) like any other off-grid cell.

for (nr, nc) in [(r.wrapping_sub(1), c), (r + 1, c), (r, c.wrapping_sub(1)), (r, c + 1)] {
    if matches!(grid.get(nr).and_then(|row| row.get(nc)), Some(&cell) if cell != b'#') {
        // (nr, nc) is an open neighbor
    }
}

Common mistakes

• Marking visited when popping instead of when pushing. A node can then be pushed many times (once per neighbor that sees it) before it's popped. Results may still be right, but the queue can blow up on dense graphs.
• A Vec with remove(0) as the queue. O(n) per pop, O(V²) overall.
• DFS for shortest paths. Depth-first search finds a path, not the shortest one.
• Weighted edges. BFS counts edges. When edges have different costs, you need Dijkstra (later in this module).

Your task

Write fn shortest_hops(adj: &[Vec<usize>], from: usize, to: usize) -> Option<usize>: the fewest edges on a path from from to to in a directed graph given as adjacency lists, or None if to can't be reached (Some(0) when from == to). The tests include a graph of 200,000 nodes.

Challenge 2

Write a maze solver. Standard input is a grid, one row per line: S is the start, E the exit, # a wall and . open floor. You can move up, down, left or right. Print shortest path: N steps with the fewest moves from S to E, or no path.

Use BFS over the cells with a VecDeque<((usize, usize), usize)> of positions and distances, and a Vec<Vec<bool>> of visited cells. The lesson's wrapping_sub trick handles the edges of the grid.

Challenge 3

Showing how many hops isn't enough for the network team; they want the route itself. Write fn shortest_route(adj: &[Vec<usize>], from: usize, to: usize) -> Option<Vec<usize>> that returns the nodes of a shortest path from from to to, both included ([from] when they're equal), or None. In every test the shortest path is unique.

During BFS, record each node's parent: the node you were at when you first discovered it (parent: Vec<Option<usize>>). When you reach to, follow the parents back to from and reverse the list.

Previous: Representing graphs: adjacency lists Next: Depth-first search: recursion and an explicit stack