Depth-First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. Imagine walking through a maze and always choosing to go deeper into an unexplored corridor rather than trying a different turn — that's DFS in action.
DFS is the engine behind recursive backtracking, the most popular maze generation algorithm. By randomly choosing neighbors, DFS carves long winding corridors that feel organic and challenging. Every cell is visited exactly once, producing a "perfect maze" — one with exactly one solution and no loops.
| Time Complexity | O(V + E) — visits each vertex and edge once |
| Space Complexity | O(h) — where h is the maximum depth of the recursion stack |
| Finds Shortest Path? | ❌ No (use BFS or A* instead) |
| Complete? | ✅ Yes (in finite graphs) |
| Data Structure | Stack (implicit via recursion, or explicit) |
| Best For | Maze generation, topological sort, cycle detection |
Our Classic Maze is generated using DFS-based recursive backtracking. Play it and experience the long, winding corridors that DFS creates.
DFS dives deep into one path before trying alternatives, while BFS explores all neighbors at the current distance first. BFS always finds the shortest path; DFS uses less memory and is the basis of recursive backtracking maze generation.
No. DFS finds a path, but it may be longer than necessary. For the shortest path, use BFS (unweighted) or A* (weighted).
DFS creates long, winding corridors with few branches, producing mazes that feel natural and challenging. The recursive backtracking variant randomly chooses neighbors, guaranteeing every cell is reachable with exactly one solution.