Depth first search
Depth first search or DFS explores a graph by going as deep as possible along one branch before backing up. From the current vertex it picks an unvisited neighbor, moves there, and repeats. When a vertex has no unvisited neighbors, DFS backtracks to the previous vertex and tries another branch.
Stack or recursion
DFS is driven by a stack, which can be the program's call stack when written recursively or an explicit stack when written iteratively.
- Mark a vertex visited when you first reach it.
- Recurse into each unvisited neighbor.
- Returning from recursion is the backtrack step.
What DFS reveals
DFS is the foundation for many graph algorithms. The order in which vertices finish their recursion supports topological sorting, cycle detection, and finding connected components. It does not by itself find shortest paths because it commits to deep branches rather than exploring by distance.
A single DFS visits every vertex and edge a constant number of times, so it runs in time proportional to the graph size.
Key idea
DFS plunges down one branch using a stack and backtracks, forming the backbone of cycle detection, topological sort, and component finding.