Depth-First Search maze algorithm
Depth-First Search follows one corridor as far as it goes, and only backs up when it hits a dead end.
How it works
DFS keeps a stack. It takes the newest cell, marks it, and pushes its unvisited neighbours. Because it always continues from the newest cell, it runs down one passage until it's stuck, then resumes from the most recent branch it skipped.
It needs little memory and on many mazes reaches the exit while exploring less of the grid than BFS. But the path it finds is whatever route it happened to take, which can be far longer than the shortest one. That's the classic race result: DFS 'wins' on cells explored, BFS wins on path length.
What to watch for
Watch a single bright thread race off in one direction, dead-end, and jump back to an earlier branch. The colours follow the order it explored, not the distance.
Properties
- Shortest path
- No
- Finds the exit
- Always, in a finite maze
- Explores
- Depends on luck and neighbour order
- Memory
- The stack
Race it
Same maze, same speed, first to the exit wins: Depth-First Search vs Breadth-First Search. Or put it in a gauntlet, where the winner stays on.
FAQ
Why is the DFS path so long?
DFS keeps the first route it found to each cell, not the shortest one, so detours stay in the path.
Is DFS faster than BFS?
Sometimes. It can reach the exit after exploring fewer cells, but it can also wander the whole maze. It depends on the maze and the order it tries neighbours.