Diving before backtracking
Depth first search, or DFS, plunges as deep as possible along one branch before backing up to try alternatives. You can implement it with explicit recursion or an explicit stack. Either way, each vertex is marked visited once so the search never loops forever.
Discovery and finish times
A powerful idea in DFS is tracking when a vertex is first entered and when its exploration finishes. These timestamps reveal the tree structure of the search and classify edges as tree, back, forward, or cross edges.
Common applications
- Topological ordering of a directed acyclic graph using finish times.
- Cycle detection by spotting back edges to a vertex still on the recursion stack.
- Connected components in undirected graphs, one DFS sweep per component.
- Path existence between two vertices.
DFS uses memory proportional to the depth of recursion, which can be modest, but very deep graphs risk a stack overflow when using language level recursion. Switching to an explicit stack avoids that limit.
Key idea
DFS explores one branch fully before backtracking, and its discovery and finish times power topological sorting, cycle detection, and component analysis.