Graph Breadth-First Search

How It Works

Graph BFS expands outward from a source (or sources) one "ring" at a time, guaranteeing that the first time you reach any node, you've reached it via the shortest possible path (in an unweighted graph). The skeleton is: enqueue all starting nodes with distance 0, then repeatedly dequeue, look at neighbors, and enqueue any unvisited one with distance + 1.

function bfsShortestDistance(grid, sources) {
  const rows = grid.length;
  const cols = grid[0].length;
  const visited = new Set();
  const queue = [];

  for (const [r, c] of sources) {
    queue.push([r, c, 0]);
    visited.add(`${r},${c}`);
  }

  const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  let maxDistance = 0;

  while (queue.length > 0) {
    const [r, c, dist] = queue.shift();
    maxDistance = Math.max(maxDistance, dist);

    for (const [dr, dc] of directions) {
      const nr = r + dr;
      const nc = c + dc;
      const key = `${nr},${nc}`;

      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited.has(key)) {
        visited.add(key);
        queue.push([nr, nc, dist + 1]);
      }
    }
  }

  return maxDistance;
}

The "graph" is often implicit rather than an explicit adjacency list: a grid where neighbors are adjacent cells, or a state space where each "node" is a string (a word, a lock combination) and "edges" connect strings that are one valid transformation apart. Multi-source BFS (starting the queue with every source node at distance 0 instead of just one) is the key trick behind problems like "rotting oranges" or "walls and gates," where several starting points spread simultaneously.

When To Use It

Reach for graph BFS when you spot any of these signals:

• The problem asks for the minimum number of steps, moves, turns, or minutes to reach a goal or to reach every reachable location.
• You need the shortest path in an unweighted graph or grid; BFS guarantees the first visit to any node is via the shortest path, which DFS cannot guarantee.
• There are multiple starting sources spreading at once (multiple rotten oranges, multiple gates, multiple fire sources): seed the queue with all of them at distance 0 rather than running BFS once per source.
• The state space is implicit: each "node" is a string, a word from a dictionary, or a 4-digit lock code, and "neighbors" are states reachable by one valid transformation (change one letter, turn one wheel by one digit).
• You're asked something like "can you reach X, and if so in how few steps": the "few steps" part is the signal that this is BFS, not just reachability (which could be either BFS or DFS).

Time & Space Complexity

• Time: O(V+E). Every node/state is enqueued and processed once, and every edge/transition is examined once. For grid problems this is O(rows × cols); for word-ladder-style problems it's O(wordCount × wordLength × alphabetSize) since generating neighbors means trying every letter substitution at every position.
• Space: O(V). The queue plus the visited set, bounded by the total number of distinct nodes/states/cells that can ever be reached.

Alternative Approaches

• DFS with memoized distances: technically possible for some of these problems but far more error-prone for "shortest path" guarantees; DFS naturally finds a path, and retrofitting it to guarantee the shortest one requires extra bookkeeping that BFS gives you for free.
• Dijkstra's algorithm: if the state space has weighted transitions (not all steps cost the same), plain BFS breaks down and you need Dijkstra (or 0-1 BFS if weights are just 0 or 1) instead.
• Bidirectional BFS: for problems like Word Ladder with a large dictionary, searching outward from both the start and end word simultaneously and stopping when the frontiers meet can cut the search space dramatically compared to single-direction BFS.

Common Mistakes

• Running single-source BFS once per source instead of multi-source BFS: for "rotting oranges" style problems, seeding the queue with all initial sources at once and running BFS a single time is both correct and far more efficient than looping BFS per source.
• Marking a node visited when it's dequeued instead of when it's enqueued: this allows the same node to be added to the queue multiple times from different neighbors before it's ever processed, wasting time and occasionally causing incorrect distances.
• Forgetting the "unreachable" case: after BFS completes, some target cells/oranges/words may never have been visited; the problem usually wants you to detect this and return a sentinel like -1, not silently ignore it.
• Recomputing neighbor generation incorrectly for implicit graphs: for Word Ladder-style problems, a common bug is generating "neighbors" by comparing against every word in the list with an O(wordLength) diff check instead of generating candidate strings directly, which is both slower and easy to get subtly wrong.
• Using Array.shift() in tight loops on large inputs: same pitfall as tree BFS: shift() is O(n); prefer an index-based queue pointer for large state spaces.

Pattern Summary

Graph BFS is "expand in waves, track distance by ring." Whenever you need the fewest steps to a goal, a shortest path in an unweighted space, or simultaneous spread from multiple sources, seed the queue with your starting point(s) at distance 0 and let BFS's level-by-level guarantee do the work of finding the optimal answer.