Give a directed graph where an edge from A to B means "A must come before B" — course prerequisites, build dependencies, task ordering — and topological sort answers "what's one valid order to do everything in?" It's built directly on depth-first search: run a DFS from every node, and every time a node finishes (meaning all its outgoing edges have already been fully explored), push it onto a stack. When there's nothing left to visit, reverse that stack. That's the whole algorithm — the hard part isn't the traversal, it's noticing that a node can only be safely placed after everything it points to has already finished, which is exactly what "finish order, then reverse" gives you for free. It only makes sense on a graph with no cycles (a Directed Acyclic Graph, or DAG) — if A depends on B and B depends on A, there's no order that satisfies both, and the demo below can show you exactly where that breaks.
The graph below is eight courses and their prerequisites: CS101 = Intro to
Programming, MATH = Discrete Math, DS = Data Structures, ALGO
= Algorithms, DB = Databases, OS = Operating Systems, DSYS =
Distributed Systems, CAP = Capstone Project. An arrow from X to Y means X is a
prerequisite of Y. Press Step or Run to walk the DFS: a dashed
node is currently "on the path" (visiting, not yet finished), a shaded node is fully finished, and
the strip below the graph fills in with the raw finish order as nodes complete — watch it get
reversed into the final answer on the last step. Press Add cycle edge to add one
extra arrow from Distributed Systems back to Data Structures (a real requirements loop: DS → ALGO
→ DSYS → DS) and re-run — the algorithm should catch it and refuse to produce an order, rather than
silently returning a wrong one.
A DFS visit to node X doesn't return — doesn't mark X "finished" — until it has fully explored every node reachable from X. So by the time X gets pushed onto the finish stack, everything X points to (directly or transitively) is already sitting on that stack, closer to the top. Reversing the whole stack at the end turns "closer to the top" into "earlier in the final order," which is exactly the guarantee a topological order needs: every edge points from something earlier to something later. This works even across disconnected pieces of the graph — the outer loop just starts a fresh DFS from the next unvisited node, in id order here, whenever the previous one runs out of reachable nodes, and the relative order within each independently-discovered piece is still respected once everything gets reversed together at the end.
The one subtlety plain DFS doesn't need but this does: three states per node,
not two. A node is unvisited, visiting (pushed onto the current DFS path
but not yet finished), or done (fully finished). The reference implementation below
checks a neighbor's state before recursing into it — and that three-way check is also exactly how
it catches a cycle (see Pitfalls).
Matches the demo above one for one — the demo's step generator is the same recursive shape,
just with yield points added at each state transition so every intermediate step is
visible instead of only the final answer:
const UNVISITED = 0, VISITING = 1, DONE = 2;
function topologicalSort(numNodes, adjacency) {
const state = new Array(numNodes).fill(UNVISITED);
const order = []; // nodes pushed in finish order
function visit(node) {
state[node] = VISITING;
for (const next of adjacency[node]) {
if (state[next] === VISITING) {
throw new Error(`cycle: ${node} -> ${next}`);
}
if (state[next] === UNVISITED) visit(next);
// state[next] === DONE: already fully explored, nothing to do
}
state[node] = DONE;
order.push(node);
}
for (let node = 0; node < numNodes; node++) {
if (state[node] === UNVISITED) visit(node);
}
return order.reverse();
}Two states can't detect a cycle — you need the third. If a node only tracked
"visited" or not, a cycle A → B → A would look identical to A and B simply sharing a common
successor: by the time the recursion comes back around to A, A is already marked visited, and a
naive check would just skip it and keep going, quietly producing a bogus order instead of ever
noticing anything was wrong. The VISITING state is what makes the distinction — it
means "still on the current path, not actually finished" — so an edge into a VISITING
node is unambiguously a back-edge onto the graph's own current recursion path, which is precisely
what a cycle is. This is also the standard way to answer "does this directed graph have a cycle at
all," independent of wanting a topological order — the same three-state DFS is the whole
algorithm.
The order isn't unique. Nothing above says there's only one valid answer —
plenty of DAGs (including the one in the demo) have several. Starting the outer loop from
MATH instead of CS101, or trying DB before OS
inside Data Structures' neighbor list, produces a different but equally valid order, since both
still put every prerequisite before whatever needs it. If a caller needs a specific tie-break (say,
alphabetical among courses with no ordering constraint between them) that has to be layered on top
— plain DFS-based topological sort doesn't provide one on its own.
Only defined for DAGs. The demo's cycle toggle exists to make this concrete rather than just asserted: with the extra edge in place, there is genuinely no valid order — Data Structures needs to come before Distributed Systems (through Algorithms), but the added edge also needs Distributed Systems before Data Structures. Both can't be true at once, and the algorithm's job is to say so cleanly instead of returning a plausible-looking wrong answer.
This three-state DFS is specifically for directed cycles. If the graph were undirected instead, this whole machinery would be overkill — there's a much simpler check for that case built on Union-Find: process edges one at a time, and if an edge's two endpoints are already in the same set, adding it would close a cycle.
Time: O(V + E) — identical to plain DFS, since it is
plain DFS: every vertex is visited and finished exactly once, and every edge is inspected exactly
once, from its source. Space: O(V) for the state array, the finish
stack, and the recursion depth, which in the worst case (a graph that's one long chain) is also
O(V) — the same stack-overflow
pitfall that applies to any deep recursive DFS.
This site's guide, Choosing a Graph Traversal Approach, compares this entry against the other ten Graph Traversal entries side by side.