Breadth-first search

Overview

Breadth-first search (BFS) explores a graph level by level. Starting from a source, it visits every neighbor at distance 1, then every node at distance 2, and so on, using a first-in-first-out queue.

Because it expands in order of distance, BFS finds the shortest path in an unweighted graph. It is the default choice for minimum steps, minimum moves, nearest exit, and spreading processes such as rotting oranges or network broadcasts.

When to use it

• Shortest path or fewest steps when every edge costs the same.
• Level-order traversal of trees.
• Multi-source spreading problems (start with all sources in the queue).
• Checking connectivity or bipartiteness.

Problem patterns it solves

Where it is used in real software

Key terms

Queue

FIFO structure holding discovered nodes waiting to be processed.

Visited set

Nodes already discovered, preventing repeated processing and infinite loops.

Level / distance

Number of edges from the source.

Parent map

Records which node discovered each node, allowing path reconstruction.

How it works, step by step

1. 1
   Seed the queue

   Push the source, mark it visited, and set its distance to 0.

2. 2
   Dequeue the front node

   Process nodes in the order they were discovered.

3. 3
   Discover neighbors

   For each unvisited neighbor, mark it visited immediately, set distance = current + 1, record the parent, and enqueue it.

4. 4
   Repeat until empty

   When the queue empties, every reachable node has its shortest distance.

5. 5
   Rebuild the path

   Follow parent links from the destination back to the source, then reverse.

BFS from A

A: B, C | B: D | C: D, E | D: F | E: F

Visit order is A, B, C, D, E, F. The shortest path from A to F has 3 edges: A, B, D, F (following parents F to D to B to A).

Implementation

1type Graph = Map<string, string[]>;2 3function bfs(graph: Graph, source: string) {4  const distance = new Map<string, number>([[source, 0]]);5  const parent = new Map<string, string | null>([[source, null]]);6  const queue: string[] = [source];7  let head = 0; // avoid O(n) Array.shift()8 9  while (head < queue.length) {10    const node = queue[head++];11    for (const next of graph.get(node) ?? []) {12      if (distance.has(next)) continue; // already discovered13      distance.set(next, distance.get(node)! + 1);14      parent.set(next, node);15      queue.push(next);16    }17  }18 19  return { distance, parent };20}21 22function pathTo(parent: Map<string, string | null>, target: string): string[] {23  if (!parent.has(target)) return [];24  const path: string[] = [];25  for (let node: string | null = target; node !== null; node = parent.get(node)!) {26    path.push(node);27  }28  return path.reverse();29}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Marking nodes visited when dequeued instead of enqueued.

  Fix: Mark on enqueue; otherwise the same node can be queued many times.

• Using Array.shift() in JavaScript.

  Fix: shift is O(n). Use a head index or a real deque.

• Using BFS for weighted shortest paths.

  Fix: Switch to Dijkstra with a priority queue.

Interview questions

Practice problems