What Is Depth-First Search?
Depth-First Search (DFS) is a graph/tree traversal that dives as deep as it can along one path, and when it can't go further, backtracks to try another path. It's the counterpart to breadth-first search (BFS) among the basic traversals.
The one-line idea: "follow one path to its end first." When you hit a dead end, return to the most recent fork and try an unvisited path.
It Runs on a Stack
DFS's "backtracking" is naturally a stack. The most common implementation is recursion, where the function call stack plays that role. You can also use an explicit stack with a loop.
Either way, marking visited is essential. Without it, a graph with cycles loops forever over the same nodes.
How It Works
Step 1. Mark the start node visited.
Step 2. Pick one unvisited neighbor and dive into it (a recursive call).
Step 3. When there's nowhere left to go, the call returns and you backtrack to the previous node, where you try another unvisited neighbor.
Step 4. Repeat until every reachable node is visited.
The AlgoNote visualization color-codes the edges going deeper and the moments of backtracking, step by step.
Difference from BFS
| DFS | BFS | |
|---|---|---|
| Structure | stack (recursion) | queue |
| Order | depth first | breadth (nearest) first |
| Good for | path existence, cycle detection, topological sort, connected components | unweighted shortest path, fewest steps |
Shortest-distance problems that need nearest-first suit BFS; problems where you "go to the end" to understand structure suit DFS.
Time and Space Complexity
| Complexity | |
|---|---|
| Time | O(V + E) |
| Space | O(V) |
V is the number of vertices, E the number of edges. Each is visited once, so it's O(V + E).
Walking Through an Example
In a graph with edges 0 - 1, 0 - 2, 1 - 3, DFS from 0:
- •visit 0 → dive to 1 → dive to 3 → 3 dead-ends, back to 1 → 1 dead-ends, back to 0 → dive to 2
- •visit order, e.g.: 0 → 1 → 3 → 2
Common Mistakes
- •Missing visited marks: an infinite loop on cycles. DFS's number-one pitfall.
- •Mark timing: mark a node on entry so you don't enqueue/push the same node twice.
- •Recursion depth limit: very deep graphs can overflow the call stack, so an explicit stack is sometimes used.
See It in Action on AlgoNote
Watch DFS dive deep along one path and backtrack to try another when stuck, step by step on AlgoNote.