What is breadth-first search?
Breadth-first search explores a graph level by level from a starting point, using a queue — first in,
first out — instead of a stack. Every node one step away gets visited before any node two steps away, and that
strict ordering is what makes the algorithm reliable: the first time you reach a node is guaranteed to be by the
shortest possible route, as long as every edge counts the same.
- Queue
- A first-in, first-out list — nodes are explored in the same order they were added
- Frontier
- The ring of nodes currently one step further out than everything already visited
- Level
- How many edges a node sits from the start — visited in order, 0, 1, 2, …
Why breadth-first search at all?
Drop a stone in a pond. The ripple doesn't teleport to the far edge — it reaches every point one inch away before it touches anything two inches away, spreading outward in even rings.
A queue gives an algorithm the same discipline: process everything at the current distance before moving on to the next distance. That's the whole trick, and it's why the first arrival at any node is provably the shortest way to reach it.
Every ring finishes lighting up before the next one starts — never out of order.
What kinds of problems does it solve?
Four shapes come up constantly. The queue never changes — only what counts as a "neighbor" and how many places the queue starts from does.
Shortest path around obstacles
Starting from one corner of a grid, expand ring by ring. Walls just get skipped as neighbors — the first ring to reach the target is, by construction, the shortest route around them.
The wall is never a neighbor — the ring just routes around it.
Level order traversal
On a tree, "distance from the root" is exactly "which level a node sits on". A queue visits a whole level before touching the next one, so the visit order falls out for free.
The whole level empties out of the queue before the next one goes in.
Nearest of several starting points
Seed the queue with every source at once — two gates, two rotten oranges, whatever counts as a start. The ring that reaches a cell first is, automatically, its nearest source.
Cells on the seam are equally close to both sources.
Reachability and connected regions
Run the ripple from one cell and see how far it spreads. Anything the ripple never touches — sealed off by walls — isn't part of the same connected region at all.
The corner cell never lights up — it's walled off from the source.
Two types
The mechanics never change — a queue, a visited set, one ring at a time. The only real choice is how many nodes seed that queue before the first ring even starts.
Single-source
The queue starts with exactly one node at distance 0. Every ring after that is strictly farther away, so the distance map you build is the shortest distance from that one starting point.
One source in, one ring at a time out.
function bfs(graph: Map, start: string): Map {
const dist = new Map([[start, 0]]);
const queue = [start]; // seeded with exactly one node
while (queue.length > 0) {
const node = queue.shift()!; // dequeue — FIFO
for (const neighbor of graph.get(node) ?? []) {
if (!dist.has(neighbor)) {
dist.set(neighbor, dist.get(node)! + 1);
queue.push(neighbor); // enqueue, one ring farther out
}
}
}
return dist;
}
Multi-source
Seed the queue with every source at distance 0, all at once, before the loop even starts. The rings still expand one at a time — but now every cell's distance is to whichever source reaches it first.
Both sources ride in the same queue — one pass, not two separate searches.
function nearestSource(grid: number[][], sources: [number, number][]): number[][] {
const dist: number[][] = grid.map((row) => row.map(() => -1));
const queue: [number, number][] = [];
for (const [r, c] of sources) {
dist[r][c] = 0;
queue.push([r, c]); // every source enqueued before ring 0 even runs
}
while (queue.length > 0) {
const [r, c] = queue.shift()!;
for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const nr = r + dr;
const nc = c + dc;
if (grid[nr]?.[nc] !== undefined && dist[nr][nc] === -1) {
dist[nr][nc] = dist[r][c] + 1;
queue.push([nr, nc]);
}
}
}
return dist; // distance to the nearest source, from anywhere
}
Where it works — and where it breaks
Breadth-first search leans on one quiet assumption: every edge costs the same to cross. Counting hops only tells you the truth about distance when hops themselves are the thing you care about.
Works when every edge weighs the same
On an unweighted grid, the ring that first reaches a cell used the fewest possible hops to get there — and fewest hops is exactly what "shortest path" means here.
Breaks when edges have different weights
"Fewest hops" and "cheapest total" stop being the same thing the moment edges carry different costs. BFS can report a 2-hop route as the winner while a 3-hop route is actually far cheaper.