Going deep first
Depth first search explores a graph or tree by plunging as far as possible along one path before backing up to try alternatives. It suits problems about connectivity, cycle detection, path existence, and exhaustive enumeration where reaching the bottom of a branch matters.
Recursion or an explicit stack
DFS has two equivalent forms.
- The recursive form calls itself on each unvisited neighbor, letting the call stack remember where to resume.
- The iterative form uses an explicit stack, pushing neighbors and popping the most recent first.
Either way you mark a node visited the moment you reach it, then recurse or push its unvisited neighbors. Marking prevents revisiting and protects against infinite loops in graphs with cycles.
Pre and post order moments
DFS gives two useful hooks. Work done before recursing into children is pre order, good for recording discovery. Work done after children finish is post order, which drives cycle detection coloring, topological ordering, and computing values that depend on subtrees.
Key idea
DFS dives along one path using recursion or a stack, marks nodes visited to avoid loops, and offers pre order and post order hooks for different kinds of work.