Graph BFS

At a glance

The instinct

Breadth-first search explores everything 1 step away, then everything 2 steps away, and so on. Because rings are finished in order, the first time a node is dequeued (or enqueued) is via a shortest path when all edges cost the same. That single property makes BFS the default for "minimum number of moves" questions.

The hard part is rarely the BFS itself. It is modelling the state: deciding what a node is (a cell, a word, a lock combination, a cell plus remaining obstacle removals) and what counts as one move.

Recognise it

Not this pattern if...

• Edges have different positive weights: Dijkstra (or 0-1 BFS when weights are only 0 and 1).
• You only need connectivity or component size: DFS is equally fine and often shorter.
• The question asks for all paths, not the shortest: DFS with backtracking.
• Order must respect dependencies: Topological Sort (Kahn's algorithm is BFS on in-degrees, but its goal is ordering, not distance).

Memory hack

Analogy: a rumour spreading through an office. At minute 0 only the source knows. Each minute, everyone who knows tells their direct neighbours. Ask "when does Alice first hear it?" and you are asking for her BFS level.

Say it out loud in the interview:

1. "State = ___, one move = ___, every move costs 1, so BFS gives the minimum."
2. "Queue the start(s), mark them visited when enqueued."
3. "Process level by level; return the level when I reach the goal, or -1 if the queue empties."

How it works

Process the queue in layers: record size = queue.size() at the start of a layer, pop exactly that many nodes, and push their unvisited neighbours. After the layer, increment steps.

Trace for Rotting Oranges on a 3×3 grid (2 rotten, 1 fresh, 0 empty), starting with one rotten orange at (0,0) and fresh oranges at (0,1), (1,0), (1,1), (2,2):

The queue empties while one orange (2,2) is still fresh and unreachable, so the answer is -1. If it had been reachable, the answer would be the last minute that rotted something.

Multi-source BFS (01 Matrix, Rotting Oranges) puts every source in the queue before the loop. Bidirectional BFS (a speed-up for Word Ladder) grows one frontier from each end and stops when they meet, shrinking the explored area dramatically. State-augmented BFS (Shortest Path in a Grid with Obstacles Elimination) makes visited three-dimensional.

Java template

import java.util.*;

class GraphBfs {
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    // Multi-source grid BFS: distance from the nearest source to every reachable cell.
    static int[][] distances(int[][] grid, int sourceValue, int wallValue) {
        int m = grid.length, n = grid[0].length;
        int[][] dist = new int[m][n];
        for (int[] row : dist) Arrays.fill(row, -1);    // -1 doubles as "not visited"
        Deque<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++)
                if (grid[r][c] == sourceValue) { dist[r][c] = 0; q.offer(new int[]{r, c}); }
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            for (int[] d : DIRS) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
                if (grid[nr][nc] == wallValue || dist[nr][nc] != -1) continue;
                dist[nr][nc] = dist[cur[0]][cur[1]] + 1;  // mark on enqueue
                q.offer(new int[]{nr, nc});
            }
        }
        return dist;
    }

    // Level-order BFS over an implicit state graph (e.g. words, lock codes).
    static int minSteps(String start, String goal, Set<String> blocked) {
        if (blocked.contains(start)) return -1;
        Deque<String> q = new ArrayDeque<>(List.of(start));
        Set<String> seen = new HashSet<>(List.of(start));
        for (int steps = 0; !q.isEmpty(); steps++) {
            for (int size = q.size(); size > 0; size--) {
                String cur = q.poll();
                if (cur.equals(goal)) return steps;
                for (String next : neighbours(cur)) {
                    if (!blocked.contains(next) && seen.add(next)) q.offer(next);
                }
            }
        }
        return -1;
    }

    private static List<String> neighbours(String s) {
        // problem-specific move generator; here: turn each digit wheel up or down by one
        List<String> out = new ArrayList<>();
        char[] a = s.toCharArray();
        for (int i = 0; i < a.length; i++) {
            char orig = a[i];
            a[i] = (char) ((orig - '0' + 1) % 10 + '0'); out.add(new String(a));
            a[i] = (char) ((orig - '0' + 9) % 10 + '0'); out.add(new String(a));
            a[i] = orig;
        }
        return out;
    }
}

Complexity

Variations

• Single-source shortest path: one start, stop at the goal. Example: Open the Lock.
• Multi-source BFS: seed all sources at level 0. Example: Rotting Oranges, 01 Matrix.
• State-augmented BFS: the node includes extra info such as remaining power-ups. Example: Shortest Path in a Grid with Obstacles Elimination.
• Graph of groups: BFS over routes instead of stops to count transfers. Example: Bus Routes.
• Bidirectional BFS: two frontiers meeting in the middle, always expanding the smaller one. Example: Word Ladder.
• 0-1 BFS: deque; push 0-cost edges to the front and 1-cost edges to the back.

Common mistakes

• Reading q.size() inside the loop condition while pushing, so levels blur together; capture the size first.
• Off-by-one on the answer: decide whether steps counts edges or nodes (Word Ladder counts words, so it is levels + 1).
• Forgetting the "impossible" case: return -1 when the queue empties, or when fresh cells remain.
• Using LinkedList with null entries or a Stack by mistake; ArrayDeque with offer/poll is the safe choice.
• In augmented states, keeping a 2D visited array, which wrongly blocks revisiting a cell with a better remaining budget.

All practice problems

6 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.