BFS and DFS in Rust

Drop a pebble into a still pond. A ring spreads out from the spot, then a wider ring, then a wider one. The water nearest the pebble moves first, and the far bank moves last.

That is breadth-first search, or BFS. You start at one place in a graph (lesson 10) and visit everything one step away. Then everything two steps away. Then three. Breadth means you spread wide before you go deep.

There is a second way to explore, and it is how most people walk a maze. You pick one corridor and follow it as far as it goes. At the dead end, you back up to the last fork and try the next corridor. That is depth-first search, or DFS. Depth means you go deep before you go wide.

Both visit every vertex you can reach from the start, and both cost the same. They differ in the order, and the order is what makes each one useful. Reach for BFS when "fewest steps" matters. Reach for DFS when you need to explore everything in a piece, or try every path, as in lesson 16.

Both searches share one skeleton. You keep a to-do list of vertices to visit. Take one off the list, visit it, and add its unvisited neighbours to the list. Repeat until the list is empty. The only difference is which end of the list you take from.

• Take from the front, adding to the back: that is a queue (lesson 5), first in, first out. The oldest entry goes first, so the nearest vertices are finished before the farther ones. That is BFS, and it makes the rings.
• Take from the back, adding to the back: that is a stack (lesson 4), last in, first out. The newest entry goes first, so you keep following the road you just found. That is DFS.

Walk through the picture with BFS. Start with vertex 0. Visit it, and add its neighbours 1, 2 and 3 to the queue. Take 1 from the front, visit it, and add its new neighbour 4. Take 2, and add 5 and 6. Take 3, and add 7. The queue now holds 4, 5, 6, 7, and those are the second ring, in the order they are taken. DFS on the same graph goes 0, 1, 4, and then has to back up to reach 2.

The visited set. There is one rule you must never skip. Keep a record of vertices you have seen, and never add one twice. Real graphs have loops: a road from A to B, and B back to A. Without a record, the search would go round and round forever. A Vec<bool> indexed by vertex works, because vertices are numbers. A HashSet works when they are names.

A graph in pieces. A search from one vertex only reaches the vertices connected to it, its own component. If the graph has several pieces, you start a fresh search at every vertex you have not seen yet. The number of fresh starts is the number of pieces.

Remember: BFS uses a queue and finds the nearest first. DFS uses a stack and goes deep first. Both need a visited record.

These functions take the bare list from lesson 10. There, a Graph kept it in a field called adj, where adj[v] lists the neighbours of vertex v. Here, the functions take that list directly, so each snippet runs on its own. A small helper builds one.

/// The graph from lesson 10, as the bare list: `adj[v]` holds the vertices
/// next to `v`. This builds one for two-way roads between numbered vertices.
pub fn adjacency(n: usize, edges: &[(usize, usize)]) -> Vec<Vec<usize>> {
    let mut adj = vec![Vec::new(); n];
    for &(a, b) in edges {
        adj[a].push(b);
        adj[b].push(a);
    }
    adj
}

Each road (a, b) is added in both directions, because roads go two ways. Now BFS.

use std::collections::VecDeque;

