Depth-First Search

A graph $G = (V, E)$ can be represented as an Adjacency List or an Adjacency Matrix; DFS works with either, though the adjacency list gives the better running time. Depth-first search explores $G$ by starting at a vertex $u$, marking it visited, and then recursively exploring one unvisited neighbor of $u$ at a time. When a call returns — because the current vertex has no more unvisited neighbors — the algorithm backtracks to the vertex that called it, and continues searching that vertex's remaining neighbors. This is precisely a preorder-style traversal of the recursion tree, generalized from trees to arbitrary graphs (which may contain cycles and multiple paths between vertices). Because a graph need not be connected, DFS is normally run as an outer loop over all vertices: for every vertex not yet visited, start a fresh DFS call from it. Each such call produces a DFS tree rooted at the starting vertex, consisting of the tree edges — the edges $(u, v)$ traversed when $v$ is first discovered from $u$. The union of all DFS trees produced by the outer loop is the DFS forest. Every edge of $G$ that is not a tree edge is classified, in the fuller treatment of DFS, as a back, forward, or cross edge depending on the relationship between the endpoints in the forest — this classification is the subject of DFS Edge Classification and Timestamps, but even without timestamps, the forest itself already reveals connectivity structure: the number of DFS trees equals the number of connected components (undirected case) or gives partial information about reachability (directed case). The key mechanical device that makes DFS well-defined and efficient is a visited (or color) marker per vertex, checked before recursing. Without this marker, DFS would loop forever on any graph containing a cycle, since it would keep re-entering already-explored vertices. With it, each vertex is entered into the "currently being explored" state exactly once, guaranteeing termination and linear work.

