Depth-first search

As of 10 October 2026 this site's JavaScript had 1260 modules and 2929 imports. If module A imports B, and B, through a chain of imports, A again, the browser has to run one of them before the other, and that one will see its neighbour half-finished. Is there such a loop on the site? One pass of depth-first search over all the imports is enough to answer. Below are the 20 modules of the symbolic maths engine behind the solvers and trainers of “Mathematics, the Queen of the Sciences”, and the search over their 98 imports, step by step.

Each module is a bar from the moment the search entered it to the moment it left. The bars nest inside each other like brackets; why this always happens is proved below. Of the 98 imports, 19 go along the search tree, 6 to descendants already found by another route, 72 into branches closed earlier, and only one goes up, to a module that is still on the stack: poly.js imports expand.js, and expand.js imports poly.js. This is the only cycle on the whole site, at least on the day of the snapshot. Switch the check to “seen before”: the naive rule “we came where we have been, so it is a loop” raises 79 alarms instead of one.

The idea

Go forward along edges while you can, and at a dead end step back and try the next edge. The path from the start to the current vertex is a stack: a step forward pushes a vertex, a step back pops it. Mark two moments for each vertex: when you entered and when you left. The vertices entered and not yet left are exactly the stack, and an edge into such a vertex means a cycle.

The marks are conveniently counted on one clock: each entry and each exit moves it on by one. These two numbers are called the entry and exit times. Along with them a vertex goes through three states: white, not yet seen; grey, entered but not left; black, left. At any moment the grey vertices form a path from the root of the search to the current vertex.

The search looks at each edge u → v exactly once, standing at u, and by the colour of v at that moment the edge falls into one of four classes:

• tree: v is white, and the search goes into it; these edges form the search tree (or forest);
• back: v is grey, that is, an ancestor of u on the stack; the edge closes a cycle;
• forward: v is black and was entered later than u: it is a descendant reached earlier by another route;
• cross: v is black and was entered before u: it is in another, already closed branch.

On the bars the classes can be seen by eye. A back edge strikes straight up, into a bar that is still open. A forward edge goes down and to the left, into u's own bar. A cross edge runs into a bar that closed before u's bar opened.

Why the brackets show everything

If entering a vertex is written as an opening bracket and leaving as a closing one, the result is a balanced bracket sequence. Under the scene it is written out in full: (index (rational) (ast) …). The second theorem says who will become a descendant.

Hence the price of the naive check. A black vertex is not a cycle: two paths simply lead to it, as in a diamond where two modules import the same third one. The site's code has thousands of such edges. Only grey vertices give away a cycle.

Code

The recursive version repeats the definition almost word for word. A dictionary keeps the colours, one variable the clock. The demo is seven modules of the same engine and the imports between them:

The last line is the modules in order of exit time. This is exactly how the browser will run them if the page loads solve.js: a module runs after everything it imports. The price of the cycle shows too: poly.js runs before expand.js, although it imports it. Function declarations from expand.js are already available to it, but constants and classes that expand.js has not yet created are not available at that moment, and using them while poly.js loads would end in a ReferenceError.

On large graphs recursion is replaced with a stack of one's own. But the stack must hold not vertices but pairs “a vertex and the place where we stopped in its list of neighbours”: that is exactly a frame of the call stack. In Python the place is kept by an iterator, in Go by the index of the next neighbour. The program below goes through all the site's modules, counts the edge classes and prints the cycle found: the grey part of the stack from the vertex the back edge ran into:

The stack never grew deeper than seven modules: the site's code is shallow. The search left 763 edges in the tree, 2093 cross, 72 forward and one back. The naive check would have raised 2166 alarms.

The trap: a stack of vertices is not depth-first search

People often write this: pop a vertex from the stack, push all its unmarked neighbours and mark them at once. The loop is short and looks like depth-first search, but it is not. All the neighbours are pushed at once, so a neighbour put aside long ago is taken later than vertices reached through its siblings. Such a loop visits the same vertices, but in a different order, and the vertices have no exit time at all: a vertex is popped before its descendants are dealt with.

While all you need is “what is reachable”, this does not matter. When you need an order, it is a mistake. By the ECMAScript specification the browser runs a module after the modules it imports, in the order of its import lines: that is the exit order of depth-first search. Below, side by side, are a real search and a stack of vertices whose order is taken in reverse:

The real search breaks only one edge, the one inside the cycle poly ↔ expand, which cannot be avoided in any order. The stack of vertices, when solve.js is loaded, breaks two more imports: simplify.js would run before evaluate.js, and poly.js before numeric.js, although both import them. Choose index.js, and there are seven violations.

What it costs

Each vertex enters the stack and leaves it once, each edge is looked at once, from its start. In total O(V + E) time and O(V) memory for the colours, marks and stack. For the whole site that is 1260 entries, 1260 exits and 2929 edges: a fraction of a millisecond.

The catch is the depth. The stack can grow to V: on a chain of a hundred thousand modules, recursion goes a hundred thousand levels deep. In Python the default depth limit is a thousand calls. It is raised with sys.setrecursionlimit, and since version 3.11 calls of Python functions do not use the processor stack, so deep recursion no longer crashes the interpreter. In this article's sandbox a recursion 200,000 deep ran, while at a million levels the program hit the memory limit of 256 MB. In Go a goroutine's stack grows by itself, by default up to 1 GB: in the sandbox a recursion a million levels deep ran, and at ten million memory ran out again. A stack of frames of one's own removes the question altogether: it lives in ordinary memory and grows while there is room.

Where it is used

Order and dependency cycles. Depth-first search underlies topological sorting: the exit order read backwards is a correct order of dependencies. Go forbids import cycles between packages: go build refuses to build the program and prints import cycle not allowed together with the loop itself. The browser allows cycles, but pays for it in that one module of the cycle sees another half-finished.

The structure of a graph. Marking by entry and exit times is the basis of a whole family of linear algorithms: Tarjan's and Kosaraju's strongly connected components, bridges and articulation points, planarity testing. All of them are one pass of depth-first search with a pair of numbers per vertex.

Backtracking. Sudoku, placing queens, solvers of logical formulas: this is depth-first search over a tree of partial solutions that is never stored whole: a step forward is the next decision, a dead end is a step back. More in backtracking.

Mazes. Depth-first search with a random choice of neighbour builds a maze without loops, and the rules for getting out of a maze, which Édouard Lucas in 1882 attributed to the telegraph engineer Trémaux, are the same depth-first search written in chalk on the walls. More on this in the course chapter on graphs.

Tarjan and Hopcroft

Walking a maze with backtracking was known long ago, but depth-first search as a tool for algorithms was discovered in the early 1970s. Robert Tarjan was writing a dissertation on planarity testing, whether a graph can be drawn on the plane without edges crossing, and defended it in 1972. The same year the paper “Depth-first search and linear graph algorithms” came out: in it depth-first search with entry times gave strongly connected components and biconnected components in linear time. In 1974 Tarjan and John Hopcroft published the first linear-time planarity test, also built on depth-first search. In 1986 both received the Turing Award “for fundamental achievements in the design and analysis of algorithms and data structures”.

Its sibling is breadth-first search: the same traversal with a queue instead of a stack. The wave finds shortest paths, but does not know where a branch ends, and so sees neither cycles nor order.

Problems

Both problems are on this site's real imports. In the first you tell a cycle from a diamond. In the second you repeat the browser: print the modules in the order they run, and a stack of vertices will not help here.