DFS Template
The Intuition
Picture yourself exploring a maze with a ball of string. At the entrance, you pick a corridor and start walking. You keep going straight until you hit a dead end. Then you follow your string back to the last fork you passed and try the next corridor you haven't explored yet. You keep doing this until you've walked every reachable corridor in the maze.
Your ball of string is the call stack. Every time you step into a new corridor (make a recursive call), the string gets a little longer. Every time you hit a dead end and walk back (return from a function), you're reeling string in. The stack remembers every fork you've passed through so you always know where to backtrack to.
There's one critical rule: mark the walls as you go. If you walk into a room you've already visited, turn around immediately. Without markings, you'd loop forever in a maze with cycles, walking the same corridors over and over, never finishing.
The iterative version swaps your call stack for an explicit stack data structure. You push neighbors onto the stack instead of making recursive calls. Pop from the top, process, push unvisited neighbors. The behavior is the same. You go deep before going wide. You exhaust one branch completely before starting another.
Cycle detection, connected components, topological sorting, path finding, flood fill, island counting, or any problem requiring full exploration of branches before backtracking.
- Need shortest path (use BFS)
- Graph is very wide and shallow (BFS is more efficient)
- Need level-by-level processing
Variations:
- Recursive DFS: Clean and concise, but limited by stack depth.
- Iterative DFS: Uses an explicit stack, avoids stack overflow for large graphs.
- Cycle detection (directed): Use three colors (white/gray/black) to detect back edges.
- Cycle detection (undirected): Track parent to avoid false positives on the edge you came from.
- Disconnected graph with multiple separate components
- Single node with no edges
- Graph containing a self-loop
Key Points
- •Use recursion (call stack) or an explicit stack (LIFO)
- •Mark visited before recursing to avoid infinite loops
- •Useful for detecting cycles, connected components, and paths
- •Iterative DFS uses a stack; processes nodes in reverse neighbor order
- •Can track entry/exit times for advanced applications
Code Template
1 def dfs_recursive(graph, node, visited=None):
2 """DFS traversal using recursion."""
3 if visited is None:
4 visited = set()
5 visited.add(node)
6 # process(node)
7
8 for neighbor in graph[node]:
9 if neighbor not in visited:
10 dfs_recursive(graph, neighbor, visited)
11 return visited
12
13 def dfs_iterative(graph, start):
14 """DFS traversal using explicit stack."""
15 visited = set()
16 stack = [start]
17
18 while stack:
19 node = stack.pop()
20 if node in visited:
21 continue
22 visited.add(node)
23 # process(node)
24
25 for neighbor in graph[node]:
26 if neighbor not in visited:
27 stack.append(neighbor)
28 return visited
29
30 def has_cycle_directed(graph, n):
31 """Detect cycle in directed graph using colors."""
32 WHITE, GRAY, BLACK = 0, 1, 2
33 color = [WHITE] * n
34
35 def dfs(u):
36 color[u] = GRAY
37 for v in graph[u]:
38 if color[v] == GRAY:
39 return True
40 if color[v] == WHITE and dfs(v):
41 return True
42 color[u] = BLACK
43 return False
44
45 return any(color[i] == WHITE and dfs(i) for i in range(n))Common Mistakes
- Stack overflow on large graphs. Use iterative DFS instead
- Not marking visited before recursion (causes infinite loops)
- Confusing DFS order with BFS shortest-path guarantees