Skip to content
ReadMe Daily

Search articles, problems, patterns and every cheat sheet topic.

Pathfinding

Breadth-First Search Visualiser

A queue, so the search spreads out evenly in all directions.

Drawthen drag on the board
Board

Breadth-first search: a queue, so cells come out in the order they went in. That spreads outwards evenly.

Cells expanded
0
In the queue
1
O(cells + edges)extra space O(cells) for the queue

There are 303 cells to search on this board. The gap between that and the cells expanded is what a better search order buys you — walls and mud change it, so redraw the board and watch it move.

  • Start
  • End
  • Wall
  • Mud (costs 5)
  • Waiting to be expanded
  • Expanded
  • Route
function bfs(grid, start, end) {
const queue = [start];
const cameFrom = new Map([[start, null]]);
while (queue.length > 0) {
const cell = queue.shift(); // the oldest waiting cell
if (cell === end) return path(cameFrom, end);
for (const next of neighbours(grid, cell)) {
if (cameFrom.has(next)) continue;
cameFrom.set(next, cell);
queue.push(next);
}
}
return null; // the end is walled off
}

The highlighted line is the one that produced the picture on the left.

What Breadth-First Search does

Breadth-first search explores everything one step away, then everything two steps away, and so on. Because it never looks at a cell four steps out before it has finished the cells three steps out, the first time it reaches the goal it must have done so by the shortest route.

How it works, step by step

  1. Put the starting cell in a queue and record that it came from nowhere.
  2. Take the cell from the front of the queue — the one that has been waiting longest.
  3. If it is the goal, follow the recorded parents back to the start to rebuild the route.
  4. Otherwise add every unseen neighbour to the back of the queue, recording that it was reached from this cell.

What to watch for

  • The visited area grows as a diamond, not a line. Every cell at the same distance is taken before anything further out.
  • Each cell is only ever added once, because a cell already in `cameFrom` is skipped. That one check is what stops the search going round in circles.
  • Put mud on the board. BFS walks straight through it, because it counts steps and not cost — compare that with Dijkstra on the same board.
  • Change `queue.shift()` to `stack.pop()` and you have depth-first search. Nothing else differs.

Cost

TimeO(cells + edges)
Extra spaceO(cells) for the queue
FindsFewest steps
Handles costsNo — every step counts as 1
Waiting listQueue (first in, first out)

When to reach for it

For the shortest route when every step costs the same: tile maps, friend-of-a-friend hops in a social graph, the fewest moves in a puzzle. If steps have different costs, you need Dijkstra instead.

Read more