Breadth-first search

The problem it solves

You have a network of things — web pages and links, people and friendships, rooms and doors, states of a puzzle and legal moves — and a starting point. Two questions come up constantly: what can I reach from here? and what is the fewest number of steps to reach it? Breadth-first search answers both at once, and it answers the second one with a guarantee: the first time BFS touches a node, it has found a shortest route to it, and no amount of further searching will find a shorter one.

That guarantee is why BFS shows up in places that don’t look like graph problems at all. “Fewest moves to solve this puzzle” is BFS over puzzle states. “Degrees of separation between two people” is BFS over a social graph. “Shortest escape route through a maze” is BFS over grid cells. If every step costs the same, BFS is the shortest-path algorithm — Dijkstra and friends only earn their complexity when steps cost different amounts.

The intuition — and where it breaks down

Drop a stone into still water and watch the rings spread. The wavefront reaches everything one metre away before anything two metres away, everything two metres away before anything at three. BFS is that wavefront made discrete: it visits everything one edge from the start, then everything two edges away, then three, each ring complete before the next begins.

The mechanism that enforces the rings is embarrassingly small: a queue. When you discover a node, you put it at the back of the line. When you need the next node to explore, you take from the front. First discovered, first explored — and since nearer nodes are discovered before farther ones, nearer nodes are explored before farther ones. The queue is the algorithm; everything else is bookkeeping.

Here is where the ripple analogy breaks, and it matters: water spreads through continuous space in all directions at once, but BFS only moves along edges, and it processes one node at a time. More importantly, a real ripple weakens with distance — BFS does not. The tenth ring is explored as thoroughly as the first. And if two ripples meet, they interfere; when two BFS frontiers would “meet” (a node reachable two ways), the visited set simply ignores the second arrival. The analogy sells the ordering, not the mechanics.

Loading…

A walkthrough you can check

Take a small graph: A connected to B and C; B connected to D; C connected to D; D connected to E. Start at A.

1. A enters the queue with distance 0. Queue: [A].
2. Dequeue A. Its neighbours B and C are undiscovered: label both distance 1, enqueue both. Queue: [B, C].
3. Dequeue B — it has waited longest. Its neighbour D is new: distance 2, enqueued. Its neighbour A is already labelled — that edge is rejected. Queue: [C, D].
4. Dequeue C. Its neighbour D already carries distance 2 — rejected. This is the moment worth staring at: C also reaches D, but too late, and BFS simply shrugs. Queue: [D].
5. Dequeue D. Neighbour E is new: distance 3. Queue: [E].
6. Dequeue E. No new neighbours. Queue empty — done.

Every label is the fewest edges from A, and the rejected edges are not waste: each one is a proof that a shorter route already existed. Run the visualization above on the default input and count the rejections — a connected graph with E edges and V nodes rejects exactly E − (V − 1) of them, because only a spanning tree’s worth of edges can ever be “first”.

The invariant

At any pause point, this is true: the queue contains exactly the discovered-but-unexplored frontier, and it never holds two nodes whose distances differ by more than one. All nodes at distance less than the front of the queue are completely explored.

That second clause is the whole shortest-path proof. When a node n is dequeued with label d, every possible discoverer of n at distance less than d − 1 has already been explored — so if a shorter route existed, n would already be labelled. Interviewers rarely ask you to recite this; they ask questions whose answers fall out of it, like “why can’t a later edge improve a BFS distance?” (because improvement would require a discoverer closer than d − 1, and those are all finished).

Complexity, derived

Count what actually happens rather than quoting the formula. Every node enters the queue at most once (the visited check guarantees it), and each entry costs one enqueue and one dequeue: that is O(V). When a node is dequeued, the algorithm inspects each of its edges once; over the whole run every edge is inspected once per endpoint, which is at most twice: O(E). Total: O(V + E), and the counters panel in the visualization shows you both numbers live — nodes visited and edges inspected — so the claim is checkable, not folklore.

Space is the queue plus the visited set: O(V). The queue’s peak size is the widest ring, which on bushy graphs can be a large fraction of V — that is the practical cost people forget, and it is why bidirectional BFS (searching from both ends and meeting in the middle) can save enormous memory on big graphs: two shallow frontiers are far smaller than one deep one.

What people get wrong

“Mark nodes visited when you dequeue them.” No — mark on enqueue. If you wait until dequeue, a node sitting in the queue can be discovered again by another edge and enqueued a second time. The algorithm still terminates and still produces correct distances, but the queue bloats and the complexity analysis quietly breaks. This is the single most common BFS bug, and the prediction prompts in the visualization above ask about exactly this moment.

“BFS works on weighted graphs if I just… “ It does not, and no small patch fixes it. BFS counts edges; a two-edge path of weights 1+1 beats a one-edge path of weight 10, but BFS will label via the one-edge path first. The exception worth knowing: if weights are only 0 and 1, a deque (0-weight edges push to the front) preserves the ordering invariant — that’s 0-1 BFS, a genuinely useful trick.

“DFS would find the same thing with less memory.” DFS finds a path, not a shortest one, and on this point the two algorithms are not interchangeable no matter how the code is arranged.

Implementation notes across languages

The pitfalls are language-specific in an unglamorous way. In Python, list.pop(0) is O(n) — use collections.deque and popleft(), or your “linear” BFS is quadratic. In JavaScript, Array.prototype.shift() has the same problem on very large queues; an index-into-array queue (queue[head++]) fixes it without a library. In Java, use ArrayDeque, not LinkedList, for the queue — same interface, far better constants — and remember poll() returns null on empty where remove() throws. In all three, the visited structure should be a set or boolean array keyed by node id, never a list you contains() against.