Breadth-First Search

Breadth-first search (BFS) is a graph traversal algorithm that visits nodes in order of increasing distance from a start node, using a FIFO queue to process the closest unvisited frontier first. Because the first arrival at any node travels a minimum number of edges, BFS computes shortest paths in unweighted graphs in O(V + E) time.

Drop a stone in a still pond. The ripple reaches everything one ring out, then everything two rings out, and it never skips ahead — no point at distance three gets wet before every point at distance two. BFS is that ripple, and the queue is what enforces the physics: discoveries join the back, the next node to process comes off the front, so the wave can't outrun itself.

How Breadth-First Search Works

The whole algorithm is one loop over a queue:

1. Enqueue the start node, mark it visited, set its distance to 0.
2. While the queue is non-empty, dequeue the front node and scan its neighbours. Each unvisited neighbour gets marked, assigned distance current + 1, and pushed onto the back.

The load-bearing detail hides in step 2: mark a node visited the instant you enqueue it, not when you later dequeue it. Wait until dequeue and the same node can be discovered by several neighbours and pushed several times — duplicated work and, worse, corrupted distances. The animated graph-mode code puts visited.add(nb) right beside the append, inside the if nb not in visited block, for exactly this reason.

This lesson runs in two modes. In Tree mode there is exactly one path to every node, so reconvergence is impossible — and the animated tree code honestly drops the visited set altogether, leaving a four-line loop of dequeue-and-push-children. In Graph mode edges may reconverge or form cycles, and the visited set returns as the guard. An edge that points at an already-discovered node is skipped, because the node already holds a distance from an earlier — hence equal-or-shorter — path. It is a back edge when the target is an ancestor of the current node in the BFS tree, and a cross edge otherwise.

The "closest first" discipline buys the headline guarantee. Nodes leave the queue in non-decreasing distance order, so the first edge to reach a node is the final word on its shortest distance. In an unweighted graph, BFS is the shortest-path algorithm.

Breadth-First Search Step by Step

The default configuration is Graph mode, Simple preset, starting at node 0: a 7-node graph where two paths converge on node 5 — 0 → [1, 2], 1 → [3, 4], 2 → [5], 4 → [5], 5 → [6], and 3 and 6 are leaves. That reconvergence is the point: it is where the visited set turns a second arrival into a cross edge instead of duplicated work.

1. Enqueue 0 — mark it, d = 0. Queue: [0].
2. Dequeue 0 — 0 → 1 and 0 → 2 are both unvisited: enqueue each at d = 1. Queue: [1, 2] — level 1, complete, before any level-2 node exists.
3. Dequeue 1 — 1 → 3 and 1 → 4 enqueued at d = 2. Queue: [2, 3, 4].
4. Dequeue 2 — 2 → 5 is unvisited: enqueue 5 at d = 2. This is 5's first arrival, so 2 is its parent and d(5) = 2 is final. Queue: [3, 4, 5].
5. Dequeue 3 — a leaf, nothing to push. Queue: [4, 5].
6. Dequeue 4 — checks 4 → 5, but 5 is already discovered. This is the moment the lesson exists for: 4 → 5 is a cross edge, skipped, no enqueue. 4 reached 5 by a path no shorter than 2's, so BFS has nothing to learn from it. Queue: [5].
7. Dequeue 5 — 5 → 6 enqueued at d = 3. Queue: [6]. Dequeue 6 — a leaf, and the queue drains to empty.

Visit order: 0, 1, 2, 3, 4, 5, 6, distances 0 / 1, 1 / 2, 2, 2 / 3. The order reads like plain level order, but step 6 is the whole difference between a tree and a graph: node 5 had two ways in, BFS took the first and the visited set turned the second into a skipped cross edge. Delete that guard and 4 → 5 re-enqueues 5 with a corrupted second distance.

The other presets move the emphasis. Tree mode (Balanced) removes reconvergence — one path per node, no cross edges, the queue mechanics alone: 0, 1, 2, 3, 4, 5, 6 in clean level order on the complete binary tree, the exact contrast to depth-first search's 0, 1, 3, 4, 2, 5, 6 plunge down the same shape. The graph Cyclic preset goes the other way: every cycle-closing edge lands on an already-discovered node and is skipped, so the visited set is the only thing between you and an infinite queue. From node 0, 2 → 0 points back at 2's own ancestor — a back edge — while 2 → 4, 4 → 5 and 5 → 1 are cross edges. Reach for those to isolate the queue from the skipped-edge handling; the default shows both at once.

On the canvas, the queue is the bottom strip: chips slide in at the back on every enqueue and out at the front on every dequeue, while a focus ring lands on whichever node was just popped. Nodes wear their state — faint blue while unreached, orange once discovered and waiting in the queue, green once fully scanned — and each carries its d= label, so you can watch the green wave sweep outward one distance ring at a time; a skipped back or cross edge flashes red as the scan rejects it.

Time and Space Complexity

Each vertex is enqueued and dequeued exactly once (mark-on-enqueue is what makes "exactly" true); each edge is examined once. Space is the queue plus the visited set. At any moment the queue holds at most two adjacent levels — what is left of the current one plus the part of the next one found so far — so its peak tracks the graph's width. For a bushy graph that can be a large fraction of all vertices at once, which is precisely where DFS's stack stays shallow. The two containers grow in opposite dimensions; the visited set costs O(V) in both.

Edge Cases

• Single node, no edges — enqueue it, dequeue it, find nothing, done.
• Unreachable nodes — BFS reaches only the nodes the start can reach along directed edges (in an undirected graph, its connected component); everything else stays unvisited. Covering the whole graph means restarting from each still-unvisited node.
• Cycles — every cycle-closing edge hits a discovered node and is skipped, as a back edge if its target is an ancestor and a cross edge otherwise; the queue cannot grow forever.
• Wide versus deep input — a broad frontier bloats the queue; a long chain barely fills it. Mirror-image of DFS's cost profile.

Common Mistakes

1. Marking visited on dequeue instead of enqueue. The same node gets pushed by several neighbours before it is ever processed — wasted work and wrong distances. Mark it the instant it enters the queue.
2. Reaching for BFS on a weighted graph. BFS counts edges, so its "shortest path" only holds when every edge costs the same. Varying weights call for Dijkstra's algorithm.
3. Swapping the queue for a stack and not noticing. That one substitution literally turns BFS into DFS — the container is the algorithm. If your traversal mysteriously dives instead of rippling, check what pop means in your language's library.
4. Dropping the visited set in graph mode. Any cycle then re-enqueues the same nodes endlessly. (Only a genuine tree earns the four-line version without it.)