RustArena

Step 3 of 7

Depth-first search: recursion and an explicit stack

Depth-first search (DFS) goes as deep as it can along one path, and only when it gets stuck does it back up and try the next branch. It's the natural way to ask "what can I reach from here?", to count separate groups (connected components), to detect cycles, to flood-fill a region of a map, and it's the basis of topological sorting.

Recursion expresses it directly: visit a node, then recursively visit each unvisited neighbor.

fn explore(u: usize, adj: &[Vec<usize>], seen: &mut [bool], members: &mut Vec<usize>) {
    seen[u] = true;
    members.push(u);
    for &v in &adj[u] {
        if !seen[v] {
            explore(v, adj, seen, members);
        }
    }
}

fn main() {
    // friendships: 0-1, 1-2, 3-4, and 5 knows nobody
    let adj = vec![vec![1], vec![0, 2], vec![1], vec![4], vec![3], vec![]];
    let mut seen = vec![false; adj.len()];
    for start in 0..adj.len() {
        if !seen[start] {
            let mut members = Vec::new();
            explore(start, &adj, &mut seen, &mut members);
            println!("group: {members:?}");
        }
    }
}

group: [0, 1, 2]
group: [3, 4]
group: [5]

The outer loop starts a new DFS from every node not seen yet; each DFS marks one whole component. Every node and edge is handled once: O(V + E).

The same thing with a stack

Recursion depth equals the length of the path DFS is following. On a long chain or a big grid that can be hundreds of thousands of calls deep, and the program dies with thread 'main' (4242) has overflowed its stack. The fix is to keep your own stack in a Vec, which lives on the heap and can grow as needed:

fn reachable(adj: &[Vec<usize>], start: usize) -> Vec<usize> {
    let mut seen = vec![false; adj.len()];
    let mut stack = vec![start];
    let mut order = Vec::new();
    while let Some(u) = stack.pop() {
        if seen[u] {
            continue; // pushed twice before we got to it
        }
        seen[u] = true;
        order.push(u);
        for &v in adj[u].iter().rev() {
            if !seen[v] {
                stack.push(v);
            }
        }
    }
    order
}

fn main() {
    let adj = vec![vec![1, 3], vec![2], vec![], vec![4], vec![]];
    println!("{:?}", reachable(&adj, 0));
}

[0, 1, 2, 3, 4]

Pushing the neighbors in reverse makes the stack pop them in their original order, so the visiting order matches the recursive version. Here a node can sit on the stack more than once, so it's checked when popped (continue if already seen).

Common mistakes

Your task

Count the islands on a map. Write fn count_islands(map: &[&str]) -> usize where each string is a row, # is land and . is water. Land cells that touch up, down, left or right belong to the same island. Use DFS with an explicit stack (Vec<(usize, usize)>): the tests include a 700 by 700 map that is all land, where recursion would overflow the stack.

Challenge 2

The map team now wants the size of the largest island (the number of land cells in it), with the same map format: # land, . water, and only up, down, left and right connect. Write fn largest_island(map: &[&str]) -> usize (0 if there's no land). Recursion or an explicit stack are both fine here; the maps in these tests are small.

Challenge 3

Print a project's folder tree like the tree command. The first line of standard input is the name of the root folder. Every following line is PARENT CHILD: CHILD is directly inside PARENT. Print the tree from the root, one name per line, indented by two spaces per level, with each folder's children in alphabetical order:

project
  Cargo.toml
  src
    lib.rs
    main.rs

A recursive DFS is perfect here (folder trees are shallow). Store the children in a BTreeMap<String, BTreeSet<String>> so they come out sorted, and pass the depth down the recursion.

Previous: Breadth-first search with VecDeque Next: Topological sort: ordering tasks with dependencies