BFS — Level-by-Level and Shortest Paths

BFS explores level by level using a queue. Its superpower: in unweighted graphs/grids, the first time BFS reaches a node is via a shortest path — guaranteed.

The template (memorise the level-size trick)

function bfs(start) {
  const queue = [start];
  const seen  = new Set([start]);
  let steps = 0;

  while (queue.length) {
    const levelSize = queue.length;          // ← snapshot the level
    for (let i = 0; i < levelSize; i++) {   //   process exactly one level
      const node = queue.shift();
      if (isGoal(node)) return steps;
      for (const next of neighbours(node)) {
        if (!seen.has(next)) {
          seen.add(next);                    // mark WHEN ENQUEUING (not when popping!)
          queue.push(next);
        }
      }
    }
    steps++;                                 // finished a level → one more step
  }
  return -1;
}

The levelSize snapshot is what turns plain BFS into "how many steps" answers — rotting oranges, word ladder, minimum knight moves are all this template.

Grid BFS — the interview favourite

const DIRS = [[1,0],[-1,0],[0,1],[0,-1]];
// neighbours of (r, c):
for (const [dr, dc] of DIRS) {
  const nr = r + dr, nc = c + dc;
  if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !seen.has(nr + "," + nc)) {
    ...
  }
}

The two bugs everyone writes

• Marking seen on pop instead of push — the same node enters the queue many times → TLE. Mark when enqueuing.
• Forgetting the seen set entirely — any cycle = infinite loop.

Spot it when…

• "Shortest / minimum number of steps" in an unweighted graph, grid, or state space.
• "Level by level" / "layer" language for trees.
• Spreading processes: infection, fire, rotting — simulate one level per time unit.

BFS vs DFS in one line: BFS for shortest/nearest (queue), DFS for exists/count/all-paths (recursion). Next: DFS & Backtracking.