🗺️ BFS on Grid

How It Works

Breadth-First Search (BFS) finds the shortest path in an unweighted graph by exploring nodes level by level. On a grid, each cell is a node, and its 4 neighbors are its edges.

Algorithm

1. Enqueue the start cell
2. Dequeue a cell, mark it explored, add unvisited neighbors to the queue
3. Track each cell's parent — the cell we came from
4. When we dequeue the end cell, trace parent pointers back to reconstruct the path
5. If the queue empties without finding the end, no path exists

Key Code

function* bfsGen(grid, start, end) {
  const queue = [start];
  const visited = new Set([key(start)]);
  const parent = new Map();

  while (queue.length > 0) {
    const curr = queue.shift();    // dequeue (FIFO — this is what makes it BFS)
    yield { curr, queue: [...queue] };

    if (sameCell(curr, end)) {
      const path = tracePath(parent, end);
      yield { done: true, path };
      return;
    }
    for (const nbr of neighbors(grid, curr)) {
      if (!visited.has(key(nbr))) {
        visited.add(key(nbr));
        parent.set(key(nbr), curr);
        queue.push(nbr);           // neighbors added to BACK of queue
      }
    }
  }
  yield { noPath: true };
}

Why BFS finds the shortest path: All cells at distance d are explored before any at distance d+1. The first time we reach the end, it's via the shortest route.