--- title: Depth-First Search module: Graphs moduleNumber: 6 lessonNumber: 2 order: 602 summary: | Swap BFS's queue for a stack and the search plunges instead of fanning out. Depth-first search stamps every vertex with discovery and finish times that nest like parentheses, classifies each edge as tree, back, forward, or cross, and — through the back edge — decides in one pass whether a graph has a cycle. These timestamps underpin topological sort, strong connectivity, and the rest of this module. topics: [Graph Traversal, Depth-First Search] sources: - book: CLRS ref: "Ch. 22 — Elementary Graph Algorithms" - book: Erickson ref: "Ch. 6 — Graph Search" - book: Skiena ref: "§5 — Graph Traversal" practice: - title: 'Clone Graph' slug: clone-graph difficulty: Medium - title: 'Course Schedule' slug: course-schedule difficulty: Medium - title: 'Number of Islands' slug: number-of-islands difficulty: Medium --- This builds on [Graph Representations and Traversal](/algorithms/graphs/representations-and-traversal), which set up graphs, the two representations, and the $\textsc{Whatever-First-Search}$ skeleton read with a queue as breadth-first search. Here we read the same skeleton with a **stack**, and the change of order exposes an entirely different structure. ## Depth-first search Where BFS fans out in rings, **depth-first search** (DFS) plunges. It is Whatever-First-Search with a **stack**: pulling the _newest_ discovered vertex means we always descend from where we just were. From a vertex it follows an edge to an unvisited neighbor, then a neighbor of _that_, going as deep as possible before **backtracking** to the most recent vertex with an unexplored edge. The LIFO stack is usually left implicit — it _is_ the recursion call stack. DFS produces a pair of **timestamps** on each vertex $v$: a _discovery_ (or _start_) time, which we write $s_v$, stamped when $v$ first turns gray, and a _finish_ time $f_v$, stamped when $v$ turns black after all its descendants are done. A single global clock $time$ ticks once per stamp, so on $n$ vertices every value in $1, 2, \dots, 2n$ is used exactly once. Unlike BFS, the outer driver restarts DFS from any leftover white vertex, so it covers disconnected pieces too, producing a **depth-first forest** rather than a single tree. ```algorithm caption: $\textsc{DFS}(G)$ — discovery / finish times for every vertex number: 4 foreach vertex $u \in V$ do $u.color \gets \text{white}$ $u.\pi \gets \text{nil}$ $time \gets 0$ foreach vertex $u \in V$ do if $u.color = \text{white}$ then call $\textsc{DFS-Visit}(G, u)$ ``` ```algorithm caption: $\textsc{DFS-Visit}(G, u)$ — explore everything reachable from $u$ number: 5 $time \gets time + 1$ $u.s \gets time$ // discover u (turns gray) $u.color \gets \text{gray}$ foreach $v$ adjacent to $u$ do if $v.color = \text{white}$ then $v.\pi \gets u$ call $\textsc{DFS-Visit}(G, v)$ $u.color \gets \text{black}$ $time \gets time + 1$ $u.f \gets time$ ``` Like BFS, DFS runs in $\Theta(V + E)$: the initialization and the outer loop cost $\Theta(V)$, and $\textsc{DFS-Visit}$ is called exactly once per vertex (only on white vertices, which it immediately grays), scanning each adjacency list once for $\Theta(E)$ total. ::impl{algo="depth_first_search"} ### A worked DFS, and the parenthesis structure Run $\textsc{DFS}$ on the digraph below. The outer loop scans vertices in the order $s, w, y, x, z, t, q, r$, and each adjacency list is scanned alphabetically. The clock ticks once per stamp: - $t{=}1$: discover $s$. Its list is $w, z$; the first neighbor $w$ is white. - $t{=}2$: discover $w$ (so $w.\pi = s$). Its list is $y, z$; $y$ is white. - $t{=}3$: discover $y$. Its only neighbor $x$ is white. - $t{=}4$: discover $x$. No white neighbors. - $t{=}5$: finish $x$. $\;$ $t{=}6$: finish $y$ — back in $w$, whose next neighbor $z$ is still white. - $t{=}7$: discover $z$. Its list is $s, x$: $s$ is **gray** (an active ancestor), $x$ is **black** — neither is entered, but both edges get classified below. - $t{=}8$: finish $z$. $\;$ $t{=}9$: finish $w$ — back in $s$, whose remaining neighbor $z$ is now black. - $t{=}10$: finish $s$. The outer loop resumes and finds $t$ still white. - $t{=}11$: discover $t$; $t{=}12$/$13$: discover and finish $q$; $t{=}14$/$15$: discover and finish $r$ (its neighbor $q$ is black); $t{=}16$: finish $t$. Each vertex below is labeled with its interval as _discovery/finish_. Thick edges are **tree edges** (the depth-first forest — two trees here, rooted at $s$ and $t$); dashed edges are the non-tree edges, tagged B (back), F (forward), or C (cross) and classified in the next section. $$ % caption: DFS forest on a digraph with discovery/finish times and non-tree edges tagged % B (back), F (forward), C (cross). \begin{tikzpicture}[ >=Stealth, V/.style={ellipse, draw, minimum width=13mm, minimum height=8mm, font=\small, inner sep=1pt}, tree/.style={->, very thick}, nontree/.style={->, black, dashed}, lab/.style={font=\scriptsize, black}] \node[V] (s) at (3.0,4.6) {$s$~ 1/10}; \node[V] (w) at (3.0,3.0) {$w$~ 2/9}; \node[V] (y) at (4.4,1.5) {$y$~ 3/6}; \node[V] (x) at (4.4,0) {$x$~ 4/5}; \node[V] (z) at (1.4,1.5) {$z$~ 7/8}; \node[V] (t) at (7.6,4.6) {$t$~ 11/16}; \node[V] (q) at (6.6,3.0) {$q$~ 12/13}; \node[V] (r) at (8.8,3.0) {$r$~ 14/15}; % tree edges \draw[tree] (s) -- (w); \draw[tree] (w) -- (y); \draw[tree] (y) -- (x); \draw[tree] (w) -- (z); \draw[tree] (t) -- (q); \draw[tree] (t) -- (r); % non-tree edges \draw[nontree] (s) -- node[pos=0.55, left=1pt, lab] {F} (z); \draw[nontree] (z) to[bend left=45] node[pos=0.5, left=1pt, lab] {B} (s); \draw[nontree] (z) to[bend right=12] node[pos=0.5, below=3pt, lab] {C} (x); \draw[nontree] (r) -- node[pos=0.5, below=1pt, lab] {C} (q); \end{tikzpicture} $$ The discovery and finish times nest like balanced parentheses. Write each vertex's **interval** $[s_v,\, f_v]$. Reading the trace above as brackets — open at discovery, close at finish — gives $$ \big(_s \big(_w \big(_y \big(_x \big)_x \big)_y \big(_z \big)_z \big)_w \big)_s \; \big(_t \big(_q \big)_q \big(_r \big)_r \big)_t $$ a well-formed string: intervals can never _partially_ overlap. This is the **parenthesis theorem** (Erickson calls it the nesting lemma).[^erickson-dfs] > **Theorem (Parenthesis theorem).** For any two vertices $u$ and $v$, exactly one of the > following holds: > > - the intervals $[s_u, f_u]$ and $[s_v, f_v]$ are **disjoint**, and neither > vertex is a descendant of the other (they are _incomparable_); or > - one interval **contains** the other, and the contained vertex is a > **descendant** of the container in the DFS forest. It makes the recursion visible. Drawing each interval $[s_v, f_v]$ as a bar along the time axis turns the forest into a literal stack of nested brackets — a bar sits _strictly inside_ another exactly when the inner vertex is a descendant of the outer: $$ % caption: DFS intervals $[s_v, f_v]$ drawn as bars on the time axis; one bar nesting % inside another marks a descendant. \begin{tikzpicture}[x=4.4mm, y=6.5mm] \definecolor{acc}{HTML}{2348F2} \foreach \x in {1,...,16} \node[font=\scriptsize, black!50] at (\x,0) {\x}; \draw[->, black!50] (0.4,0.5) -- (16.9,0.5) node[right, font=\scriptsize, black]{time}; \draw[line width=2pt] (1,1) -- (10,1) node[midway, above, font=\scriptsize, black]{$s$}; \draw[line width=2pt] (2,1.8) -- (9,1.8) node[midway, above, font=\scriptsize, black]{$w$}; \draw[line width=2pt] (3,2.6) -- (6,2.6) node[midway, above, font=\scriptsize, black]{$y$}; \draw[line width=2pt] (4,3.4) -- (5,3.4) node[midway, above, font=\scriptsize, black]{$x$}; \draw[line width=2pt] (7,2.6) -- (8,2.6) node[midway, above, font=\scriptsize, black]{$z$}; \draw[line width=2pt] (11,1.8) -- (16,1.8) node[midway, above, font=\scriptsize, black]{$t$}; \draw[line width=2pt] (12,2.6) -- (13,2.6) node[midway, above, font=\scriptsize, black]{$q$}; \draw[line width=2pt] (14,2.6) -- (15,2.6) node[midway, above, font=\scriptsize, black]{$r$}; \end{tikzpicture} $$ Above, $[s_x, f_x] = [4,5] \subset [3,6] = [s_y, f_y] \subset [2,9] = [s_w, f_w]$, so $x$ is a descendant of $y$ is a descendant of $w$. Two companions sharpen it. > **Theorem (White-path).** $v$ becomes a descendant of $u$ **if and only if**, at > the moment $u$ is discovered (time $s_u$), there is a path $u \rightsquigarrow > v$ consisting entirely of still-white vertices. This is the cleanest test for "what will end up under $u$." > **Theorem (Cycle).** Every back edge lies on a cycle, and every cycle contains at > least one back edge. Equivalently, a digraph is **acyclic iff DFS finds no back > edge**. This makes "look for a back edge" a decision test for cyclicity, and the two clauses are precisely its [soundness and completeness](/algorithms/foundations/what-is-an-algorithm). _Every back edge lies on a cycle_ is **soundness**: when DFS flags a back edge, a genuine cycle is there — no false alarm. _Every cycle contains a back edge_ is **completeness**: no cycle slips past the search. Together they underlie cycle detection and [topological sort](/algorithms/graphs/topological-sort-and-scc). ### Classifying edges As DFS traverses an edge $(u, v)$, the _color_ of $v$ at that moment reveals what kind of edge it is, a classification that drives the algorithms of the next lessons. In the worked digraph above: - **Tree edge.** $v$ is white: we set $v.\pi = u$, so the edge is $(v.\pi, v)$. We discover $v$ through this edge; it joins the depth-first forest (e.g. $s \to w$, $w \to y$). - **Back edge.** $v$ is **gray**, an ancestor of $u$ still on the recursion stack ($z \to s$, since $[s_z, f_z] \subset [s_s, f_s]$). _A digraph has a back edge iff it has a cycle_, the linchpin of cycle detection and topological sort. - **Forward edge.** $v$ is black and a _descendant_ of $u$ ($s \to z$: a non-tree edge to an already-finished descendant). - **Cross edge.** $v$ is black and _not_ a descendant of $u$ ($z \to x$, or the edge $r \to q$ between separate tree branches). The color test runs _during_ the traversal; once DFS finishes, the timestamps alone decide, courtesy of the parenthesis theorem. For an edge $(u, v)$: | Class | Interval relation | Color of $v$ when $(u,v)$ scanned | | --- | --- | --- | | tree / forward | $s_u < s_v < f_v < f_u$ | white / black | | back | $s_v \leq s_u < f_u \leq f_v$ | gray | | cross | $s_v < f_v < s_u$ | black | (Tree and forward edges share the interval pattern — $v$ a descendant of $u$ — and are told apart by $v.\pi = u$.) The fourth conceivable pattern, $s_u < s_v$ with $v$ finishing after $u$, never occurs for an edge: if $v$ is discovered while $u$ is active, the white-path property pulls $v$ into $u$'s subtree, so $v$ finishes first. A minimal example exhibiting all four classes: $$ % caption: All four edge classes on one small digraph. DFS starts at $u$, then restarts at % $x$; vertices show discovery/finish times. \begin{tikzpicture}[ >=Stealth, V/.style={ellipse, draw, minimum width=12mm, minimum height=8mm, font=\small, inner sep=1pt}, tree/.style={->, very thick}, nontree/.style={->, black, dashed}, lab/.style={font=\scriptsize, black}] \definecolor{acc}{HTML}{2348F2} \node[V] (u) at (0,0) {$u$~ 1/6}; \node[V] (v) at (2.6,0) {$v$~ 2/5}; \node[V] (w) at (5.2,0) {$w$~ 3/4}; \node[V] (x) at (8.4,0) {$x$~ 7/8}; \draw[tree] (u) -- node[pos=0.5, above=1pt, lab] {\texttt{tree}} (v); \draw[tree] (v) -- node[pos=0.5, above=1pt, lab] {\texttt{tree}} (w); \draw[nontree] (u) to[bend left=40] node[pos=0.5, above=1pt, lab] {\texttt{forward}} (w); \draw[nontree] (w) to[bend left=40] node[pos=0.5, below=1pt, lab] {\texttt{back}} (u); \draw[nontree] (x) to[bend right=32] node[pos=0.5, above=1pt, lab] {\texttt{cross}} (w); \end{tikzpicture} $$ DFS from $u$ walks the chain $u, v, w$; the edge $w \to u$ finds $u$ gray (back), and on the way out $u \to w$ finds $w$ black inside $u$'s interval (forward). The restart at $x$ finds $w$ black with $f_w < s_x$ (cross). In an **undirected** graph the picture simplifies: every edge is either a tree edge or a back edge, since forward and cross edges cannot occur, because exploring an edge from either endpoint reaches the other while it is still gray. ### Worked example: connected components The outer driver — restarting DFS from any leftover white vertex — labels **connected components** for free. Each restart begins a new tree, and every vertex it reaches shares the same component. Take an undirected graph on seven vertices with edges $a$–$b$, $b$–$c$, $a$–$c$ (a triangle), the lone edge $d$–$e$, and the isolated pair $f$–$g$. Scanning vertices alphabetically: - **Restart 1 at $a$** (component $1$). DFS visits $a$, then $b$, then $c$; from $c$ the edge $c$–$a$ finds $a$ gray, a back edge that closes the triangle but visits nothing new. Component $1 = \set{a, b, c}$. - **Restart 2 at $d$** (component $2$). DFS visits $d$, then $e$ across the single edge; $e$ has no other neighbor. Component $2 = \set{d, e}$. - **Restart 3 at $f$** (component $3$). DFS visits $f$, then $g$. Component $3 = \set{f, g}$. Three restarts, three components. The number of times the outer loop calls $\textsc{DFS-Visit}$ from a white vertex _is_ the number of connected components, computed in the same $\Theta(V + E)$ pass — no extra structure needed beyond a component counter incremented at each restart. $$ % caption: DFS labels connected components for free. Each restart of the outer loop from a % white vertex (arrowed) begins a new tree; here three restarts at $a$, $d$, $f$ % discover the three components $\{a,b,c\}$, $\{d,e\}$, $\{f,g\}$. \begin{tikzpicture}[font=\small, V/.style={circle, draw, minimum size=8mm, font=\small}, tree/.style={->, line width=1.1pt, draw=acc}, back/.style={-, black, dashed}] \definecolor{acc}{HTML}{2348F2} % component 1: triangle \node[V] (a) at (0,1.3) {$a$}; \node[V] (b) at (1.3,1.3) {$b$}; \node[V] (c) at (0.65,0.2) {$c$}; \draw[tree] (a) -- (b); \draw[tree] (b) -- (c); \draw[back] (c) -- (a); \node[font=\scriptsize, acc] at (0.65,-0.7) {comp 1}; % component 2: edge \node[V] (d) at (3.2,1.3) {$d$}; \node[V] (e) at (3.2,0.2) {$e$}; \draw[tree] (d) -- (e); \node[font=\scriptsize, acc] at (3.2,-0.7) {comp 2}; % component 3: pair \node[V] (f) at (5.2,1.3) {$f$}; \node[V] (g) at (5.2,0.2) {$g$}; \draw[tree] (f) -- (g); \node[font=\scriptsize, acc] at (5.2,-0.7) {comp 3}; \end{tikzpicture} $$ The dashed edge $c$–$a$ is the triangle's one back edge; every other edge is a tree edge, matching the undirected rule above. On a _directed_ graph the same restart-counting overcounts — reachability is one-way — the gap that [strongly connected components](/algorithms/graphs/topological-sort-and-scc) close with a second DFS pass. ## Common pitfalls Traversal code is short, and most of its bugs hide in the two lines everyone writes from memory. - **Marking visited at dequeue instead of enqueue.** If BFS checks the color only when a vertex _leaves_ the queue, a vertex can be enqueued once per incoming edge before its first copy is processed. Distances still come out right (the first copy dequeued carries the smallest $d$), but the queue swells to $\Theta(E)$ entries. Discover-time marking — gray the vertex the moment it is first seen — is what keeps "each vertex enqueued once" true. - **No visited check at all.** On any graph with a cycle the traversal loops forever; on a dense DAG it can revisit vertices exponentially often. The visited flag is the entire difference between graph search and blind walking. - **Undirected graphs stored one-way.** An undirected edge $\set{u,v}$ must appear on _both_ adjacency lists. Insert only $(u, v)$ and the graph silently becomes a digraph; BFS distances and connectivity both come out wrong, and nothing crashes to tell you. - **Recursive DFS on deep graphs.** A path of $10^6$ vertices means recursion depth $10^6$, which overflows the call stack in most language runtimes long before memory runs out. Production DFS either raises the recursion limit or maintains an explicit stack of (vertex, position-in-adjacency-list) frames — and the naive "push all neighbors" stack version visits vertices in a valid DFS order but does _not_ reproduce the recursive discovery/finish times, so timestamp-based arguments quietly break. - **Parent edges masquerading as cycles.** In an undirected graph, DFS from $v$ immediately re-sees the edge back to its parent $v.\pi$, which is gray. That is not a cycle; cycle detection must ignore the single edge to the parent (and be careful again if parallel edges are allowed). - **Trusting vertex order.** Adjacency-list order changes the BFS tie-breaking order within a layer and the shape of the DFS forest. Distances and the parenthesis structure are guaranteed; _which_ shortest-path tree or which edge classification you get is not, so tests that hard-code one particular tree are brittle. ## BFS or DFS? They are one algorithm, $\textsc{Whatever-First-Search}$, read with two different bags. Both are $O(V + E)$ linear-time skeletons; the _order_ of removal is the only difference, and it dictates the structure each exposes. | | BFS (queue) | DFS (stack) | | --- | --- | --- | | Frontier bag | queue, FIFO — oldest first | stack, LIFO — newest first | | Search tree | shallowest paths from $s$ | nesting / parenthesis structure | | Computes | $\dist[s][v]$ (shortest hops) | start/finish times $[s_v, f_v]$ | | Reveals | level sets, connectivity | back edges → cycles, finish order | | Typical uses | unweighted shortest paths, components | cycle detection, topological sort, strong connectivity | Choose BFS when distance-in-hops matters; choose DFS when you need a graph's recursive structure, which, as the next two lessons show, is what topological sorting and strong connectivity demand. And keep the frame in mind: swap the bag for a **priority queue** and the very same skeleton becomes Dijkstra and Prim. ## What DFS unlocks Almost every algorithm in the rest of this module is DFS with a small amount of bookkeeping added. The timestamps and the edge classification are the raw material. **Cycle detection, traced.** The cycle theorem ("acyclic iff no back edge") is a decision procedure. Take the dependency graph $a \to b \to c \to a$ with a side branch $b \to d$. DFS from $a$ discovers $a$ (gray), then $b$ (gray), then $c$ (gray); $c$'s only edge is $c \to a$, and $a$ is **gray** — an ancestor still on the recursion stack — so $c \to a$ is a **back edge** and a cycle is reported the instant it is scanned. The gray set at that moment, $\{a, b, c\}$, holds exactly the cycle's vertices. Contrast a graph with $c \to d$ instead of $c \to a$: every scanned edge lands on a white or black vertex, DFS finds no back edge, and the finish order $d, c, b, a$ (reverse of finishing) is a valid [topological order](/algorithms/graphs/topological-sort-and-scc). $$ % caption: Cycle detection by back edge. Left: $c \to a$ finds $a$ gray (on the stack), so % it is a back edge and $\set{a,b,c}$ is a cycle. Right: replacing it with $c \to d$ % leaves no gray target, no back edge, and DFS finishing order gives a topological % sort. \begin{tikzpicture}[>=Stealth, font=\small, V/.style={circle, draw, minimum size=8mm, font=\small}, G/.style={circle, draw, minimum size=8mm, font=\small, fill=acc!18, draw=acc, thick}, back/.style={->, red!75!black, line width=1.2pt}, tree/.style={->, line width=1.1pt}] \definecolor{acc}{HTML}{2348F2} % left: has cycle. a,b,c stacked on the left; back edge c->a sweeps up the RIGHT % side, clear of the tree edges; d hangs off to the far left. \node[G] (a) at (0,1.6) {$a$}; \node[G] (b) at (0,0) {$b$}; \node[G] (c) at (0,-1.6) {$c$}; \node[V] (d) at (-1.6,0) {$d$}; \draw[tree] (a) -- (b); \draw[tree] (b) -- (c); \draw[tree] (b) -- (d); \draw[back] (c) to[bend right=55] node[font=\scriptsize, right]{back} (a); \node[font=\scriptsize] at (0,-2.7) {cycle: a, b, c all gray}; % right: acyclic \begin{scope}[xshift=52mm] \node[V] (a2) at (0,1.4) {$a$}; \node[V] (b2) at (0,0) {$b$}; \node[V] (c2) at (1.4,-1.0) {$c$}; \node[V] (d2) at (-1.4,-1.0) {$d$}; \draw[tree] (a2) -- (b2); \draw[tree] (b2) -- (c2); \draw[tree] (b2) -- (d2); \draw[tree] (c2) to[bend left=30] (d2); \node[font=\scriptsize] at (0,-2.1) {acyclic: topo order $d,c,b,a$}; \end{scope} \end{tikzpicture} $$ **Iterative DFS.** The recursive form is the clearest, but a path of a million vertices overflows the call stack in most runtimes. The fix is an explicit stack of frames — a `(vertex, iterator-into-its-adjacency-list)` pair — so the "recursion" lives on the heap. The subtlety worth flagging: the naive "push all neighbors at once" stack does visit vertices in _a_ valid DFS order, but it does **not** reproduce the discovery/finish timestamps, because a vertex can be pushed several times before it is first popped. Any argument that leans on the parenthesis structure (edge classification, low-link values) needs the frame-based iterative form that stamps finish times on the way back down the stack. **The rest of the module, in one sentence each.** Every algorithm ahead is DFS plus a specific piece of bookkeeping: - **[Topological sort and SCC](/algorithms/graphs/topological-sort-and-scc)** orders a DAG by _reverse finish time_, and finds strongly connected components by running DFS twice (Kosaraju) or tracking low-links in one pass (Tarjan). - **[Bridges and articulation points](/algorithms/graphs/bridges-and-articulation-points)** add a `low[v]` value — the earliest discovery time reachable from $v$'s subtree via one back edge — to find the edges and vertices whose removal disconnects the graph. - **[Lowest common ancestor](/algorithms/graphs/lowest-common-ancestor)** and **[Eulerian tours](/algorithms/graphs/eulerian-tours)** both walk the DFS tree, one reading its ancestor structure, the other its edge traversal order. DFS is a _framework_: run the depth-first walk, and decide what to record. The choice of bookkeeping is the design space. ## Takeaways - A **graph** $G = (V, E)$ models things and their connections; the sparse-versus-dense distinction drives every representation choice. - Prefer the **adjacency list** ($\Theta(V + E)$ space, fast neighbor iteration); use the **adjacency matrix** ($\Theta(V^2)$) only for dense graphs or constant-time edge tests. - **$\textsc{Whatever-First-Search}$** is the one skeleton: grow a frontier _bag_, and let the bag's discipline pick the next vertex. A **queue** gives BFS, a **stack** gives DFS, a **priority queue** gives the weighted algorithms to come. - **BFS** explores in rings from a source and computes $\dist[s][v]$, the shortest path _in hops_, building a breadth-first tree via a FIFO queue. - **DFS** plunges and backtracks, stamping **start/finish times** $[s_v, f_v]$ that **nest** like parentheses (parenthesis + white-path theorems) and **classify edges**; a **back edge** exists exactly when the graph has a cycle. - Both traversals run in $O(V + E)$, linear in the graph's size, and either one labels connected components for free. [^erickson-dfs]: **Erickson**, Ch. 6 — Graph Search — DFS start/finish times and the parenthesis (nesting) theorem.