DFS can be written recursively (using the language's call stack) or iteratively (using an explicit stack data structure). The recursive form is the clearest expression of the "commit fully, then backtrack" idea, so we present it first, then give the iterative variant that avoids recursion-depth limits.

Recursive DFS. Each vertex has a color: `WHITE` (undiscovered), `GRAY` (discovered, still being explored), or `BLACK` (finished, all neighbors explored). The outer procedure loops over all vertices so that disconnected components are all covered. ``` DFS(G): for each vertex u in G.V: color[u] = WHITE parent[u] = NIL time = 0 forest = [] # list of trees, one per component for each vertex u in G.V: if color[u] == WHITE: tree = new empty tree rooted at u DFS-VISIT(G, u, tree) forest.append(tree) return forest, parent DFS-VISIT(G, u, tree): color[u] = GRAY # u is discovered time = time + 1 discovery[u] = time tree.add(u) for each v in G.adj[u]: # examine every outgoing edge (u, v) if color[v] == WHITE: parent[v] = u tree.add_edge(u, v) # (u, v) becomes a tree edge DFS-VISIT(G, v, tree)

# else: v already discovered — edge is non-tree (back/forward/cross) color[u] = BLACK # u is finished time = time + 1 finish[u] = time ``` The `discovery` and `finish` timestamps are included here because they cost nothing extra and are exactly the hooks used by later algorithms (cycle detection, topological sort, strongly connected components); a plain reachability-only DFS can omit them and simply track `color`.

Iterative DFS (explicit stack). Recursion depth in the recursive version can reach $O(V)$ in the worst case (a long path), which can overflow a language's call stack for very large graphs. An explicit-stack version avoids this: ``` DFS-ITERATIVE(G, s): for each vertex u in G.V: color[u] = WHITE stack = empty stack stack.push(s) while stack is not empty: u = stack.peek() if color[u] == WHITE: color[u] = GRAY # discover u advanced = false for each v in G.adj[u]: # find next unvisited neighbor if color[v] == WHITE: parent[v] = u stack.push(v) advanced = true break if not advanced: color[u] = BLACK # all neighbors explored: finish u stack.pop() ``` This iterative version simulates the same recursion tree: the explicit stack holds exactly the path from the current vertex back to the root, mirroring the call stack of the recursive version. Its subtlety is that `G.adj[u]` must be scanned incrementally (skipping already-tried neighbors) rather than restarted from scratch each time `u` is revisited, or the running time degrades; a standard fix is to store, per vertex, an iterator/index into its adjacency list. The figure below shows a directed graph and the DFS forest produced by running `DFS` starting the outer loop at vertex A (assuming adjacency lists list neighbors alphabetically).

Reading the figure: DFS starts at A (discovery time 1), goes to B, then to C (a dead end after one edge, so C finishes quickly at time 4), backtracks to B, descends to D, then to F, then to E (another dead end), and finally the edge F → A is discovered but A is already `GRAY`/finished-ancestor, so it is not a tree edge — it is a back edge, drawn dashed, indicating a cycle in the original graph.

Time complexity. With an adjacency-list representation, `DFS-VISIT` is called exactly once per vertex, because the `color[u] == WHITE` check in the outer loop and in the neighbor loop guarantees a vertex is never entered twice. Inside each call, the `for each v in G.adj[u]` loop scans u's adjacency list once. Summing over all vertices, the total work done scanning adjacency lists is

(for a directed graph; for undirected graphs each edge appears in two adjacency lists, still $\Theta(E)$ overall since constants don't affect asymptotic order). The bookkeeping per vertex (coloring, timestamping) is $\Theta(1)$, contributing $\Theta(V)$ total. Hence:

This is optimal in the sense that any algorithm must at least read the input graph, which already takes $\Omega(V + E)$ time. If instead an Adjacency Matrix is used, checking a vertex's neighbors takes $\Theta(V)$ time regardless of actual degree, giving $\Theta(V^2)$ total — a real cost, which is why adjacency lists are preferred for sparse graphs.

Space complexity. DFS uses $\Theta(V)$ auxiliary space: the color array, the parent array, and (for the recursive version) the call stack, whose depth is bounded by the longest root-to-leaf path in the DFS tree, at most $V$. The iterative version's explicit stack is likewise bounded by $O(V)$ vertices, since each vertex is pushed at most once. Storing the forest itself (parent pointers, timestamps) is also $\Theta(V)$.

Correctness. The central claim is: `DFS(G)` visits every vertex exactly once, and every edge is examined exactly once (per direction), producing a well-defined forest. The proof proceeds by strong induction on the order of `DFS-VISIT` calls, using the color invariant:

• Invariant. At any point during execution, `WHITE` vertices are undiscovered, `GRAY` vertices are ancestors of the currently executing call on the recursion stack (i.e., currently "open"), and `BLACK` vertices are fully finished — every vertex reachable from them via unexplored edges has already been discovered.

Base case: before any call, all vertices are `WHITE`, satisfying the invariant vacuously. Inductive step: when `DFS-VISIT(G, u, tree)` is called, `u` was `WHITE` (guaranteed by the caller's check), so `u` was undiscovered — consistent with the invariant. Immediately, `u` is colored `GRAY`, correctly marking it as newly opened. For each neighbor $v$: if $v$ is `WHITE`, the invariant guarantees $v$ was truly undiscovered, so recursing into it is safe and it becomes a new tree edge child of $u$; if $v$ is `GRAY` or `BLACK`, it has already been (or is being) discovered elsewhere, so skipping it is correct — re-entering it would violate "each vertex visited once" and would in fact loop forever on a cyclic graph if the check were omitted. After all neighbors are exhausted, `u` is colored `BLACK`, correctly marking it finished, matching the invariant that a finished vertex has no more work. Termination: every recursive call strictly decreases the number of `WHITE` vertices by at least one (the vertex it discovers), and there are finitely many vertices, so the recursion cannot proceed forever. The outer loop's `for each vertex u` similarly runs $|V|$ times, calling `DFS-VISIT` only on still-`WHITE` vertices, guaranteeing all components are covered exactly once. Since each edge $(u,v)$ is examined exactly once (when scanning `adj[u]`), and colored consistently by the invariant, the forest produced has exactly $|V|$ vertices, each with a well-defined parent (or none, if a tree root), and the tree-edge set is acyclic by construction — parent pointers always point from a `GRAY` vertex to a freshly-discovered `WHITE` vertex, never creating a cycle among tree edges. $\blacksquare$

Honest tradeoffs. DFS gives no shortest-path guarantee — unlike Breadth-First Search, the tree-path from the root to a vertex in a DFS tree can be far longer than the true shortest path, since DFS commits to depth over breadth. Recursive DFS is elegant but risks stack overflow on graphs with very long paths (e.g., a graph that is essentially a chain of $10^6$ vertices); the iterative version trades code clarity for robustness. Finally, plain DFS (without timestamps) only tells you reachability and forest structure — extracting cycle information, topological order, or strongly connected components requires the timestamp/classification machinery layered on top, covered in DFS Edge Classification and Timestamps.

Consider the directed graph from the figure, with adjacency lists (neighbors listed in alphabetical/insertion order):

Run `DFS(G)`, outer loop visiting vertices in order A, B, C, D, E, F.

The result: a single DFS tree (the graph is connected via directed reachability from A), with tree edges A→B, B→C, B→D, D→F, F→E, and exactly one non-tree edge, F→A, discovered while A was still an open ancestor (`GRAY`) — this is the hallmark of a back edge, which (as elaborated in DFS Edge Classification and Timestamps) certifies that the directed graph contains a cycle: A→B→D→F→A. Notice the parenthesis structure of the timestamps: $[d[A], f[A]] = [1,12]$ properly contains $[d[B], f[B]] = [2, 11]$, which properly contains $[d[C], f[C]] = [3,4]$ and $[d[D], f[D]] = [5, 10]$, which contains $[d[F], f[F]] = [6, 9]$, which contains $[d[E], f[E]] = [7, 8]$ — this nesting is not a coincidence but a theorem (the parenthesis theorem) that always holds for DFS timestamps, since a vertex's interval exactly spans the time its subtree is being explored.

Depth-first search as a systematic algorithmic technique — with the formal color/timestamp machinery, complexity analysis, and its use as a subroutine for planarity testing, biconnectivity, and strong connectivity — was crystallized by Robert Tarjan and John Hopcroft in the early 1970s, building on maze-traversal ideas that predate computing (the "Trémaux" wall-following strategy for solving mazes, and Charles Pierre Trémaux's 19th-century graph-traversal rule, are often cited as an intellectual ancestor). Their work turned an intuitive backtracking heuristic into a rigorously analyzed $O(V+E)$ algorithm with a battery of powerful applications.

Compilers and build systems (such as `make`, Bazel, and package managers like `npm` or `pip`) run DFS-based cycle detection over dependency graphs to reject circular dependencies, and DFS-based Topological Sort to compute a valid build/install order. Garbage collectors in managed-memory runtimes (JVM, .NET CLR, V8) use an iterative, stack-based DFS (or its close cousin, mark-and-sweep tracing) to identify all objects reachable from root references. Version control systems and file-system tools use DFS to walk directory trees. Maze-generation and maze-solving code in games literally implements the "commit and backtrack" idea directly. Network tools use DFS-style traversal to enumerate reachable hosts or to detect cycles in routing/dependency graphs. Static analyzers and IDEs use DFS over control-flow or call graphs to detect infinite recursion, unreachable code, or circular imports. In each case, the appeal is the same property proved above: linear-time, low-memory exploration that leaves behind a forest rich enough to answer deeper structural questions.

Ask the tutor: How do discovery and finish timestamps let DFS detect cycles and compute a topological order?