Pathfinding Algorithm
Depth-First Search
“The Maze Runner”
History
The concept of Depth-First Search dates back to the 19th century with Charles Pierre Trémaux, who created a manual method for solving mazes. It was formalized for computers alongside other fundamental graph algorithms in the mid-20th century.
If BFS is a cautious expanding circle, DFS is a lightning bolt. It commits to a decision and sticks with it until it hits a wall. It is the algorithmic equivalent of looking for your car keys by walking in a straight line until you hit a fence, then turning left.
How It Works
DFS is aggressive. It explores as far as possible along each branch before backtracking. It doesn't care about the "closest" nodes; it cares about the "deepest" nodes.
The Algorithm Step-by-Step
- Initialize: Push the start node onto a stack.
- Pop: Take the top node off the stack.
- Explore: If it hasn't been visited, mark it.
- Check Goal: If we found it, celebrate.
- Push Neighbors: Add all unvisited neighbors to the stack.
- Repeat: Continue until the stack is empty.
Stack vs. Recursion
DFS is naturally recursive. You can implement it with an explicit Stack data structure, or you can just let the system call stack handle it via recursion.
Why It Does Not Guarantee Shortest Path
DFS might find a path that winds around the entire map before stumbling onto the goal, even if the goal was just one tile away from the start. It is lucky, not smart.
Mathematically, it does the same amount of work as BFS (visiting nodes and edges). It just does them in a drastically different order.
This is where DFS shines. It only needs to store the current path of nodes. On deep, branching trees, this is significantly more memory efficient than BFS.
The core data structure powering Depth-First Search.
How this algorithm appears during visualization.
Code Walkthrough
Real implementations in multiple programming languages. Select a language to view idiomatic code.
1def dfs(grid: list[list[int]], start: tuple[int, int], end: tuple[int, int]) -> list[tuple[int, int]] | None:2 """Find a path in grid using DFS. Does NOT guarantee shortest path."""3 rows, cols = len(grid), len(grid[0])4 stack = [(start, [start])]5 visited = set()6 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]78 while stack:9 (row, col), path = stack.pop()1011 if (row, col) in visited:12 continue13 visited.add((row, col))1415 if (row, col) == end:16 return path1718 for dr, dc in directions:19 new_row, new_col = row + dr, col + dc2021 if (0 <= new_row < rows and 0 <= new_col < cols22 and grid[new_row][new_col] == 023 and (new_row, new_col) not in visited):24 stack.append(((new_row, new_col), path + [(new_row, new_col)]))2526 return NoneReal World Use Cases
- 1Maze Generation (creating long, winding corridors)
- 2Topological Sorting (build dependency resolution)
- 3Cycle Detection in graphs
- 4Sudoku and Puzzle Solvers
- 5Pathfinding where memory is extremely limited
- 6Game AI decision trees
Key Insights
- It finds *a* path, not necessarily the *good* path.
- It is extremely memory efficient compared to BFS.
- It preserves the topology of the graph better than BFS.
- It can get stuck in infinite loops if you don't track visited nodes properly.
- It mirrors how humans naturally try to solve mazes.
When to Use
Use DFS when you need to visit every node (like in a simulation), when memory is tight, or when you are generating a maze rather than solving one.
When NOT to Use
Never use DFS if you need the shortest path. Also avoid it on extremely deep graphs (like state-machines) without a depth limit, or you'll trigger a Stack Overflow.