Breadth-First Search (BFS)
Explore a graph in expanding rings from the start — the first time you reach a node is provably the shortest unweighted path to it.
Hands on Interactive visualization
Implementation Code
export function bfs(
adj: Map<number, number[]>,
start: number,
target: number,
): number {
const visited = new Set<number>([start]); // mark on enqueue
let frontier = [start];
let dist = 0;
while (frontier.length > 0) {
const next: number[] = [];
for (const node of frontier) {
if (node === target) return dist;
for (const nb of adj.get(node) ?? []) {
if (!visited.has(nb)) {
visited.add(nb); // enqueue-time marking
next.push(nb);
}
}
}
frontier = next; // advance one ring outward
dist++;
}
return -1;
}Big-O Complexity
Every vertex is enqueued once and every edge examined once (twice for undirected graphs). Space is the queue plus the visited set — the queue can hold an entire frontier, up to O(V) on wide graphs.
In production When to use
When every edge costs the same, BFS finds the minimum-hop path by construction — routing hops in a network, fewest moves in a puzzle, minimum edits in a word ladder. No Dijkstra needed.
Social graphs answer how far apart are these two people? with BFS — friend suggestions, LinkedIn's 2nd/3rd-degree labels, and six-degrees analyses are all frontier-by-frontier expansions.
Crawlers seed a queue with start URLs and expand outward level by level, which naturally prioritizes pages closer to the seeds and keeps a visited set to avoid re-fetching.
Tracing collectors mark live objects by traversing references from the roots; Cheney's copying-collector algorithm is literally a BFS whose queue is the to-space being filled.
Printing a tree level by level, computing per-depth aggregates, or finding the minimum depth are BFS on a tree — the queue boundary is the level boundary.
Paint-bucket fill, counting islands in a grid, and connected-component labeling treat grid cells as vertices with 4- or 8-neighbor edges and BFS from each unvisited seed.
Trade-offs Strengths & weaknesses
- Guarantees the shortest path in edge count — the first arrival at a node is optimal.
- Visits nodes in order of distance, so it can stop early at a target depth.
- Iterative by nature: no recursion, no stack-overflow risk on huge graphs.
- O(V + E) is optimal — every search that may need the whole graph must touch it once.
- Distances and parent pointers fall out for free, reconstructing the actual path.
- O(V) queue memory — on wide, bushy graphs the frontier can dwarf DFS's path-depth stack.
- Shortest-path guarantee holds only for unweighted (or uniform-weight) graphs.
- Needs the visited set from the very first step, or cycles loop it forever.
- Poor fit for deep, narrow searches where the target is far from the start — it exhaustively fills every closer ring first.
- Cache-unfriendly on pointer-based graphs: frontier nodes are scattered across memory.
Intuition Mental model
Ripples in a pond
Drop a stone in still water: rings spread outward, each ring one step farther than the last, and no point is wetted by a later ring before an earlier one reaches it. BFS is that wavefront — the queue holds the current ring, and distance is just which ring got there first.
- The stone hits the water = start node enqueued at distance 0.
- The first ring = all direct neighbors, discovered together at distance 1.
- Each ring expands only from the previous ring's edge = dequeue a node, enqueue its unseen neighbors at distance +1.
- Water already disturbed doesn't ripple again = the visited set, marked when the wave first touches it.
- The ring number when the wave hits your target = the shortest hop count, guaranteed, because no later ring can arrive earlier.
Prep Interview questions
Why does BFS find the shortest path in an unweighted graph? Prove it.
Word Ladder: transform 'hit' to 'cog' one letter at a time through a dictionary. Why BFS?
Rotting oranges / multi-source BFS: minutes until all oranges rot. What changes?
When do you need Dijkstra or 0-1 BFS instead of plain BFS?
BFS vs DFS: how do you choose in an interview?
Watch out Common bugs
If a node is only marked when popped, it can be pushed multiple times by different neighbors before its first pop — the queue balloons (up to O(E) entries) and work is duplicated. Mark visited at the moment of enqueue, so each vertex enters the queue exactly once.
On any graph with a cycle (or just an undirected edge, which is a 2-cycle), the traversal revisits nodes forever. Trees are the only structure that forgives this — and interviewers know it.
BFS counts hops, not weight. A 2-hop path of cost 100 will be found before a 3-hop path of cost 3. Weighted shortest paths need Dijkstra (or 0-1 BFS / Bellman-Ford as appropriate).
Popping from the wrong end silently turns BFS into DFS — traversal still terminates, so the bug surfaces only as wrong distances. In Python, use collections.deque.popleft(), never list.pop(0), which is O(n) per dequeue.
One screen Cheat sheet
Queue + visited set: explore in rings, mark on enqueue, first arrival = shortest unweighted path.
- Queue (FIFO) drives the level-by-level order — swap in a stack and you have DFS.
- Mark visited when you ENQUEUE, not when you dequeue.
- First arrival at a node is the shortest path in edge count — unweighted graphs only.
- Track parent pointers to reconstruct the path, or a depth counter per frontier.
- Multi-source BFS: seed the queue with several starts at distance 0.
- Iterative and stack-safe, but the frontier can hold O(V) nodes on wide graphs.