Graph traversal

A graph is a set of states and the moves allowed between them. Sometimes you get it as a list of edges. Other times it's hidden in a grid, a lock, word changes, or a sequence of actions. Defining the state correctly is often harder than writing the BFS.

DFS goes deep down one branch first. It's good for "can I reach it?", for finding connected groups, and for learning about structure. BFS handles states in order of how many edges they are from the start. When every edge costs the same, the first time BFS reaches a node gives its shortest distance. Mark a node as seen when you add it to the queue, so it isn't added twice.

pub fn bfs_dist(adj: &[Vec<usize>], start: usize) -> Vec<Option<usize>> {
    use std::collections::VecDeque;
    assert!(start < adj.len());
    let mut dist = vec![None; adj.len()];
    let mut queue = VecDeque::from([start]);
    dist[start] = Some(0);
    while let Some(u) = queue.pop_front() {
        let next_distance = dist[u].unwrap() + 1;
        for &v in &adj[u] {
            if dist[v].is_none() {
                dist[v] = Some(next_distance);
                queue.push_back(v);
            }
        }
    }
    dist
}

The node numbers must be valid indexes. This takes O(V + E) time and O(V) extra space, not counting the adjacency list. None means unreachable. To find the distance to the nearest of several sources, put all of them in the queue at distance 0 and run one BFS.

A "seen" set only works if its key is the full state. In a grid with keys to collect, position alone isn't enough: reaching the same cell with different keys changes where you can go next. The state might be (row, column, keys held). Two different paths can share a state only when their futures and costs are the same.

For a grid, decide what counts as a neighbor: four directions or eight, the edges of the grid, blocked cells, and whether you can revisit cells. Flood fill asks "can I reach it?" Shortest route asks "how far?" A DFS that happens to reach the target first usually doesn't find the shortest route.

To find a cycle in an undirected graph, ignore the edge back to the node you came from, and look for any other neighbor you've already seen. Repeated edges between the same two nodes need extra care. In a directed graph, track whether a node is "in progress" or "done", or use topological sort. A single "seen" flag isn't enough for every cycle check.

Practice: LC 200 Number of Islands, LC 133 Clone Graph, LC 994 Rotting Oranges, LC 127 Word Ladder, LC 752 Open the Lock, LC 864 Shortest Path to Get All Keys.

Check your understanding: What are the nodes? What makes a move allowed? Is reaching the same place with different resources the same state? Does every move cost the same?