/// Visits every vertex reachable from `start`, nearest first, like ripples.
/// Returns the vertices in the order they were visited.
pub fn bfs_order(adj: &[Vec<usize>], start: usize) -> Vec<usize> {
    let mut visited = vec![false; adj.len()];
    let mut queue = VecDeque::new();
    let mut order = Vec::new();

    // Mark a vertex the moment it joins the queue, so it can never join twice.
    visited[start] = true;
    queue.push_back(start);

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

Go through it in order.

• visited has one flag per vertex, and queue is a VecDeque, the queue from lesson 5.
• The start is marked visited as it joins the queue. Marking at joining, not at visiting, is what stops a vertex from joining twice.
• The loop takes from the front with pop_front, records the vertex, and adds every neighbour not yet seen to the back.
• When the queue is empty, every reachable vertex has been visited, and order holds them nearest first.

The demo below it builds the graph in the picture and prints the order.

Now DFS. The recursive version is shorter, because the call stack from lesson 16 is the stack.

/// Visits every vertex reachable from `start`, going as deep as possible down
/// one road before backing up. Returns the visiting order.
pub fn dfs_order(adj: &[Vec<usize>], start: usize) -> Vec<usize> {
    let mut visited = vec![false; adj.len()];
    let mut order = Vec::new();
    visit(adj, start, &mut visited, &mut order);
    order
}

fn visit(adj: &[Vec<usize>], v: usize, visited: &mut [bool], order: &mut Vec<usize>) {
    visited[v] = true;
    order.push(v);
    for &w in &adj[v] {
        if !visited[w] {
            visit(adj, w, visited, order);
        }
    }
}

visit marks the vertex, records it, and then calls itself on every neighbour not yet seen. Each call goes as deep as it can before returning. When a call returns, that is the "back up to the last fork" step.

For a very deep graph, recursion can overflow the call stack (see the note in lesson 16). The fix is to use a Vec as the stack yourself.

/// The same walk without recursion. A `Vec` used as a stack plays the part of
/// the call stack. Swap it for a queue and this becomes BFS.
pub fn dfs_order_stack(adj: &[Vec<usize>], start: usize) -> Vec<usize> {
    let mut visited = vec![false; adj.len()];
    let mut stack = vec![start];
    let mut order = Vec::new();

    while let Some(v) = stack.pop() {
        if visited[v] {
            continue; // it was pushed twice before we got to it
        }
        visited[v] = true;
        order.push(v);
        // Reversed, so the first neighbour is on top and is visited first.
        for &w in adj[v].iter().rev() {
            if !visited[w] {
                stack.push(w);
            }
        }
    }
    order
}

Compare it with BFS. It is the same loop, but pop takes from the back instead of pop_front from the front. That one change turns ripples into corridors. Here a vertex may be pushed twice before it is reached, so a check at the top skips any that were already visited. The neighbours are pushed in reverse so that the first neighbour ends up on top and is explored first, which gives the same order as the recursive version.

Remember: swap the queue for a stack, and BFS becomes DFS.

Finally, counting pieces. Start a search at every vertex not yet seen.

/// How many separate pieces the graph is in. A search from one vertex only
/// reaches its own piece, so start a new search at every vertex not seen yet.
pub fn count_components(adj: &[Vec<usize>]) -> usize {
    let mut visited = vec![false; adj.len()];
    let mut pieces = 0;

    for start in 0..adj.len() {
        if visited[start] {
            continue;
        }
        pieces += 1;
        visited[start] = true;
        let mut stack = vec![start];
        while let Some(v) = stack.pop() {
            for &w in &adj[v] {
                if !visited[w] {
                    visited[w] = true;
                    stack.push(w);
                }
            }
        }
    }
    pieces
}

Each time the outer loop finds an unseen vertex, that is a new piece. The small search inside marks the whole piece as seen. A vertex with no roads is a piece of its own.

You have already met every tool. VecDeque is the queue, because push_back and pop_front are both O(1). A plain Vec is the stack, with push and pop. And HashSet is the visited record when your vertices are names instead of numbers.

Real data has names. Here is BFS over a friendship map, using a HashMap for the neighbours and a HashSet for the visited names. The Playground link runs it.

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

// The same walk on names. A map holds the neighbours, a set the visited.
let mut friends: HashMap<&str, Vec<&str>> = HashMap::new();
friends.insert("Asha", vec!["Ben", "Chen"]);
friends.insert("Ben", vec!["Asha", "Dia"]);
friends.insert("Chen", vec!["Asha"]);
friends.insert("Dia", vec!["Ben"]);

let mut seen = HashSet::new();
let mut queue = VecDeque::new();
seen.insert("Asha");
queue.push_back("Asha");

let mut order = Vec::new();
while let Some(person) = queue.pop_front() {
    order.push(person);
    for &friend in &friends[person] {
        // `insert` says false if the name was already in the set.
        if seen.insert(friend) {
            queue.push_back(friend);
        }
    }
}

println!("{:?}", order);
assert_eq!(order, ["Asha", "Ben", "Chen", "Dia"]);

The neat part is seen.insert(friend). A HashSet's insert returns true if the name was new and false if it was already there. So that one call checks and marks together, and the if adds the friend to the queue only the first time.

The standard library has no ready-made BFS or DFS. (The petgraph crate has both, if you need them in a project.) The pieces are small enough that you will write them yourself, and interviewers expect you to.

The cost says V + E, not V × E, because a vertex's neighbour list is read only once, when the vertex is visited. A queue can hold up to V vertices at once, and a stack as well.

Two of these use a grid. A grid is a graph without being drawn as one: each cell is a vertex, and its neighbours are the cells above, below, left and right. You never build a list of neighbours. You work out the four positions as you go. Each starter has a todo!(), a placeholder that panics if it runs. Replace it with your code.

pub fn count_islands(grid: &[Vec<u8>]) -> usize {
    todo!("every 1 you have not seen starts a new island; then flood it")
}

/// `1` is land and `0` is water. An island is land joined up, down, left
/// or right.
pub fn count_islands(grid: &[Vec<u8>]) -> usize {
    let rows = grid.len();
    let cols = grid.first().map_or(0, |row| row.len());
    let mut seen = vec![vec![false; cols]; rows];
    let mut islands = 0;

    for r in 0..rows {
        for c in 0..cols {
            if grid[r][c] != 1 || seen[r][c] {
                continue;
            }
            // New land. Flood every piece joined to it, so it counts once.
            islands += 1;
            seen[r][c] = true;
            let mut stack = vec![(r, c)];
            while let Some((r, c)) = stack.pop() {
                for (dr, dc) in [(0isize, 1isize), (1, 0), (0, -1), (-1, 0)] {
                    // `checked_add_signed` stops a step off the top or left edge.
                    let (Some(nr), Some(nc)) = (r.checked_add_signed(dr), c.checked_add_signed(dc))
                    else {
                        continue;
                    };
                    if nr < rows && nc < cols && grid[nr][nc] == 1 && !seen[nr][nc] {
                        seen[nr][nc] = true;
                        stack.push((nr, nc));
                    }
                }
            }
        }
    }
    islands
}

pub fn has_path(adj: &[Vec<usize>], from: usize, to: usize) -> bool {
    todo!("can a search from `from` ever reach `to`?")
}

pub fn has_path(adj: &[Vec<usize>], from: usize, to: usize) -> bool {
    use std::collections::VecDeque;

    let mut visited = vec![false; adj.len()];
    let mut queue = VecDeque::from([from]);
    visited[from] = true;

    while let Some(v) = queue.pop_front() {
        if v == to {
            return true;
        }
        for &w in &adj[v] {
            if !visited[w] {
                visited[w] = true;
                queue.push_back(w);
            }
        }
    }
    false
}

pub fn maze_steps(maze: &[Vec<u8>]) -> Option<usize> {
    todo!("ripples out from the top-left corner")
}

/// `0` is open and `1` is a wall. The fewest steps (up, down, left, right)
/// from the top-left to the bottom-right, or `None` if there is no way.
pub fn maze_steps(maze: &[Vec<u8>]) -> Option<usize> {
    use std::collections::VecDeque;

    let rows = maze.len();
    let cols = maze.first().map_or(0, |row| row.len());
    if rows == 0 || cols == 0 || maze[0][0] == 1 || maze[rows - 1][cols - 1] == 1 {
        return None;
    }

    // `steps[r][c]` is how far the ripple had travelled when it got there.
    let mut steps = vec![vec![None; cols]; rows];
    steps[0][0] = Some(0);
    let mut queue = VecDeque::from([(0, 0)]);

    while let Some((r, c)) = queue.pop_front() {
        let here: usize = steps[r][c].unwrap_or(0);
        if (r, c) == (rows - 1, cols - 1) {
            return Some(here);
        }
        for (dr, dc) in [(0isize, 1isize), (1, 0), (0, -1), (-1, 0)] {
            let (Some(nr), Some(nc)) = (r.checked_add_signed(dr), c.checked_add_signed(dc)) else {
                continue;
            };
            if nr < rows && nc < cols && maze[nr][nc] == 0 && steps[nr][nc].is_none() {
                steps[nr][nc] = Some(here + 1);
                queue.push_back((nr, nc));
            }
        }
    }
    None
}

Graph search appears in more interview questions than any other idea in this course. Many of them do not mention a graph at all.

• Spot the signals. "Connected", "reachable", "islands", "shortest number of steps", "minimum moves", "every path", and "number of groups" all point here. A grid with moves between cells is a graph. So is a word puzzle where one change turns a word into the next.
• Pick the search on purpose. "Fewest steps" means BFS. "Does any path exist", "count the pieces", and "try every path" mean DFS or BFS, with DFS usually shorter to write.
• Say the visited rule. Name it first: "I mark a vertex when I add it, so nothing is queued twice." A missing visited record is the classic bug, and it makes the program run forever on a loop.
• Handle every piece. If the question could have several separate pieces, say that one search from one start is not enough, and loop over all starts.
• Know the cost. O(V + E) time and O(V) space. On a grid, that is O(rows × columns).
• Mention the stack depth. Recursive DFS on a huge graph can overflow the call stack. Offering the version with your own Vec shows you have thought about it.
• Say the one-line difference. "They are the same loop. BFS takes from a queue and DFS takes from a stack." It is short, it is true, and it shows you see the whole picture.

Made by VeraStack Labs