Depth-first search

Depth-first search is a graph search that follows a branch as far as it can before returning to try the next unexplored branch. Starting at a vertex $s$ of an undirected graph on a finite set of vertices, mark $s$ as discovered. Scan its graph neighbours in a fixed order: for each undiscovered vertex, record the current vertex as its parent in a rooted tree in the discovery tree, mark the new vertex, and explore it immediately using recursion. Return when its adjacency list is exhausted. Discovery marks persist after return, preventing a graph cycle from causing repeated exploration. This branch-and-return rule is the maze exploration described in MIT's notes. ^[ref]

Use the same unweighted undirected graph as breadth-first search, with vertex set $V=\{A,B,C,D,E,F,G\}$ and edgeswhere $XY$ denotes the unordered pair $\{X,Y\}$. Visit graph neighbours in lexicographic order of their one-letter labels, starting at $A$. The discovery order, computed by the diagram's generator, isThe discovery edges in order are $AB,BD,BE,EC,CF,FG$. They form a rooted tree spanning the reached vertices, with root of a tree $A$. The other edges, $AC$ and $EG$, remain in the original graph but never discover a new vertex. In particular, the graph cycle $A,B,E,C,A$ causes no repeated discovery.

At $D$ there is no undiscovered graph neighbour, so its call returns to $B$. The next call enters $E$, then $C$, then $F$, then $G$. Immediately after discovering $G$, the call stack is $A,B,E,C,F,G$, with $G$ on top; $D$ is still discovered but its call has finished. The maximum call stack depth is six, although seven vertices are discovered. Following the recorded parent in a rooted tree backwards at each step reconstructs a graph path; here the route from $A$ to $G$ is $A,B,E,C,F,G$, using five edges. Breadth-first search instead finds $A,B,E,G$, using three edges. Depth-first search establishes reachability but does not guarantee the fewest edges.

An explicit LIFO stack can replace recursion, but its entries and discovery rule must be specified. To reproduce this exact traversal, store one frame per active vertex, retaining the next position in its adjacency list. Advance the top frame by one graph neighbour; if that vertex is undiscovered, mark it and push its frame immediately; pop an exhausted frame. Pushing all undiscovered graph neighbours at once and marking them on push is a different iterative variant. Even pushing them in reverse lexicographic order does not generally reproduce the parent in a rooted tree relationships above: $C$ would already be marked while processing $A$, so $E$ could not discover $C$.

With an adjacency list representation, constant-cost discovery checks and frame operations, and the graph neighbours already ordered, depth-first search has time complexity $O(|V|+|E|)$ in Big O notation. Each reached vertex is entered once and each incident edge is examined at most twice in an undirected graph; initializing all discovery marks costs $O(|V|)$. The call stack has depth at most $|V|$, since no active vertex repeats. Discovery marks and the recorded parent in a rooted tree for each nonroot vertex also need $O(|V|)$ auxiliary space complexity, excluding storage for the graph. Sorting adjacency lists to obtain a chosen order is additional work. ^[ref]

One start explores only its connected component of a graph. To cover a disconnected graph, start again at every still-undiscovered vertex while keeping all discovery marks; the discovery trees form a forest. Depth-first search is useful for reachability, constructing a spanning tree of a connected graph, and organizing the return steps needed by a depth-first traversal of a tree. For detecting a graph cycle in a simple graph that is an undirected graph, an edge to an already discovered vertex other than the current parent in a rooted tree closes a graph cycle; the immediate return edge to that parent in a rooted tree is not itself a graph cycle.

// Target: computer-science.bigb