Card 03/ 10
Depth-First Search: Following One Path Until It Ends
A stack, or the call stack, goes as deep as it can before it backs up and tries the next neighbour.
Depth-first search visits every vertex a start vertex can reach by always moving to an unvisited neighbour of the latest vertex, and backing up only when there is none. Where breadth-first search keeps a queue, depth-first search keeps a stack: usually the call stack of a recursive function, or an explicit stack in a loop. This card traces it with three colours, compares its order with breadth-first search, and shows where recursion runs out.
The three colours record where each vertex stands. White means not yet seen, grey means on the current path, entered and not yet finished, and black means finished, with every neighbour explored. The recursive form is three lines: colour the vertex grey, visit each white neighbour in turn, then colour the vertex black. The steps below run it from A on the topic's graph, the six vertices A to F with neighbours in alphabetical order, as a run printed it.
Depth-first search from A, with the path on the stack and each vertex's colour
Enter A
A turns grey and is the only vertex on the stack.
stack: A
colours: A grey, B white, C white, D white, E white, F white
order: AEnter B
B is A's first neighbour and is white, so the search goes to B at once, before it ever looks at C.
stack: A B
colours: A grey, B grey, C white, D white, E white, F white
order: A BEnter D
B's neighbours are A, which is grey, and D, which is white.
stack: A B D
colours: A grey, B grey, C white, D grey, E white, F white
order: A B DEnter C
D's first white neighbour is C, so C is reached through D, three edges from A, although it is one edge from A directly.
stack: A B D C
colours: A grey, B grey, C grey, D grey, E white, F white
order: A B D CEnter E
C's neighbours A and D are grey, and E is white.
stack: A B D C E
colours: A grey, B grey, C grey, D grey, E grey, F white
order: A B D C EEnter F
F is the last white vertex. The path from A now holds every vertex.
stack: A B D C E F
colours: A grey, B grey, C grey, D grey, E grey, F grey
order: A B D C E FFinish F to A
F has no white neighbour, so it turns black and leaves the stack. The same holds for E, C, D, B and A in turn, and the search ends with every vertex black.
stack: (empty)
colours: A black, B black, C black, D black, E black, F black
order: A B D C E FDepth-first search visits A B D C E F where breadth-first search visits A B C D E F. Both visit every reachable vertex in O(V + E) time; the difference is the order, and the order is what each one is used for. Breadth-first search's order follows distance. Depth-first search's order follows paths, and the moments it finishes vertices are what two later ideas stand on: Detecting a Cycle in a Directed Graph With Three Colours, and the topic Topological Sort.
The recursive form has a limit in Python. The call stack holds one frame per grey vertex, and Python stops at 1,000 frames by default. A run on a path of 5,000 vertices, each joined to the next, raised RecursionError after 999 vertices. The same search with an explicit list as the stack visited all 5,000: push the start, and until the stack is empty, pop a vertex, skip it if visited, mark it, and push its unvisited neighbours. Java and TypeScript limit the call stack too, by its size in memory rather than a count, so a deep enough graph fails there as well.
- Time
- O(V + E)
- each vertex is entered once, and each adjacency list read once
- Extra space
- O(V)
- the colours, and a stack as deep as the longest path the search follows
- Python recursion limit
- 1,000 frames
- the default in Python 3.14; past it, use an explicit stack
← → move through sections and cards