Eight tasks, each waiting on the ones before it. Schedule them by hand and feel the constraints bite —
then let a depth-first search dive to the bottom of every dependency and surface a
valid build order every time. Then add one bad edge and watch it refuse.
THE GIST · 20 SECONDS
A topological sort lays the vertices of a DAG in a line so every arrow points
forward — every task after its prerequisites. The trick: run DFS, and the moment a node
finishes (all its descendants explored), push it to a list. Reverse that list and
you have a valid order. It runs in O(V + E) — and a cycle is exactly what makes it impossible.
DAGdirected graph, no cycles
In-degreearrows pointing into a node
Finish timewhen DFS leaves a node
Back edgeedge to an in-progress node = cycle
① Order the graph yourself → ② Let DFS reverse its finishes → ③ Add a cycle, watch it refuse
BUILD ORDER
— nothing scheduled yet —
ready to schedule on the stack (visiting) finished / placed in a cycle
An arrow a → b means a must be built before b. DFS dives to the deepest dependency first, so a node only finishes after everything it points to — which is exactly why reversing the finish order gives a legal build order.
UNDER THE HOOD
What you just played, written down
You scheduled it by hand, watched DFS dive and finish nodes bottom-up, then saw a back edge expose a cycle. Here's the same thing as code.
How the Foreman thinks — five steps
Pick any unvisited node. Mark it gray — it's now on the recursion stack.
Recurse into its successors. For each edge out of it, dive into that node first if it hasn't been visited.
Finish the node. Once every successor is done, mark it black and push it onto a list.
Repeat from any node still unvisited, until all are black.
Reverse the list. The reversed finish order is a valid topological order.
WHY REVERSE-POST-ORDER WORKS
For any edge u → v, DFS finishes v before u (it explored v while still inside u).
So u sits later in the finish list, and after reversing, u sits earlier — exactly
the order topological sort requires. Catch a gray node mid-recursion and you've found a
cycle: no order exists.
The algorithm
WHITE, GRAY, BLACK = 0, 1, 2
function topoSort(graph):
color = {v: WHITE for v in graph}
order = [] # finish order
for s in graph:
if color[s] == WHITE:
dfs(s)
return reversed(order)
function dfs(u):
color[u] = GRAY # on the stack
for v in neighbours(u):
if color[v] == GRAY:
raise CycleError # back edge!
if color[v] == WHITE:
dfs(v)
color[u] = BLACK
order.append(u) # finished
TIMEO(V + E)every node + edge once
SPACEO(V)colors + recursion stack
Solved by hand — the run for the graph above
DFS finishes nodes deepest-first; reverse that and every arrow points forward.
↔ DFS vs Kahn's algorithm
The DFS way reverses finishing times. Kahn's way is BFS-flavoured: repeatedly emit
any node with in-degree 0, then remove its out-edges. Both are O(V + E); Kahn's also surfaces
the cycle as "nodes that never reach in-degree 0".
↔ Why a cycle breaks it
In a cycle a → b → … → a, every node waits on another in the loop, so none can go first.
A topological order exists iff the graph is acyclic — that's what the D and A in
DAG guarantee.
★ Where it's used
Build systems (make, Bazel) picking compile order, package managers, task schedulers, spreadsheet
recalculation, course prerequisites, and database migration ordering.
The picture: all arrows point forward
The page’s build graph laid out in the order the algorithm produces: reversed finish order. Every dependency arc runs left to right. The one extra edge from deploy to config (below the line) is the only kind of edge that cannot be drawn this way, because it points back at something that must already be done.
Worked example, step by step
The page’s graph has eight tasks. Visit them in index order, trying successors in the order the edges are listed. First the same graph with one extra edge, deploy → config, which closes a loop: rows 1 to 6. Then the original graph again from the point where deploy has no successors: rows 7 to 12. Gray means “on the stack right now”; finished nodes are black.
Step
Event
Gray stack
Finished so far
Note
1
enter config
config
—
2
enter db
config → db
—
3
enter auth
config → db → auth
—
4
enter ui
config → db → auth → ui
—
5
enter deploy
config → db → auth → ui → deploy
—
6
deploy sees config
config → db → auth → ui → deploy
—
config is gray: back edge, so a cycle
7
finish deploy
config → db → auth → ui
deploy
Without the extra edge, deploy has no successors
8
finish ui
config → db → auth
deploy, ui
9
api sees auth (black: already done)
config → api
deploy, ui, auth, db
10
cache sees deploy (black: already done)
config → api → cache
deploy, ui, auth, db
11
finish config
—
deploy, ui, auth, db, cache, api, config
12
finish utils
—
deploy, ui, auth, db, cache, api, config, utils
Reverse the finish list for the order
The cycle is found the moment an edge reaches a node that is still gray: the stack at that point, config → db → auth → ui → deploy, plus the edge back to config, is the cycle itself. Without the extra edge, the same walk shows why reversing works. Two later checks (api sees auth, cache sees deploy) meet black nodes and do nothing, since a finished node has already been placed behind everything that depends on it. The finish order is deploy, ui, auth, db, cache, api, config, utils; reversed, it is utils, config, api, cache, db, auth, ui, deploy. Checking all ten edges against that order finds none pointing backwards.
Complexity and trade-offs
Case
Time
Space
Why
DFS, recursive
O(V + E)
O(V)
Each node is entered once and each edge examined once. The space is the colour array plus a call stack as deep as the longest path.
DFS, explicit stack
O(V + E)
O(V)
Same work with the stack on the heap. This avoids the recursion limit: in Python’s default limit a straight chain of 2,000 nodes failed at depth 998.
Kahn’s algorithm (in-degree queue)
O(V + E)
O(V)
Repeatedly removes a node with no remaining prerequisites. It also detects a cycle: if fewer than V nodes come out, the rest are on or behind a cycle.
Repeated scan for a free node
O(V · E) or worse
O(V)
Recount incoming edges each round. On a 100-node chain this made 4,950 edge checks, against 199 for V + E.
Counting all valid orders
exponential in general
varies
A DAG can have many valid orders; producing one is cheap, listing or counting all of them is not.
Both linear algorithms are optimal, since any answer must at least read the graph. The practical differences are elsewhere. DFS gives a cycle witness for free (the stack at the back edge) and is the building block for strongly connected components. Kahn’s version emits nodes as they become ready, so it extends naturally to scheduling with parallel workers, and it is iterative by construction. Once you have a topological order, a longest-path computation on a DAG is another linear pass: on this page’s graph the longest dependency chain has 5 tasks, config → db → auth → ui → deploy.
Common mistakes
Tracking only visited, not on-stack
With a single visited flag a back edge looks the same as a harmless revisit. On the two-node loop a → b → a a visited-only version returns an order without complaint. You need three states: unseen, on the stack (gray), finished (black).
Treating every revisit as a cycle
The opposite error is reporting a cycle whenever an edge reaches an already-visited node. The diamond 0 → 1, 0 → 2, 1 → 3, 2 → 3 has no cycle, but the second path to node 3 meets a finished node. Only a gray target means a cycle.
Forgetting to reverse
Finish order puts dependencies first, so printing it as is gives the reverse of what you want. On the page’s graph, all 10 of 10 edges point backwards in the raw finish order, and 0 do after reversing.
Recording nodes on entry instead of on exit
A preorder list is not a topological order, reversed or not. On the page’s graph, preorder (config, db, auth, ui, deploy, api, cache, utils) has 4 edges pointing backwards, for example api before utils although utils feeds it. Append at finish time.
Starting from one node
A topological sort has to cover the whole graph, so run DFS from every unseen node. Starting only from config returned 7 of the 8 tasks, missing utils, which cannot be reached from config.
Where this shows up
Build and package tools
Deciding which target to build first, or which package to install before another, is a topological sort of the dependency graph, and a reported cycle is an error to show the user.
Spreadsheets and dataflow
A cell that references others must be recalculated after them. Ordering cells topologically gives a safe recalculation order and flags circular references.
Scheduling and migrations
Course prerequisites, database migrations and deployment steps all form a graph of “this must happen before that”, and an order that respects it is a topological order.
Dynamic programming on DAGs
When subproblems form a DAG, processing them in topological order guarantees each is solved after the ones it uses. Longest or shortest path in a DAG is one such pass.
RUN IT YOURSELF
The same algorithm, in Python & TypeScript
Both tabs are the identical algorithm (Kahn's), running for real in your browser — Python through WebAssembly, TypeScript transpiled on the fly. No server. Switch tabs to compare the languages line for line, read the numbered comments, edit anything, and hit Run (or ⌘/Ctrl + Enter). Each language downloads its runtime once on first run.
HOW TO READ THE CODE — 4 IDEAS
in-degree = how many prerequisites a task is still waiting on. The comments mark this step 1.
Any task at in-degree 0 has nothing left to wait for, so it's ready to build now (step 2).
Building a task frees its dependents: drop each of their counters by one; when a counter hits 0, that task becomes ready too (steps 3–5).
If some tasks never reach 0, they're stuck waiting on each other — a cycle, so no order exists (step 6).
CPython · WebAssembly
1
1
▶ Watch it explained
DFS and Topological Sort: Time and Space Complexity, From First Principles
QUICK CHECK
Did it stick?
See every answer, with the reasoning
How does DFS turn into a topological sort?
Answer: Push each node when it finishes, then reverse the list — A node finishes only after every node it points to, so it lands later in the finish list — reversing puts dependencies first.
During DFS, an edge points to a node currently marked gray (on the stack). What does that mean?
Answer: The graph has a cycle, so no topological order exists — An edge to a gray (in-progress) ancestor is a back edge — the signature of a cycle. Topological sort is only possible on a DAG.
A DAG has how many valid topological orders?
Answer: Often many — any order respecting the edges — Whenever two nodes have no path between them they can swap, so most DAGs have many valid orders.
FAQ
Topological sort, answered
What is a topological sort?
A linear ordering of a DAG's vertices so that for every edge u → v, u comes before v. It linearizes "do this before that" constraints — and exists if and only if the graph has no cycle.
How does DFS produce a topological order?
Run DFS; each time a node finishes (all descendants explored), push it to a list. Reverse the list. Because a node always finishes after everything it points to, the reversed order puts every dependency first.
What is the time complexity?
O(V + E) for both the DFS method and Kahn's algorithm — each vertex and edge is touched once. Space is O(V) for colors plus the recursion stack or the queue.
How does it detect a cycle?
Mark a node gray while it's on the recursion stack, black when it finishes. An edge to a gray node is a back edge — it points to an ancestor still in progress — which means a cycle, so no order exists.
Is the topological order unique?
Usually not. Two nodes with no path between them can go in either order, so most DAGs have many valid orders. It's unique only when the DAG is a single chain.
Where is topological sort used?
Build systems and compilers (compile order), package managers, task schedulers, spreadsheet recalculation, course prerequisites, dependency injection, and ordering database migrations.