Depth-First Search

The 10-second versionCopy Anchor Link

Depth-First Search dives. From a vertex it picks one neighbour and goes all the way down that path before it ever considers a second one, backing up only when it hits a dead end. Recursion (or an explicit stack) remembers where it came from. The real magic isn't the order of visiting — it's the order of finishing: record when each vertex is discovered and when it's completely done, and those two numbers turn out to encode cycles, connectivity and topological order.

Why this existedCopy Anchor Link

Maze solving is old. Long before computers, people needed an algorithm to escape a hedge maze without wandering in circles forever. The earliest written-up method is Trémaux's method, attributed to a 19th-century French engineer named Charles Trémaux and popularised in Édouard Lucas's 1882 book Récréations Mathématiques. The recipe: walk forward, chalking the corridors you use; at a junction take any unmarked corridor; and if you hit a dead end, retrace your chalk marks back to the last junction with an unexplored branch. That is depth-first search, done with chalk instead of a call stack.

What turned a parlor trick into one of the most important algorithms in computing came in 1972. Robert Tarjan, in "Depth-first search and linear graph algorithms", showed that if you record two timestamps per vertex — when it's discovered and when it finishes — the shape of those numbers hands you a shocking amount of structure for free. That one paper quietly powers compilers, network analyzers and half the graph algorithms you'll ever meet.

Why did it matter then? Because before DFS, "is this graph connected?", "does it have a cycle?" and "what order can I do these tasks in?" each looked like a separate problem. Tarjan showed they all fall out of one traversal run in linear time. Depth-first search became the universal key.

Inside the inventor's headCopy Anchor Link

Imagine you're the one holding the chalk. Your first instinct is to just go — pick a tunnel and walk until something happens. Watch the two ways that goes wrong:

The deadly mistake is the same one BFS wrestles with: memory. If you don't mark where you've been, a cycle sends you around forever. And there's a subtler version that even careful people write — marking a corridor only after you come back from it:

// Naive: mark *after* exploring neighbours. On a cycle A → B → A this loops forever.function dfsLate(u, adj, seen) {  for (const w of adj[u]) {    if (!seen[w]) dfsLate(w, adj, seen);  }  seen[u] = true;                         // too late — we already blew the stack}// Improved: mark the moment we *enter* the vertex.function dfsEarly(u, adj, seen) {  seen[u] = true;                         // gray: on the current path  for (const w of adj[u]) {    if (!seen[w]) dfsEarly(w, adj, seen);  }}

The fix is one line moved up: mark on entry. Now the "aha" that makes DFS more than maze running. Tarjan stared at the chalk trail — the set of vertices currently on your path back to the start — and realised it's information, not just bookkeeping. A vertex you reached but are still exploring (chalked gray) is an ancestor of everything you're touching now. A vertex you've completely finished with (chalked black) is behind you.

That distinction, "still on my path" versus "done entirely," is what lets DFS answer questions no amount of walking could. Blow the dust off Euler's degree argument — this time the numbers are timestamps, and they crack cycles, connectivity and scheduling all at once.

The final approachCopy Anchor Link

The algorithm, as a flowCopy Anchor Link

The invariants that make it correctCopy Anchor Link

