Breadth-First Search vs Depth-First Search
Same maze, same speed, first to the exit wins. On this maze Depth-First Search gets there first and turns gold.
The numbers
- BFS explored
- 2,150 cells
- BFS path
- 241 steps
- DFS explored
- 1,886 cells
- DFS path
- 441 steps
Breadth-First Search
Breadth-First Search explores a maze in rings: every cell one step away, then two, then three, until it reaches the exit. More on Breadth-First Search.
Depth-First Search
Depth-First Search follows one corridor as far as it goes, and only backs up when it hits a dead end. More on Depth-First Search.
FAQ
Which is faster in a maze, Breadth-First Search or Depth-First Search?
On this maze Depth-First Search reached the exit first, after exploring 1,886 cells to 2,150. On other mazes the result can flip; press New race to try another.
How is the race fair?
Both solvers run on the same maze and explore the same number of cells per frame. Whoever explores fewer cells before reaching the exit finishes first and turns gold.
Which one finds the shorter path?
Breadth-First Search: 241 steps to 441. Exploring fewer cells and finding the shorter path are different things.