1. One-Liner
DFS follows one path as deep as possible before backtracking, using a stack (explicit or recursion).
2. The Problem It Solves
You need to traverse all reachable vertices, detect cycles, find connected components, run topological sort (on DAGs), solve mazes, or enumerate paths — DFS is the default deep exploration tool.
3. The Core Idea
Walk a maze while keeping a string on your hand: go forward until dead end, then rewind to the last junction and try another tunnel. The call stack (or explicit stack) remembers that path.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | Mark current vertex visited |
| 2 | For each unvisited neighbor: recursively DFS (or push on stack) |
| 3 | When no new neighbors: backtrack (return or pop) |
| 4 | Colors/timestamps (white/gray/black) detect cycles in directed graphs |
| 5 | Postorder on DAG yields reverse topological order |
5. Dry Run Example
Tree edges: 0→1, 0→2, 1→3. DFS from 0 visiting smaller id first: go 0→1→3, backtrack to 1, done, back to 0, go 2. Order: 0,1,3,2. If you need preorder, record on entry; postorder on exit.
6. Key Properties
| Property | Detail |
|---|---|
| Shortest path (unweighted) | Not guaranteed — use BFS |
| Memory | O(h) recursion depth; O(V) worst case |
| Cycle detection | Back edge to gray vertex (directed) |
| Topological sort | Finish times decreasing on DAG |
7. Where It Is Used
| Company / System | Use |
|---|---|
| Garbage collectors | Mark phase traces reachable objects |
| IDE / Git | Dependency and folder tree walks |
| Compilers | CFG analysis, some register allocation contexts |
| Puzzle games | Maze generation (e.g., randomized DFS) |
8. Interview Tips
Know iterative vs recursive, time O(V+E), stack overflow risk on deep graphs, tree edge / back edge / cross edge classification. Follow-ups: find all paths, strongly connected components setup.
9. Comparison with Other Algorithms
| DFS | BFS | |
|---|---|---|
| Data structure | Stack | Queue |
| Unweighted shortest path | No | Yes |
| Memory narrow trees | O(depth) | O(frontier) |
| Topological sort | Natural on DAG | Awkward |
10. Complexity
| -- | -- |
|---|---|
| Time | O(V + E) |
| Space | O(V) visited + O(depth) recursion stack |
Implementation Example (PYTHON)
def dfs(adj, s):
n = len(adj)
vis = [False] * n
out = []
def rec(u):
vis[u] = True
out.append(u)
for v in adj[u]:
if not vis[v]:
rec(v)
rec(s)
return out