One corridor to the end
Depth-First Search
The analogy
In a maze you pick a corridor and follow it as far as it goes. Dead end? Back up to the last junction and take the next corridor. DFS commits to a path completely before considering alternatives.
Visualizer
One corridor to the end
step 1 / 15Start at A. A stack holds where to go next — last in, first out.Stack: A
📖 In depth — the full reference
DFS — everything worth knowing
| fact | value | note |
|---|---|---|
| time / space | O(V + E) / O(V) | same touch-count as BFS; the ORDER differs, not the cost |
| data structure | STACK — explicit, or the call stack via recursion | recursion IS DFS borrowing the machine's stack |
| guarantee | reaches everything reachable | but paths found are NOT shortest — that is BFS's job |
| superpowers | cycle detection, topological sort, connected components, maze solving, backtracking | Modules 6–7 are built on these |
| memory vs BFS | O(depth) vs O(width) | deep narrow graph → DFS cheap; shallow wide → BFS queue explodes |
| recursion depth limit | deep graphs overflow the call stack | iterative stack version is immune — know both |
| three colours | unvisited / in-progress / done | an edge to an IN-PROGRESS node = a cycle (the deadlock detector) |
Python: recursive and iterative DFS
import sys
# sys.setrecursionlimit(200000) # default ~1000 frames — deep graphs need more
def dfs(adj, start, seen=None, order=None):
seen = seen if seen is not None else set() # never a mutable default!
order = order if order is not None else []
seen.add(start)
order.append(start)
for nb in adj[start]:
if nb not in seen:
dfs(adj, nb, seen, order)
return order
# Iterative twin — no depth limit (reverse neighbours to match recursive order):
def dfs_iter(adj, start):
order, seen, stack = [], set(), [start]
while stack:
node = stack.pop()
if node in seen: continue
seen.add(node)
order.append(node)
stack.extend(reversed(adj[node]))
return orderdef dfs(adj, start):
seen, stack, order = set(), [start], []
while stack:
v = stack.pop() # LIFO
if v in seen:
continue
seen.add(v)
order.append(v)
stack.extend(adj[v])
return orderCheck yourself
Which finds the shortest unweighted path?
Practice — write it yourself
dfs_order(adj, start): one corridor to the end — recurse into each unseen neighbour IN LIST ORDER before moving to the next. Return the visit order.
Python 3 · runs in your browser · your draft is saved locally
📝 My notessaved in this browser