"If BFS is a ripple spreading evenly outward, DFS is a single explorer charging down one corridor until it hits a dead end, then backing up to try the next. Same graph, opposite temperament."
The Algorithm: a Stack (or the Call Stack)
Depth-first search swaps BFS's queue for a stack — and the simplest stack is the call stack, so DFS is naturally recursive: visit a node, mark it visited, then recurse into each unvisited neighbor. The recursion dives as deep as it can down one path; when a node has no unvisited neighbors, it returns (backtracks) and the previous level tries its next neighbor. You can also write DFS iteratively with an explicit stack — push the start, pop a node, push its unvisited neighbors — which avoids Python's recursion limit on very deep graphs.
The Personality: Deep, Not Wide
DFS commits hard to one route before considering alternatives. That makes it the wrong tool for shortest paths — it might reach a node via a long, winding corridor when a short one existed — but the right tool for a whole family of problems where you need to fully explore:
Path existence — "is there any way from A to B?"
Cycle detection — DFS revisiting a node on the current path means a cycle.
Connected components — DFS from each unvisited node carves out one component.
Backtracking — mazes, puzzles, permutations: DFS is the backtracking engine you'll meet in the Recursion track.
DFS uses a stack (or recursion) frontier: plunge deep down one path, backtrack at dead ends. It does NOT find shortest paths, but it's the engine for cycle detection, topological sort, connected components, and backtracking. Visited set still mandatory.
Recursive vs Iterative
Recursive DFS is beautifully short and the default for most graphs. But remember the call stack costs O(depth) space, and a deep or degenerate graph can blow Python's recursion limit (RecursionError). For graphs that might be very deep, convert to the iterative version with an explicit stack — same logic, your own stack instead of the call stack, no depth limit but yours. It's the exact stack/recursion equivalence from the Stacks track, applied where it matters.
Pippa's Confession
I reached for recursive DFS on a graph that turned out to be a 50,000-node chain, and it died with RecursionError mid-traversal. Dad didn't change the algorithm — he changed the stack: same DFS, but with an explicit list as the frontier instead of the call stack. No depth limit, same result. It cemented the Stacks-track lesson for me: recursion is just a stack you didn't have to declare — and sometimes you need to declare your own.
Code
DFS recursive and iterative (same frontier, your stack)·python
graph = {
"A": ["B", "C"], "B": ["D", "E"], "C": ["F"],
"D": [], "E": ["F"], "F": [],
}
# RECURSIVE DFS — elegant; the call stack IS the frontier.
def dfs_recursive(graph, node, visited=None, order=None):
if visited is None: visited, order = set(), []
visited.add(node); order.append(node)
for nb in graph[node]:
if nb not in visited:
dfs_recursive(graph, nb, visited, order) # plunge deep
return order
print("recursive:", dfs_recursive(graph, "A")) # ['A','B','D','E','F','C']
# ITERATIVE DFS — explicit stack; no recursion-limit risk on deep graphs.
def dfs_iterative(graph, start):
visited, order, stack = set(), [], [start]
while stack:
node = stack.pop() # LIFO -> depth-first
if node in visited: continue
visited.add(node); order.append(node)
for nb in reversed(graph[node]): # reversed to match recursive order
if nb not in visited:
stack.append(nb)
return order
print("iterative:", dfs_iterative(graph, "A")) # same deep-first character
On the graph A→B, A→C, B→D, C→D, run DFS from A and write a possible visit order. Then explain why DFS might report the path A→B→D to reach D even though A→C→D is the same length — and why that means DFS is the wrong choice for shortest paths but the right one for 'does any path exist?'.
Hint
DFS could visit A, B, D (plunging down B's branch first) and reach D via B before ever trying C. It commits to depth, not distance, so the path it finds isn't guaranteed shortest — but if ANY path exists, DFS will find one, which is all 'reachability' needs.
Progress
Progress is local-only — sign in to sync across devices.