Interactive demo
Depth-First Search
Depth-first search (DFS) always continues from the cell it reached last. It runs as far as it can in one direction and only turns back at dead ends, like exploring a maze by always taking the next unexplored corridor.
Draw walls or mud on the grid and drag the start and the goal. Once a search is finished, every change is searched again right away. Try a maze: DFS solves it, but in open areas it takes long detours. The order of the directions (up, right, down, left) decides where it goes first.
Playback
- Expanded
- –
- Frontier (max.)
- –
- Path cost
- –
Press Play or Next Step to start the search.
Grid
Options
Legend
- Start (drag to move)
- Goal (drag to move)
- Wall
- Mud
- Frontier (open list)
- Visited (closed list)
- Expanded right now
- Path
Properties
Optimal
No
Takes the first path it stumbles upon, often a long detour.
Weighted cells
No
Ignores the costs completely.
Heuristic
No
Blind: only the order of the directions decides where it goes.
Any angle
No
Moves from cell to cell, straight or diagonally.
All pathfinding algorithms compared
| Algorithm | Optimal | Weighted cells | Heuristic | Any angle |
|---|---|---|---|---|
| Breadth-First Search | Without mud and diagonals | No | No | No |
| Depth-First Search this page | No | No | No | No |
| Dijkstra's Algorithm | Yes | Yes | No | No |
| Bidirectional Search | Yes | Yes | No | No |
| Greedy Best-First Search | No | No | Yes | No |
| A* Search | With weight 1 and an admissible heuristic | Yes | Yes | No |
| Jump Point Search | Without mud | No | Yes | No |
| Theta* | No | Shortcuts over open ground only | Yes | Yes |
1. A stack
- Put the start onto a stack.
- Take the newest cell off the stack, and skip it if it was visited already.
- Mark it visited and put all unvisited neighbors onto the stack, the preferred direction last.
- Repeat until the goal comes off the stack.
2. Deep, not wide
In trees and deep searches, DFS only has to remember the branch it is on, so it needs little memory. On a grid that brings no advantage: it still visits many cells, and the path it finds is simply the one it happened to take.
3. Where it is used
DFS is the basis of maze generators (the recursive backtracker), topological sorting, finding the connected parts of a graph and searching game trees. As a pathfinder it is a poor choice, which makes it a good comparison.