DFS on Graphs
Scenario
You're in a labyrinth and want to find a way out.
Do you systematically check every room one step away, or do you pick a path and run down it until you hit a dead end?
Why it exists
Problem: Some graph problems require exploring the deepest possible paths (like finding a complete route, identifying cycles, or solving puzzles) rather than the shortest path.
Naive approach: Randomly wandering through the graph might eventually reach every node but gets stuck in cycles.
Better idea: Pick a starting node and recursively plunge down a path until a dead end is reached. Backtrack only when necessary, keeping a strict `visited` set to prevent infinite loops.
Mental model
Go as deep as possible down one branch until you hit a dead end, then rewind to the last fork and try another path.
DFS abandons the queue in favor of a stack (usually the call stack via recursion). It visits a node, marks it, and immediately recursively calls itself on the first unvisited neighbor. The phase invariant: every node is marked visited at most once to prevent infinite loops on any cycle.
Repeated decision: go deeper into the first unvisited neighbour, or backtrack?
Explanation
Depth-First Search (DFS) prioritizes extreme depth over uniform breadth. Instead of checking neighbors level-by-level, DFS selects a single adjacent neighbor and recursively plunges down that specific path until it encounters a dead end. Upon reaching this terminus, the algorithm backtracks to the most recent fork and explores the next available branch.
Mechanistically, DFS uses a Last-In-First-Out (LIFO) stack (almost always the call stack via recursion) and a `visited` set. The phase invariant is strict: mark a node visited *prior* to recursing into its neighbors to prevent infinite loops on cycles.
The #1 misconception is that DFS finds the shortest path. **DFS finds *a* path, NOT the shortest one**. Let's prove this with a hand-trace on a 4-node undirected graph:
```
Adjacency List:
A: [C, B]
B: [A, D]
C: [A, D]
D: [C, B]
```
Suppose we want to find a path from `A` to `B`. A BFS would check `A`'s neighbors, find `B` in its list, and stop in 1 edge.
Watch what DFS does based on the adjacency list order:
- Start at `A`. Mark `A` visited. Neighbors of `A` are `C` and `B`.
- DFS checks `C` first. `C` is unvisited, so we recurse into `C`.
- At `C`, mark `C` visited. Neighbors are `A` and `D`.
- `A` is already visited. Check `D`. `D` is unvisited, so recurse into `D`.
- At `D`, mark `D` visited. Neighbors are `C` and `B`.
- `C` is already visited. Check `B`. `B` is unvisited, so recurse into `B`.
- We found `B`! But the path taken was `A → C → D → B` (3 edges), completely missing the direct `A → B` edge.
Because DFS uses the call stack, the maximum recursion depth equals the longest path in the graph. In a massive graph, an `O(V)` recursion depth will cause a stack overflow, requiring an explicit iterative stack instead.
Time complexity is `O(V+E)`. The `visited` set ensures each vertex `V` is processed once, and we scan each vertex's adjacency list meaning we look at each edge `E` at most twice (in undirected graphs).
Key points
- Invariant: Each node is marked visited at most once. Violating this leads to an infinite loop on any cycle.
- Not the Shortest Path: DFS will find *a* path between two nodes, but it provides zero guarantees about finding the shortest path.
- Stack Overflow Risk: Recursion depth is O(V). For large or deep graphs, this can blow the call stack. An iterative stack avoids this.
Pattern: Depth-First Search
Recognition cues:
- finding ALL paths
- cycle detection
- topological sorting
- exploring puzzle states
Engineering examples
Garbage Collection
Identify unreachable objects in memory to free them.
Mark-and-sweep garbage collectors use DFS starting from root variables to set a mark bit on every reachable object, because the stack overhead is smaller than BFS's queue.
Common mistakes
- Forgetting to mark nodes as visited: Without a `visited` set, traversing a cyclic graph will bounce between the same nodes infinitely until the stack overflows.
- Using DFS to find the shortest path: DFS plunges down the first path it sees. In a weighted or unweighted graph, the first path found could be the longest and most winding route.
Recall questions
- What data structure drives Depth-First Search?
- Why must you mark nodes as visited in DFS?
- Does DFS guarantee the shortest path on an unweighted graph?
Questions & answers
Determine if there is a valid path from the source to the destination in a graph.
Run DFS starting from the source, marking nodes as visited. If you reach the destination during traversal, return true.
Approach: Basic reachability query where path length doesn't matter.
Find all possible paths from source to target in a Directed Acyclic Graph (DAG).
Use a backtracking DFS. Push nodes onto a current path, recurse, and then pop the node off the path when backtracking to explore other routes.
Approach: DFS naturally tracks the current path from the root via the call stack, making it perfect for path enumeration.
Continue learning
Previous: Graph representations
Previous: BFS on graphs
Next: Connected Components
Next: Cycle Detection
Next: Topological Sort