1. Every edge is looked at exactly once. Each vertex scans its own neighbour list a single time, so the whole traversal is Θ(V + E) — no edge is ever revisited.
2. Gray means "on the current path". The gray vertices are precisely the ancestors of the vertex being explored. If you ever see an edge into a gray vertex, you've found a back edge — a cycle. (That's the entire next page.)
3. Discovery and finish times are nested, never interleaved. For any two vertices, their [disc, fin] intervals are either disjoint, or one strictly contains the other — a property that mirrors the recursion tree exactly.
4. Finish order is reverse topological order. If u has an edge to v, then v finishes before u. Reverse the finish list and dependencies come out on top. (That's the page after next.)

A worked traceCopy Anchor Link

Run DFS from 0 on the graph we've been using, visiting neighbours in increasing order (0:[1,2], 1:[0,2], 2:[0,1,3], 3:[2,4], 4:[3]). The recursion plunges straight down one chain:

Read the finishes top to bottom: 4, 3, 2, 1, 0. Every edge points from a vertex that finishes later to one that finishes earlier — which is why reversing that list gives you a valid dependency order. Notice how different this is from BFS: BFS would have touched 3 at distance 2 and 4 at distance 3, but DFS found them by disappearing down the 0 → 1 → 2 tunnel first.

It in codeCopy Anchor Link

The recursive version is the one to internalise; it's short, and the timestamps are the payload:

// color: 0 = white (unseen), 1 = gray (on the path), 2 = black (done)function dfs(u, adj, color, disc, fin, timer) {  color[u] = 1;                             // gray: on the current path  disc[u] = ++timer.t;  for (const w of adj[u]) {    if (color[w] === 0) dfs(w, adj, color, disc, fin, timer); // tree edge    // color[w] === 1 would be a back edge (a cycle) — handled next page  }  color[u] = 2;                             // black: fully explored  fin[u] = ++timer.t;}// call with: const timer = { t: 0 }; dfs(0, adj, color, disc, fin, timer);

The same walk without recursionCopy Anchor Link

On a deep graph — a chain of a million vertices — recursion overflows the call stack. The fix is to manage the stack yourself. It "adds something new": you get the same exploration order, with the depth bounded by the heap rather than the CPU stack.

// Same plunge-first order, but the path lives in our own array, not the call stack.function dfsIter(root, adj) {  const visited = new Array(adj.length).fill(false);  const stack = [root];  const order = [];  while (stack.length) {    const u = stack.pop();    if (visited[u]) continue;               // a duplicate we can ignore    visited[u] = true;    order.push(u);                          // visit on pop    for (let i = adj[u].length - 1; i >= 0; i--)  // reverse push → first neighbour pops first      if (!visited[adj[u][i]]) stack.push(adj[u][i]);  }  return order;}

Cost tableCopy Anchor Link

Time is fixed at Θ(V + E): every vertex and edge is examined once, best, average and worst alike. The only choice is where the path lives — the call stack (O(h), which is O(V) in the worst case of a long chain) or your own stack (O(V)).

Where you meet it todayCopy Anchor Link

• Connected components. "How many separate groups?" is one DFS per unvisited vertex; the number of restarts is the answer.
• Cycle detection and topological order. The two pages after this one are literally DFS with a twist — watch for the gray vertex and read the finish times.
• Compilers and linkers. Resolving includes, evaluating dependency graphs, and detecting circular imports are all DFS with the color trick.
• Garbage collection and solvers. Sudoku solvers, game-tree search and the "mark" phase of a tracing collector all dive first and back up on failure.

The most familiar one is counting islands — connected blobs of land in a grid. Each cell has up to four neighbours, so a grid is a graph, and one DFS floods a whole island:

// Sink one whole island (four-connected blob of 1s) so it isn't counted twice.function sink(g, r, c) {  if (r < 0 || r >= g.length || c < 0 || c >= g[0].length || g[r][c] !== 1) return;  g[r][c] = 0;                              // mark seen  sink(g, r - 1, c); sink(g, r + 1, c);  sink(g, r, c - 1); sink(g, r, c + 1);}function countIslands(g) {  let count = 0;  for (let r = 0; r < g.length; r++)    for (let c = 0; c < g[0].length; c++)      if (g[r][c] === 1) { count++; sink(g, r, c); }  return count;}

RecapCopy Anchor Link

• DFS dives down one path to its end before backing up; recursion or an explicit stack holds the trail.
• Always mark on entry (not on exit), or a cycle loops forever.
• Its real power is the timestamps: disc and fin, which are neatly nested like the recursion tree.
• Gray = on the current path (an edge into gray is a cycle); black = completely done.
• Reversing the finish order yields a dependency order — DFS quietly contains both the next two pages.

Next up: Detecting Cycles — what that gray vertex is really telling you.