Breadth-First Search

The 10-second versionCopy Anchor Link

Breadth-First Search explores a graph in expanding rings. Start at a vertex, visit all of its neighbours (ring one), then all of their unseen neighbours (ring two), and so on outward. A FIFO queue is what enforces that order: whatever you discovered first gets expanded first. And because you sweep outward in perfect layers, the first time you ever touch a vertex you've reached it by the fewest possible edges — BFS gives you unweighted shortest paths for free.

Why this existedCopy Anchor Link

Two very different people run into the same wall a few thousand miles apart.

Edward F. Moore, working on problems involving the paths of a robot through a network of nodes, needed the shortest route through a maze, not just some route. In his 1959 paper "The shortest path through a maze", he describes growing a frontier of reachable cells one step at a time — and the first time the frontier washes over the exit, you're standing on the shortest path. That's BFS.

Two years later, C.Y. Lee hit the same shape from an engineering angle. He was routing wires between pins on a circuit board — physical wires that can't cross and must be as short as possible — and published "An algorithm for path connections and its applications" in 1961. "Lee's algorithm" is a wavefront that spreads from a source across the free grid until it reaches the target. Same idea, same expanding rings, born again from wires instead of doorways.

Why did it matter then? Because "shortest" is the thing everyone actually wants. Before BFS, finding a route meant wandering (and possibly looping forever). After it, shortest-path search became a mechanical wave you could guarantee. The very same rings you'll write in ten lines of code today are still routing chips, mapping social graphs and crawling the web.

Inside the inventor's headCopy Anchor Link

The first instinct is embarrassingly simple, and it's wrong: "just look at every neighbour, then their neighbours, then theirs." Write it down and it's three lines — and it never stops:

// Naive: explore every neighbour and hope you stop. On any cycle, you never do.function explore(u, adj) {  for (const w of adj[u]) explore(w, adj);    // runs forever}// Improved: a FIFO queue plus a visited mark — each vertex enters exactly once.function bfs(src, adj) {  const visited = new Array(adj.length).fill(false);  const queue = [src];  visited[src] = true;                        // mark the moment you enqueue  for (let head = 0; head < queue.length; head++) {    const u = queue[head];    for (const w of adj[u]) {      if (!visited[w]) { visited[w] = true; queue.push(w); }    }  }}

On the graph from the last page, 0's neighbour 1 leads back to 0, which leads back to 1… you bounce between two vertices until the stack gives out. That's the trap: a graph can have cycles, and an explorer with no memory of where it's been will walk them forever.

So the first fix is a visited set. Mark a vertex so you never re-enter it. The second fix is subtler, and it's the actual invention: to get the layers, you need to expand vertices in the order you found them. A stack would dive; a queue spreads. Push the start, pop the front, enqueue its unseen neighbours, repeat.

Here's the pivot that makes it click. Watch the frontier move:

That middle branch is the real trap legions of people fall into: if you wait until dequeuing to mark a vertex visited, a vertex with three neighbours one step away gets enqueued three times, and the waste snowballs. Mark the moment you enqueue. It's one word different in the code and the difference between O(V + E) and a combinatorial explosion.

The final approachCopy Anchor Link

The algorithm, as a flowCopy Anchor Link

The invariants that make it correctCopy Anchor Link

1. FIFO means non-decreasing distance. If u is dequeued before v, then dist[u] ≤ dist[v]. The queue only ever holds vertices at distance d and d + 1 from the source — never more.
2. The first time you reach a vertex is via a shortest path. Every vertex is discovered from a vertex one ring closer to the source, so its recorded distance is minimal.
3. Each vertex is enqueued at most once. We mark on enqueue, so a vertex can never be added twice. That's what keeps the total work proportional to the edges.
4. dist is final once set. Nothing later in the run can shorten an already-assigned distance, because everything still in the queue is the same distance or farther.

A worked traceCopy Anchor Link

Run BFS from vertex 0 on the graph we stored last page (0:[1,2], 1:[0,2], 2:[0,1,3], 3:[2,4], 4:[3]):

Final distances: dist = [0, 1, 1, 2, 3]. Vertex 4 is three edges away, and BFS proved that by reaching it only after exhausting everything at distance 0, 1 and 2. No other route to 4 could be shorter — it would have to come from ring 2, and ring 2 was fully drained first.

It in codeCopy Anchor Link

The full version also records a parent pointer for every vertex, which lets you rebuild the actual shortest path, not just its length:

// adj is an array of neighbour arrays.function bfs(src, adj) {  const dist = new Array(adj.length).fill(-1);   // -1 == unreached  const parent = new Array(adj.length).fill(-1);  const queue = [src];  dist[src] = 0;  for (let head = 0; head < queue.length; head++) { // head pointer == dequeue    const u = queue[head];    for (const w of adj[u]) {      if (dist[w] === -1) {                    // first time we've seen w        dist[w] = dist[u] + 1;        parent[w] = u;        queue.push(w);                         // mark + enqueue together      }    }  }  return { dist, parent };}

Cost tableCopy Anchor Link

There's no "best case" that's faster: BFS touches every reachable vertex once and every edge of a reachable vertex once, so it is always O(V + E) on a list (worst, average and best alike). The O(V) space is the queue plus the dist and parent arrays.

Where you meet it todayCopy Anchor Link

• Degrees of separation. "How are these two people connected?" is a BFS on the social graph — and because BFS is layered, the layer number is the number of hops.
• Crawlers and flood fills. A web crawler starts from seed pages and expands outward ring by ring; a paint-bucket fill in an image editor is the same wave restricted to one colour.
• Grid pathfinding. Games and robotics use BFS (and its weighted cousin, Dijkstra) to find the shortest route through a map of open cells and walls.
• Garbage collection. The "mark" phase of a tracing collector is a breadth-ish traversal of the object graph, following references from the roots.

The grid case is the one you'll write most often. Here's a real shortest-path-in-a-maze — four moves, 1 is a wall:

// Minimum steps from (0,0) to (R-1,C-1); 1 = wall, 0 = open. -1 if unreachable.function minSteps(g) {  const R = g.length, C = g[0].length;  const dist = g.map((row) => row.map(() => -1));  if (g[0][0]) return -1;  const queue = [[0, 0]];  dist[0][0] = 0;  const dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]];  for (let head = 0; head < queue.length; head++) {  // index pointer == dequeue    const [r, c] = queue[head];    for (const [dr, dc] of dirs) {      const nr = r + dr, nc = c + dc;      if (nr >= 0 && nr < R && nc >= 0 && nc < C && !g[nr][nc] && dist[nr][nc] === -1) {        dist[nr][nc] = dist[r][c] + 1;        queue.push([nr, nc]);      }    }  }  return dist[R - 1][C - 1];}

Swap the four-way move loop for the graph's neighbour list and it's the exact same algorithm. That's the beautiful thing: a grid is a graph, and BFS doesn't care which one it's walking.

RecapCopy Anchor Link

• BFS explores in expanding rings, using a FIFO queue to enforce the order.
• The queue guarantees the first time you reach a vertex is via the fewest edges — BFS is your unweighted shortest-path tool.
• Always keep a visited set, and mark a vertex the moment you enqueue it — not when you dequeue — or the frontier blows up.
• Cost is O(V + E) on an adjacency list (O(V²) on a matrix), with O(V) extra space.
• A grid is just a graph with four (or eight) neighbours per cell; the same code solves mazes.

Next up: Depth-First Search — the other half of the story: instead of spreading out, dive all the way in.