= Depth-first search
{wiki}
= DFS
{c}
{synonym}
<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. <6.006 Introduction to Algorithms, Fall 2011 by Massachusetts Institute of Technology, 6.006 course staff/Lecture 14: Graphs II: Depth-First Search>[MIT 6.006, lecture 14: depth-first search, pp. 2–3]{ref}
Use the same unweighted <undirected graph> as <breadth-first search>, with <vertex set> $V=\{A,B,C,D,E,F,G\}$ and <edges>
$$
E=\{AB,AC,BD,BE,CE,CF,EG,FG\},
$$
where $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, is
$$
A,B,D,E,C,F,G.
$$
The 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.
\Image[/depth-first-search-stack.png]
{title=<Depth-first search>: discovery <edges> and the active <call stack> on seven <vertices>}
{description=Numbers show first-discovery order. Solid <edges> form the discovery <tree>; dashed <edges> belong only to the original <graph>. The right panel shows the <call stack> from oldest call to current call, including the return from $D$ before entering $E$.}
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. https://raw.githubusercontent.com/kevin-wayne/algs4/master/src/main/java/edu/princeton/cs/algs4/DepthFirstPaths.java[Sedgewick and Wayne, Algorithms: DepthFirstPaths discovery marks and resource bounds]{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
Back to article page
