Programming

Depth-First Search

It is not a blind plunge into the dark. It is a dual-clock crystallization: each vertex is entered with a timestamp and exited with an epitaph, freezing the chaos of a graph into a laminar geometry of perfectly nested time intervals.

Visited flags blur ancestry; log 12 timestamps across 6 vertices to catch the single back edge.

Mission 12about 8 min

Log discovery and exit timestamps to structure graph traversals into laminar intervals and expose back edges.

  1. Step the depth-first cursor to log entry and exit ticks across six vertices
  2. Verify the parenthesis property where time intervals strictly nest or separate
  3. Spot the single back edge to certify cycles and extract topological order

After thisYou can construct linear-time topological sorts, articulation points, and Tarjan strong components.

Short on timeThe GraphCanvas laminar interval explorer in §2

Six Vertices, Two Clocks

3 minthe hook

One pass with two clocks per vertex classifies every arc of a digraph, and a single back edge certifies a cycle. Add one low-link number per vertex, and the same ledger finds every strongly connected component in linear time (Tarjan 1972). The same intervals build the dominator tree that optimising compilers use (Lengauer and Tarjan 1979).

Mark vertices visited and keep no leave time, and you have a list in the order you happened to walk it. Shuffle the adjacency lists and the list changes; the graph does not. The panel below runs the ledger on six vertices and nine arcs.

The picture is the two clocks: one ticks on entry, one on return, and a vertex’s pair of ticks reads as a parenthesis pair — it opens when the vertex is entered and closes when its frame returns.

Exactly one of these four arcs produces a back edge — pointing to an ancestor currently living on the active recursion stack. Which arc is the true cycle-closing back edge?

1 / 28
depth-first search · source A · directed
ABCDEF

1/28 new component rooted at A

  1. 1 new component rooted at A

Depth-first search from A. The path row is the recursion stack; the history below it is every enter, every arc examined and every return.

Watch B and C, not the drawn arcs: siblings get disjoint intervals, while a back edge points at an ancestor that is still open on the stack.

NextWhy do visited flags fail to capture the ancestral hierarchy of graph nodes?

Beyond the Cursor’s Trail

2 minthe trap

Ask a programmer what depth-first search does and you will hear a mechanical rule: dive as deep as possible, then backtrack. Ask what the algorithm produces and you will receive the sequence of visited vertices.

That sequence is an arbitrary artefact of input ordering and dictionary sorting. Reordering adjacent arcs completely scrambles the visit sequence while leaving the underlying graph topology untouched.

The algorithm’s true output is not a path. It is a spanning forest decorated with two timestamps per vertex that encode the global connectivity of the network.

NextHow do entry and exit timestamps create a laminar system of nested intervals?

The Laminar World: Nested Time Intervals

2 minthe invariant

Strip the traversal of commentary and a rooted spanning forest remains. Every vertex except a tree root has a unique parent that discovered it, linked by tree edges.

Assign each vertex two distinct timestamps. Let be the tick when the search enters , and let be the tick when its subroutine returns. The clock advances on every event, allocating ticks 1 through 12 across the six vertices.

vertexenter leave interval
A1121 to 12
B272 to 7
D363 to 6
E454 to 5
C8118 to 11
F9109 to 10

Each vertex owns an interval . This family of intervals is strictly laminar: any two intervals are either nested or completely disjoint, never partially overlapping. That single structural invariance drives every theorem on this page.

NextHow does the parenthesis theorem classify edges into tree, back, and cross types?

The Parenthesis Theorem and Arc Taxonomy

2 minthe algebra

The Parenthesis Invariant

This is the parenthesis theorem (Cormen, Leiserson, Rivest, and Stein). A single call stack permits no third state: subroutine calls are entered and exited in strictly nested order.

The same six vertices as dots: x is the enter time, y is the leave time

6810122468A closes lastdiscovery time d[v]finish time f[v]
ABDECF

Each point shows one vertex coordinate . One vertex nests inside another precisely when its point sits down and to the right of the ancestor point.

1 minboss round

Vertices B and C are sibling subtrees under parent A, with B explored first. What spatial relationship must their intervals share?

The Taxonomy of Four Arc Types

Every directed arc is categorized the instant its tail inspects it:

  • Tree edge. Head is undiscovered ( unassigned), making the parent of .
  • Back edge. Head is active on the stack (), pointing to an ancestor.
  • Forward edge. Head is finished and was discovered after (), skipping down to a descendant.
  • Cross edge. Head finished before was discovered (), bridging between separate branches.

The back edge alone governs cycles:

If arc is a back edge, the tree path from ancestor to combined with forms a closed cycle. Conversely, on any cycle, the earliest entered vertex must eventually receive a back edge from its cyclic predecessor.

In a directed acyclic graph (DAG), sorting vertices in decreasing order of finish time produces a valid topological order. Because a DAG has no back edges, every arc satisfies .

NextHow does a single back edge certify the presence of an algorithmic cycle?

Anatomy of Three Critical Frames

2 minthe simulation

Scrub the player to three revealing frames:

  • Frame 9. The stack holds when arc is inspected. Vertex sits at the stack bottom, meaning this single frame captures the cycle as a back edge.
  • Frame 26. Arc is examined after has already finished at time 5. This is a forward edge: an optimization shortcut rather than a cycle.
  • Frame 18. Arc reaches after ‘s entire subtree has closed. Because is neither ancestor nor descendant of , this is a cross edge.

NextHow does Tarjan's lowlink value compute strongly connected components in linear time?

Topological Ordering, Cut-Vertices, and Strong Components

2 minsystems

Run the search on a DAG and the finishing order delivers a topological sort without additional bookkeeping:

1 / 21
depth-first search · source A · directed
ABCDE

1/21 new component rooted at A

  1. 1 new component rooted at A

A DAG. Read the leave lines in order — E, D, B, C, A — and reverse them.

Reversing the exit times yields the topological order . Every directed edge points strictly forward in this sequence, generated without in-degree counting or queueing.

Define as the minimum discovery time reachable from ‘s subtree via at most one non-tree arc. This single metric enables Tarjan’s linear-time algorithms for cut-vertices and biconnectivity (Hopcroft and Tarjan 1973).

The same timestamps identify Strongly Connected Components (SCCs) in a single pass (Tarjan 1972). Modern optimizing compilers build dominator trees on control-flow graphs using this identical interval geometry (Lengauer and Tarjan 1979).

Next missionLongest Increasing Subsequence1.66M comparisons beat 10^30103 brute-force paths: how patience sorting extracts the longest ascending run.

Attributions

  • Tarjan 1972 — Depth-first search and linear graph algorithms, SIAM Journal on Computing: the linear-time strong-components algorithm, and the paper that made the forest plus two time-stamps the substrate of graph algorithms.
  • Hopcroft and Tarjan 1973 — Efficient algorithms for graph manipulation, CACM: biconnected components and articulation points from the same discovery times, via the low-link values used above.
  • Knuth 1968 — The Art of Computer Programming, Vol. 1: the systematic treatment of backtracking, of which depth-first search is the case on a graph.
  • Cormen, Leiserson, Rivest and Stein — Introduction to Algorithms: the parenthesis theorem, the white-path theorem and the four-way classification of arcs, stated here as they state them.
  • Lengauer and Tarjan 1979 — dominator trees from a depth-first traversal of a control-flow graph.
  • Trémaux 1882 — the maze-walking method, recorded in Lucas’s Récréations Mathématiques, the earliest written depth-first traversal.