THE DEPTH-FIRST SEARCH — a dart

DEPTH-FIRST SEARCH go deep, then backtrack — the recursion that explores a graph

Depth-first search explores a graph by going as far as it can down one path before backtracking to try another — the natural recursion: visit a node, mark it, then recurse into each unvisited neighbor. In one sweep it reaches every node connected to the start, and the order it enters and leaves nodes (its discovery/finish times) powers a whole family of algorithms: topological sort, cycle detection, strongly connected components, and finding bridges and articulation points. It is how you solve a maze by always taking the next unexplored turn and unwinding at dead ends. From node 0 in a connected 5-node graph it reaches all 5.

THE TECHNIQUE visit, mark, recurse into unvisited neighbors — deep then backtrack

The demo runs DFS from node 0 in a connected 5-node graph — it reaches all 5 nodes: live demo

HISTORY & CREDIT depth-first search · Trémaux / Tarjan

“Exploring a graph needs a plan.” — DFS needs only recursion: go deep, mark, backtrack; it reaches everything connected. cited

the move · visit a node, mark it, recurse into each unvisited neighbor — deep first.
the backtrack · at a dead end, unwind and try the next unexplored branch.
the power · discovery/finish order → topological sort, cycles, SCCs, bridges — Tarjan.

A graph explored by plunging down every path and unwinding at the dead ends — recursion made a search. traversal

RECOMMEND FOR I-13 the reached set, on the compiler

On the canonical compiler, DFS from node 0 in the connected graph reaches all 5 nodes:

$ i13 run nw_depthfirstsearch.i13 # recurse into unvisited neighbors RUN OK · 999 step(s) · peak stack 25 · call depth 17 reached = 5 -- all nodes reachable from 0

Recommend as a NULL — a traversal, resource-shaped. DFS computes the reachable set (and a visit order) — a forall-pinned result of the graph (B39), by a linear-time recursion (B40). No new invariant. NULL — the recursion under half of graph theory.