Breadth-First Search maze algorithm
Breadth-First Search explores a maze in rings: every cell one step away, then two, then three, until it reaches the exit.
How it works
BFS keeps a queue. It takes the oldest cell off the front, looks at its open neighbours, and adds any it hasn't seen to the back of the queue, remembering where each came from. So it finishes every cell at distance 1 before any at distance 2, and so on.
That means the first time it reaches the exit, it got there by a shortest path, which it reads back by following the 'came from' links. The cost is that it explores in every direction, including away from the goal, so it usually touches most of the maze.
What to watch for
Watch the colour spread out evenly like water from the start, and the pitch rise as the flood gets further from the start. Then the white shortest path traces back through it.
Properties
- Shortest path
- Always (equal-cost steps)
- Finds the exit
- Always, if there is one
- Explores
- Everything closer than the exit
- Memory
- The frontier queue
Race it
Same maze, same speed, first to the exit wins: Breadth-First Search vs Depth-First Search. Or put it in a gauntlet, where the winner stays on.
FAQ
Does BFS always find the shortest path?
In a maze where every step costs the same, yes. The first time it reaches a cell is along a shortest route.
BFS or DFS for mazes?
BFS if you need the shortest path. DFS often reaches the exit after exploring fewer cells, but its path can be much longer.