Breadth-First Search

Explanation

BFS starts at a source node, visits all its neighbors (level 1), then visits all their unvisited neighbors (level 2), and so on. The queue data structure enforces this order: you process nodes FIFO, so all level-k nodes are processed before any level-(k+1) nodes. This level-by-level exploration guarantees that the first time BFS reaches a node, it has found the shortest path (by edge count) from the source. BFS uses O(V) space (the queue holds at most one level's worth of nodes) and runs in O(V+E) time, same as DFS. The choice between BFS and DFS depends on what you're looking for: BFS finds shortest paths in unweighted graphs; DFS is better for detecting cycles, topological sort, and exhaustive path exploration. Real-world BFS applications: social network "degrees of separation" (shortest path from you to a celebrity in a friendship graph), web crawlers (explore pages one link-hop at a time), GPS navigation on unweighted road networks, garbage collection (mark phase scans reachable objects via BFS), binary tree level-order traversal, and multi-source BFS (start from multiple source nodes simultaneously to find distances from any source to all others, useful for "nearest exit" or "spreading fire" problems). Multi-source BFS is a powerful extension: add all sources to the queue simultaneously at the start, and BFS naturally finds the shortest distance from any source to each node. This solves "find distance from all '1' cells to nearest '0' cell" problems elegantly.

Code Example

// BFS — shortest path in unweighted graph
function bfs(adj, start, end) {
  const visited = new Set([start]);
  const queue = [[start, 0]]; // [node, distance]

  while (queue.length) {
    const [node, dist] = queue.shift();
    if (node === end) return dist;

    for (const neighbor of (adj.get(node) || [])) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, dist + 1]);
      }
    }
  }
  return -1; // not reachable
}

// BFS level-order traversal on a binary tree
function levelOrder(root) {
  if (!root) return [];
  const result = [];
  const queue = [root];

  while (queue.length) {
    const levelSize = queue.length;
    const level = [];
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();
      level.push(node.val);
      if (node.left)  queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
    result.push(level);
  }
  return result; // [[root], [level2...], [level3...]]
}

Why It Matters for Engineers

BFS's guarantee of finding the shortest unweighted path makes it the correct algorithm for any "minimum steps" or "minimum hops" problem. If you use DFS for a shortest-path problem, you'll get an answer, but it won't be the shortest path. This is a correctness issue, not just a performance issue — and it's the kind of subtle bug that only emerges on certain inputs. Level-order tree traversal (a special case of BFS) is a common interview problem that also appears in production code: serializing a tree to array, finding the minimum depth, connecting nodes at the same level, and printing trees by depth all use level-order traversal.