Descending before backtracking
After visiting a vertex, depth-first search descends into an unvisited neighbor before returning to try another. Recursive calls retain unfinished positions, while an explicit stack can store corresponding traversal state.
Marking a vertex on entry prevents cycles and alternative routes from causing endless revisits. A discovered mark does not mean that all descendant work has finished. Entry and completion are distinct events used by later structural analyses.
Building reachability evidence and forests
Recording first-discovery predecessors recovers an actual path from the source to a reached vertex. Because exploration follows one branch deeply, the first path can be circuitous. Minimum-edge paths in an unweighted graph generally call for breadth-first search instead.
For a disconnected graph, restarting at unmarked vertices creates a search forest. In an undirected graph this can label connected components. Mutual reachability in directed graphs needs additional strongly connected-component analysis.
Entry and completion orders serve different purposes
Recording before recursive calls yields preorder; recording after descendant processing yields postorder. Reversing postorder gives a topological ordering in a directed acyclic graph. Both the acyclic condition and completion order are essential to that result.
Adjacency-list traversal takes O(V+E) time on a finite graph. Recursion depth can follow a long search branch and approach the number of vertices, so deep inputs require attention to call-stack capacity or an explicitly managed stack.