Depth-First Search (DFS)
What you'll learn: How DFS explores a state space by diving as deep as possible before backtracking, using minimal memory with a stack-based approach.
Core Idea
Depth-First Search is an uninformed search algorithm that explores a search tree by always selecting the deepest unexplored node in the current path. Unlike BFS which explores level-by-level, DFS commits to a path and follows it all the way down until it hits a dead end (goal state, leaf node, or explored node), then backtracks to try alternative paths.
Think of DFS like exploring a maze by always taking the first unexplored corridor you see, walking until you can't go further, then retracing your steps to the last intersection with unexplored paths.
Why It's Memory-Efficient
DFS uses a stack (Last-In-First-Out) to manage the frontier. You only need to store:
- The current path from root to the deepest explored node
- Unexplored siblings at each level along that path
This is dramatically more memory-efficient than BFS's queue, which can hold an entire level of the search tree. For a tree with branching factor b and maximum depth m, DFS uses O(b×m) memory versus BFS's O(b^d) where d is the solution depth.
The Trade-off
DFS is not guaranteed to be optimal (doesn't find the shortest path) and may not be complete if the search space has infinite depth. It can get "lost" exploring very deep, fruitless branches while the goal sits near the root on a different branch.
Key Takeaway: DFS prioritizes memory efficiency over optimality, making it ideal for deep search spaces where exploring all paths systematically is impractical, but less suitable when finding the shortest solution matters.