Follow one branch while remembering where to return
Depth-first search, or DFS, moves from the current vertex to an undiscovered neighbor and continues deeper. When it cannot proceed, it returns to an earlier branch and examines the remaining choices. Recursion stores those return points in the call stack; an iterative implementation uses an explicit stack. Neighbor order affects the visitation sequence and search-tree shape, but correct discovery tracking still finds the vertices reachable from the start. DFS does not promise to visit vertices in increasing shortest-path distance, so its first discovered path need not be a shortest one.
Trace the return from a dead end
Take edges A → B, A → C, and B → D, and inspect B first at A. The traversal discovers A, B, and D. With no undiscovered neighbor from D, it returns to B, then to A, before examining C. Processing a vertex when first entered is preorder; processing it after its descendants finish is postorder. These events serve different purposes. A path-search task may care about the active path, whereas dependency ordering often uses completion events. An iterative translation must preserve the relevant event rather than assuming that every use only needs a visitation list.
Distinguish active ancestors from finished vertices
For cycle detection in a directed graph, a common DFS records three states: undiscovered, active, and finished. An edge to an active ancestor reveals a directed cycle. An edge to a vertex whose exploration has already finished does not by itself prove a cycle. The graph A → B, A → C, C → B is acyclic even though C can encounter an already visited B. Treating every edge to any visited vertex as a cycle therefore gives false alarms. Undirected graphs require their own handling of the edge back to the parent.
Bound the work and control recursion depth
With adjacency lists, discovering each vertex once and examining each edge a constant number of times gives O(V + E) total time. Discovery state and the stack require O(V) auxiliary space. A long chain can produce recursion depth proportional to the number of vertices, potentially exceeding a language’s recursion limit or the available call stack. An explicit stack avoids that particular call-stack constraint but must retain enough state for the task, especially if finish times matter. Reverse postorder gives a topological order only when the directed graph is acyclic; validate that precondition rather than silently applying the rule to a cyclic graph.