Breadth-First Search

BFS visits exactly the same nodes as DFS, costs the same, and is barely longer to write. It earns its own article for one reason: it visits them in order of distance, and that ordering is a guarantee DFS cannot offer at any price.

The moment a problem asks for the fewest steps, the shortest path, or anything measured in levels, BFS is the answer and DFS is not.

Why the first visit is the shortest one#

Swap the stack for a queue and the traversal turns inside out. A stack always hands back the most recent discovery, so DFS plunges. A queue hands back the oldest, so nothing at distance 2 is examined until everything at distance 1 has been.

That gives the invariant the whole technique rests on:

The queue only ever holds nodes at distance d and d+1, in that order.

From which the useful consequence follows immediately: the first time you reach a node, you have reached it by a shortest path. Any shorter route would have arrived on an earlier level, and every earlier level has already been fully drained. There is nothing left to improve, which is why BFS never revisits and never needs to compare two candidate distances.

Note the condition hiding in that argument: it counts steps, so every edge has to be worth the same. The moment edges carry different weights the guarantee evaporates — see below.

Watch the shape of the highlighted frontier rather than the individual cells. It is always a ring at one constant distance, and it bends around the walls without ever doubling back. Each step drains one ring and paints the next, so the number written into a cell is the step on which it was first reached — and therefore its shortest distance.

The template#

queue = [start]
visited = {start}                 // marked as it is ENQUEUED

while queue is not empty:
    node = pop_front(queue)
    process node

    for next in neighbours(node):
        if next not in visited:
            add next to visited   // here, not when it is popped
            push_back(queue, next)

The cost is O(V + E), the same as DFS: every node enters the queue once and every edge is examined once from each end.

The interactive BFS snippet builds this traversal line by line in Go over an adjacency list, and calls out the enqueue-time marking in the code itself. Its sibling, the DFS snippet, is the same walk with the queue replaced by recursion — worth reading side by side once.

Mark on enqueue, not on dequeue#

This is the bug, and it is worth its own heading because the code still produces the right answer. If you mark nodes only as they come off the queue, a node with five discovered neighbours gets pushed five times before any of those copies is popped. The traversal is still correct; the queue is now holding O(E) entries instead of O(V), and on a dense graph that is the difference between passing and timing out.

Mark it as it goes in, and every node is queued exactly once.

Use a real queue#

Popping from the front of an array is O(n) in most languages, which quietly turns an O(V + E) traversal into O(V²). Use the deque or linked-queue type your language provides — Python’s collections.deque, Java’s ArrayDeque, C++’s std::queue. In Go, the idiomatic queue = queue[1:] reslice is fine, because it moves the header rather than the elements.

Counting levels#

Plain BFS tells you the order but not the depth. When you need the level number — how many steps, or which nodes share a row — process the queue one whole level at a time by measuring it before you start:

level = 0

while queue is not empty:
    n = size(queue)               // freeze it: the queue grows inside this loop

    repeat n times:
        node = pop_front(queue)
        ...push this node's undiscovered neighbours...

    level = level + 1             // one full ring done

Capturing n before the inner loop is the entire trick, and reading size(queue) inside the loop instead is the entire bug — the loop would run into the next level and the count would be meaningless.

This is the shape behind most of the tree problems here. Level Order Traversal collects each ring into its own list. Right Side View keeps the last node of each ring, which is one line’s difference. And any “minimum number of moves” problem returns level at the moment it first sees the target.

Multi-source BFS#

Here is the trick that makes several Medium problems fall over: the queue can start with more than one node in it.

Seed it with every source, all at distance 0, and the frontier expands from all of them simultaneously. Each cell is still reached first by whichever source is nearest, so what you compute in one pass is the distance to the closest source.

queue = every source cell
visited = every source cell           // all at distance 0

...then the ordinary loop, unchanged...

Nothing else changes — and that is the point. Rotting Oranges seeds the queue with every already-rotten orange and counts levels until the queue empties; 01 Matrix seeds it with every zero and lets the distances fall out. Both look like they need a separate search per source, which would be O(V²), and neither does.

The way to see why it is legitimate: imagine one virtual node joined to every source by a zero-cost edge. Multi-source BFS is ordinary BFS from that node, with the first level skipped.

Implicit graphs#

Not every graph arrives as an adjacency list. Often the nodes are states and the edges are moves, and no graph is ever built — you generate neighbours on demand.

Word Ladder is the standard example: each node is a word, and two words are adjacent when they differ in exactly one letter. Comparing every pair of words to find the edges is O(n²·L). The better move is to key on the shape: bucket every word under each of its wildcard patterns — h*t, *ot, ho* — so a word’s neighbours are whatever shares one of its buckets. That reduction is the real problem; the BFS around it is the template above, counting levels.

The lesson generalises. When a problem talks about reaching a target through single moves — transformations, jumps, states of a puzzle — you are almost certainly looking at an unweighted shortest-path problem in disguise, and the work is in defining “neighbour”, not in the search.

When BFS stops working#

The distance guarantee is exactly as strong as the assumption that every edge costs one.

• Weighted edges break it, because a two-edge route can be cheaper than a one-edge route. What you want then is Dijkstra — the same traversal with a min-heap instead of a queue, so the next node examined is the nearest rather than the oldest.
• Weights of only 0 and 1 are the interesting middle case: a deque, pushing 0-cost moves to the front and 1-cost moves to the back, keeps the queue sorted without the heap.

There is one more BFS in the family that is not about distance at all. Kahn’s algorithm for topological sort runs a queue over a dependency graph, seeded with everything that has no prerequisites, releasing each node as its last prerequisite is met. Course Schedule is that algorithm, and its cycle test is simply whether the ordering came out shorter than the node count — nodes stuck in a cycle never reach zero prerequisites and never get queued.

Cost, and the memory trade#

Time is O(V + E) either way, so the choice between BFS and DFS is about the guarantee and the memory.

DFS holds one root-to-node path: O(h). BFS holds an entire level: O(w), the maximum width. On a balanced binary tree that is the difference between O(log n) and O(n/2), and it points both ways — a deep, narrow structure is cheap for BFS and a stack-overflow risk for DFS; a shallow, wide one is the reverse.

So the decision is:

• Shortest path, fewest moves, level numbers → BFS, and there is no argument to have.
• Reachability, connectivity, aggregating over subtrees, exploring every possibility → DFS, which is shorter to write and usually lighter.

Recognising it#

Reach for BFS when:

• The problem says shortest, fewest, minimum number of steps, or nearest — on unweighted edges.
• The answer is organised by level: per-row output, the last node of each row, how many rounds until something finishes.
• Something spreads outward from one or more starting points — infection, rot, water, signal. That is multi-source BFS almost by definition.
• The state space is implicit, and each move costs the same. Puzzles, word transformations, and jump games all fit.

And the check before you commit to it: are all the edges really worth the same? If not, you want a heap, not a queue.

Summary#

One structural change — a queue instead of a stack — buys an ordering guarantee: nodes come out nearest-first, so the first arrival at any node is its shortest path. Everything else is consequence. Mark nodes as they enter the queue so each is enqueued once; freeze the queue length when you need level numbers; seed the queue with every source when distance to the nearest is what you want. And when edges stop costing the same, hand the queue over to a heap.