function bfs(grid: Grid, start: Cell, goal: Cell) {const queue: Cell[] = [start];
const distance = new Map([[start, 0]]), parent = new Map();
while (queue.length > 0) {const current = queue.shift()!; // oldest first
if (current === goal) return rebuild(parent, current);
for (const neighbor of neighbors(grid, current)) {if (distance.has(neighbor)) continue;
distance.set(neighbor, distance.get(current)! + 1);
parent.set(neighbor, current);
queue.push(neighbor);
}
}
return null;
}
Start at (12, 1), goal at (5, 42). The open set holds only the start.
Understanding Breadth-first search
The idea
Breadth-first search explores the grid in rings: every cell at distance 1 from the start, then every cell at distance 2, and so on. It keeps a queue of open cells, always takes the oldest one, and enqueues its unvisited neighbours behind everything already waiting.
Because cells are reached in order of distance, the first time BFS pops the goal it has found a shortest path, as long as every step costs the same. That is its whole guarantee, and also its weakness: it floods evenly in every direction and never looks at where the goal is.
The four stages
Complexity
Versus its siblings
Pseudocode
BFS(start, goal)
queue ← [start]; dist[start] ← 0
while queue not empty
current ← dequeue the oldest
if current = goal: return path via parent
for each neighbour of current not yet seen
dist[neighbour] ← dist[current] + 1; parent[neighbour] ← current; enqueue neighbour
When to use
Pitfalls
History
Konrad Zuse described breadth-first search in his 1945 thesis on Plankalkül, which was not published until 1972. Edward Moore rediscovered it in 1959 to find the shortest route through a maze, and C. Y. Lee used it in 1961 for routing wires on circuit boards, the maze router still used in chip design.