Depth-first search (DFS) traverses a graph by following one path as far as possible, then backtracking to the previous branching point. Like exploring a maze, it continues until reaching a dead end before choosing another route. Unlike breadth-first search, DFS is not designed to find shortest paths; it is useful for understanding graph structure and visiting vertices broadly. section 14.3.4 section 14.3.5
A recursive DFS maintains the traversal state through a call stack:
- For a complete traversal, restart DFS from each still-unvisited vertex; one start may not reach every component. section 14.3.4
Choosing a traversal
Starting DFS at v1 produces one depth-oriented visitation order. Starting at v4 may leave vertices v1–v3 unreachable when the graph contains separate strongly connected components, so a later restart is required. Entry and exit times record when each vertex is entered and completed.
