---
title: "Breadth-First Search"
description: "Graph traversal using queue"
source: https://vizlearn.app/algorithms/search/breadth-first-search
---

# 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

| Case | Time | Space |
|---|---|---|
| All | O(V + E) | O(V) |

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.)