BFS in layers — how I see graph problems.

I've seen students learn BFS as a queue algorithm — push neighbors, mark visited, repeat. That's not wrong, but it's like learning chess by memorizing how each piece moves without thinking about why. You can execute it, but you can't adapt when the board looks unfamiliar.

The frame I use instead: BFS is a machine that produces layers. Layer 0 is where you start. Layer k+1 is everything you can reach from layer k in one step that you haven't seen before. The queue is just the mechanism; the layers are the idea. Once that clicks, about 60% of graph problems resolve into BFS variants you can actually construct.

What does layer k mean?

Plain unweighted shortest path first. You have a graph, a source, and you want the minimum number of edges to reach each vertex. The standard explanation is "BFS gives shortest paths because it explores nodes in order of distance." That's true but passive — it doesn't tell you how to use it.

Active version: layer k contains exactly the vertices reachable from the source in k steps and no fewer. When you pop a vertex from the queue, its distance is finalized. Every neighbor you haven't visited yet belongs to layer k+1. You're not just finding distances — you're partitioning the graph into concentric shells.

This matters because the moment you describe a problem as "what's the minimum number of steps to get from state A to state B?", BFS is your answer, and the layer structure tells you the answer is the layer number where B first appears.

Multi-source BFS

Now suppose you don't have one source — you have many. Fire spreading through a grid, oranges rotting, guards in a maze broadcasting their influence. You want the minimum distance from any source to each cell.

Students often try to run BFS from each source separately and take the minimum. That works but it's O(sources × V) when it could be O(V + E). The fix is elegant: seed the queue with all sources at distance 0 simultaneously. Layer 0 is now the entire set of sources. Layer 1 is everything adjacent to any source. The BFS proceeds identically.

// Multi-source BFS — all sources start at distance 0
queue<pair<int,int>> q;
vector<vector<int>> dist(rows, vector<int>(cols, -1));

for (auto [r, c] : sources) {
    dist[r][c] = 0;
    q.push({r, c});
}

while (!q.empty()) {
    auto [r, c] = q.front(); q.pop();
    for (auto [dr, dc] : directions) {
        int nr = r + dr, nc = c + dc;
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
        if (dist[nr][nc] != -1) continue;
        dist[nr][nc] = dist[r][c] + 1;
        q.push({nr, nc});
    }
}

The key insight: you're not doing multiple BFS runs. You're doing one BFS where layer 0 happens to contain multiple nodes. The abstraction holds — layer k still means "minimum distance k from any source". The code is identical to single-source BFS; only the initialization changes.

My students rarely meet this technique under its textbook name. In my group it goes by Pizza-BFS — named after one of my signature tasks — and once you’ve solved that one, seeding the queue with every source at distance 0 stops being a trick and becomes a reflex.

Adam once spent a long time on a grid problem where a zombie infection spread from several initial cells. He wrote a loop over infected cells and ran BFS from each. Correct answer, time limit exceeded. We rewrote the initialization in five minutes.

0-1 BFS and when layers break

Standard BFS assumes every edge has equal weight — that's what makes the layer structure work. If you add edges with weight 0 and weight 1, the layers start to fray: moving along a 0-cost edge shouldn't advance your layer number.

0-1 BFS handles this with a deque instead of a queue. Zero-cost edges push to the front (same layer); one-cost edges push to the back (next layer). The layer structure is preserved — you're just being more careful about which transitions advance the layer counter.

I mention this here not to teach 0-1 BFS fully, but to show that the layer frame predicts when standard BFS needs adjustment. If your edge costs break the "each step costs 1" assumption, you need to modify the mechanism. Dijkstra is the general case; 0-1 BFS is the efficient special case. The layer intuition tells you why each exists.

BFS on implicit state graphs

This is where the frame really earns its keep. A lot of olympiad problems aren't stated as graph problems at all — they're puzzles, simulations, combinatorial searches. But they have an implicit graph structure: states are nodes, valid moves are edges, and you want the minimum number of moves.

Knight moves on a chessboard. Sliding tile puzzles. Flipping switches where each switch affects neighbors. Word ladders. The graph is never drawn — you generate it on the fly during BFS.

The question to ask is always: what is one state? For knight moves, it's a board position. For a switch puzzle, it's the current configuration of all switches. For a sliding puzzle, it's the entire board layout (careful with N — state space blows up fast).

When you can describe what one BFS layer means in your problem's language — "all board configurations reachable in exactly k moves", "all switch configurations reachable with k flips" — the code writes itself. You're not doing graph BFS. You're doing state-space BFS, and it's the same algorithm.

Tomek was stuck on a problem where you flip a bit in a binary string and all adjacent bits also flip, and you want the minimum flips to reach a target. He kept trying to find a greedy pattern. I asked him: "what's a state?" He said "the current string." I asked "what's a transition?" He said "flip position i, which changes bits i-1, i, i+1." Then he paused and wrote BFS. Eleven minutes later he had AC.

The layer checklist

When I encounter a problem and I'm deciding whether BFS applies, I run through this:

1. What is a state? Can I represent it compactly enough that I can put it in a queue and use it as a map key?
2. What is a transition? Given a state, what states can I reach in one "step"?
3. What does one layer mean? "All states reachable in exactly k steps" — does that sentence make sense for my problem?
4. Do I have multiple starting states? If yes, seed the queue with all of them at distance 0.
5. Are all transitions equal-cost? If no, consider 0-1 BFS or Dijkstra.

If I can answer questions 1-3 cleanly, I'm writing BFS. The rest is mechanics.

The reason I teach BFS as layers rather than as a queue algorithm is that the queue is an implementation detail. Students who understand layers can reconstruct BFS from scratch if they forget the exact code. Students who memorized the queue pattern are stuck when the problem doesn't look like the template.

For OI preparation specifically: the problems that use BFS on implicit state graphs show up regularly in the first two rounds — they're hard enough to filter students who can only solve textbook graphs, but they're completely tractable if you've internalized the layer model. Get comfortable with the question "what is one state in this problem?" and you'll find graph problems stop feeling like a separate category.