Algorithms from zero
Topological sort: ordering a DAG with Kahn and DFS
You know how to traverse a graph: DFS dives deep, BFS spreads wide, and connected components count the separate pieces. Now a sharper question. Suppose the graph is a list of tasks where an arrow A → B means “A must happen before B”: course prerequisites, build steps, package installs, a spreadsheet’s formula dependencies. In what order can you do all the tasks so that nothing is ever started before something it depends on is finished? That order is called a topological order. It is not unique—often many valid orders exist—but it only exists at all if the dependency graph has no cycle. If task A needs B and B needs A, no order can satisfy both. This lesson teaches two algorithms to produce a topological order and, as a free bonus, to detect when none exists because the graph contains a cycle.
After this lesson you can define a topological order: a linear listing of the vertices of a directed acyclic graph (DAG) such that for every edge u → v, u appears before v. You understand why such an order exists if and only if the graph is acyclic. You can write Kahn’s algorithm: compute every vertex’s in-degree, enqueue all in-degree-0 vertices, repeatedly pop one into the output and decrement its neighbors’ in-degrees, enqueuing any that reach 0. You know the cycle test: if the output has fewer than V vertices, the graph has a cycle and no topological order. You can also write the DFS variant: run DFS and push each vertex onto a stack when it finishes (post-order), then reverse the stack. You know both run in O(V + E) time and O(V) space. Next lessons build on ordered DAGs for shortest paths and scheduling.
What is a topological order?
A topological order (or topological sort) of a directed graph is a linear arrangement of all its vertices such that for every directed edge u → v, vertex u comes before vertex v in the list. Read an edge u → v as “u must come first.” A valid topological order respects every such constraint at once.
It exists only for a DAG
A topological order exists if and only if the graph is a directed acyclic graph (DAG)—a directed graph with no cycle. The reason is simple. If there were a cycle a → b → c → a, then a must come before b, b before c, and c before a. That demands a comes before itself, which is impossible. So a cycle blocks any valid order. Conversely, every DAG has at least one valid order (often many). Topological order is usually not unique: two tasks with no dependency between them can go in either relative order.
A real example: course prerequisites
Each arrow means “prerequisite of.” You must finish the source course before taking the target.
intro
/ \
v v
data-structures discrete-math
| \ /
| v v
v algorithms
databases |
v
mlEdges (the adjacency list):
intro: [data-structures, discrete-math]
data-structures: [algorithms, databases]
discrete-math: [algorithms]
algorithms: [ml]
databases: []
ml: []A valid plan must take intro first (nothing depends on having done anything before it) and ml last (it depends on algorithms, which depends on two earlier courses). Several valid orders exist; the algorithm below produces one specific one.
Kahn’s algorithm: peel off the things with no prerequisites left
The Kahn’s algorithm idea is intuitive. The in-degree of a vertex is how many edges point into it—how many unmet prerequisites it has. A vertex with in-degree 0 has nothing blocking it, so it can go next. Take one, output it, and “remove” it from the graph by decrementing the in-degree of each vertex it pointed to. Some of those may now drop to 0 and become available. Repeat until every vertex is placed.
- Compute the in-degree of every vertex.
- Put all in-degree-0 vertices into a queue.
- While the queue is not empty:
- Pop a vertex v, append it to the output order.
- For each neighbor w of v: decrement
inDegree[w]. If it becomes 0, enqueue w.
- If the output contains all V vertices, it is a topological order. If it has fewer than V, the remaining vertices are stuck in a cycle—no order exists.
Worked Kahn trace on the course graph
In-degrees to start (count incoming edges):
intro: 0 data-structures: 1 discrete-math: 1
algorithms: 2 databases: 1 ml: 1Initial: only intro has in-degree 0.
queue = [intro], order = []
Pop intro. order = [intro].
decrement data-structures -> 0 (enqueue), discrete-math -> 0 (enqueue).
queue = [data-structures, discrete-math]
Pop data-structures. order = [intro, data-structures].
decrement algorithms 2->1 (not 0), databases 1->0 (enqueue).
queue = [discrete-math, databases]
Pop discrete-math. order = [intro, data-structures, discrete-math].
decrement algorithms 1->0 (enqueue).
queue = [databases, algorithms]
Pop databases. order = [..., databases]. No neighbors.
queue = [algorithms]
Pop algorithms. order = [..., algorithms].
decrement ml 1->0 (enqueue).
queue = [ml]
Pop ml. order = [..., ml]. No neighbors.
queue = []
Output has all 6 vertices -> valid topological order:
intro -> data-structures -> discrete-math -> databases -> algorithms -> mlEvery arrow in the graph points forward in that list, so the order is valid.
The DFS variant: reverse the finish order
A second algorithm uses depth-first search. Run DFS over the whole graph. When a vertex finishes—after all its outgoing edges have been fully explored—push it onto a stack. This is post-order. After DFS completes, reverse the stack (or pop it) to get a topological order.
Why it works: a vertex finishes only after everything reachable from it has already finished. So in post-order, a vertex appears before all of its descendants. Reversing flips that to “before all things it depends on”—exactly the topological constraint. For the course graph one DFS run produces the post-order ml, algorithms, databases, data-structures, discrete-math, intro; reversed, that is intro -> discrete-math -> data-structures -> databases -> algorithms -> ml, another valid order (different from Kahn’s, but equally correct).
Two ways to detect a cycle
Both algorithms double as cycle detectors:
- Kahn: if the final output has fewer than V vertices, a cycle remains. Vertices inside a cycle never reach in-degree 0, so they are never enqueued.
- DFS: track vertices currently on the recursion stack (the “in-progress” set). If DFS reaches a vertex already in-progress, that back edge closes a cycle—no topological order exists.
Kahn’s algorithm with in-degrees and a queue
1
function topoSortKahn(adj) {
2
// 1. Compute in-degree of every vertex
3
const inDegree = {};
4
for (const v of Object.keys(adj)) inDegree[v] = 0;
5
for (const v of Object.keys(adj)) {
6
for (const w of adj[v]) inDegree[w]++;
7
}
8
9
// 2. Enqueue every vertex with no prerequisites
10
const queue = [];
11
for (const v of Object.keys(adj)) {
12
if (inDegree[v] === 0) queue.push(v);
13
}
14
15
// 3. Repeatedly take a free vertex and relax its edges
16
const order = [];
17
while (queue.length > 0) {
18
const v = queue.shift();
19
order.push(v);
20
for (const w of adj[v]) {
21
inDegree[w]--;
22
if (inDegree[w] === 0) queue.push(w);
23
}
24
}
25
26
// 4. Fewer than V placed => a cycle blocked the rest
27
if (order.length < Object.keys(adj).length) {
28
return null; // no topological order exists
29
}
30
return order;
31
}
- L3 Initialize every vertex's in-degree to 0.
- L5 Scan all edges; each edge u -> w adds 1 to w's in-degree.
- L11 A vertex with in-degree 0 has no unmet prerequisite: it can go first.
- L18 Pop a free vertex from the front of the queue (FIFO).
- L19 Append it to the output order.
- L21 Removing v: each neighbor loses one prerequisite.
- L22 If a neighbor's in-degree hits 0, it is now free; enqueue it.
- L27 If not every vertex was placed, the leftovers form a cycle: return null.
Key point: in-degree 0 means “ready”
A vertex is ready to be output only when every edge pointing into it has already been removed—that is, when its in-degree drops to 0. Kahn’s queue holds exactly the set of “currently ready” vertices. A vertex inside a cycle can never reach in-degree 0 (one of its prerequisites is itself, indirectly), so it never enters the queue. That is precisely why a leftover count below V signals a cycle.
Running Kahn’s algorithm on the course graph
DFS variant: push on exit, then reverse
1
function topoSortDFS(adj) {
2
const visited = new Set();
3
const stack = [];
4
5
function dfs(v) {
6
visited.add(v);
7
for (const w of adj[v]) {
8
if (!visited.has(w)) dfs(w);
9
}
10
stack.push(v); // push on EXIT: post-order
11
}
12
13
for (const v of Object.keys(adj)) {
14
if (!visited.has(v)) dfs(v);
15
}
16
17
return stack.reverse(); // reverse post-order = topological order
18
}
- L6 Mark v visited before exploring its outgoing edges.
- L8 Recurse into each unvisited neighbor (everything v depends on first).
- L10 Push v only after all its descendants finished: this is post-order.
- L13 Loop over all vertices so disconnected parts are covered too.
- L16 Reverse the finish order: a vertex now precedes everything it points to.
1
inDegree = { intro:0, data-structures:1, discrete-math:1,
2
algorithms:2, databases:1, ml:1 };
3
queue = [intro];
4
order = [];
Time complexity: O(V + E)
Kahn’s algorithm does a constant amount of work per vertex and per edge. Computing in-degrees scans every edge once: O(E). Finding the initial in-degree-0 vertices scans every vertex once: O(V). In the main loop, each vertex is enqueued and popped exactly once (O(V) total), and each edge is examined exactly once when its source vertex is popped and its neighbors are decremented (O(E) total). Summed: O(V + E).
The DFS variant is the same: DFS visits each vertex once and each edge once, plus a push per vertex—O(V + E).
Example: a dependency graph with 6 vertices and 6 edges (the course graph) runs in O(6 + 6) = O(12) work, independent of how the dependencies branch.
Space complexity: O(V)
The in-degree map stores one entry per vertex: O(V). The queue can hold up to V vertices when many become ready at once: O(V). The output order list holds up to V vertices: O(V). For the DFS variant, the visited set and the recursion stack are each O(V). Total: O(V).
(The adjacency list itself is O(V + E) of input, not counted as extra working space.)
Why fewer-than-V means a cycle
Cyclic graph: a -> b -> c -> a (plus an extra a -> d, d in-degree 1)
In-degrees: a:1, b:1, c:1, d:1 -> NO vertex has in-degree 0.
queue starts empty.
The while loop never runs.
order = [] (0 vertices placed)
0 < 4 -> return null: no topological order.
Every vertex in the cycle keeps an unmet prerequisite forever,
so none ever reaches in-degree 0. They are exactly the leftovers.A useful diagnostic: the vertices missing from the output are precisely those trapped in (or downstream of) a cycle.
In a topological order, an edge u -> v means:
A topological order exists for a directed graph if and only if the graph is:
In Kahn's algorithm, which vertices are enqueued first?
In the DFS-based topological sort, when is a vertex pushed onto the stack?
After Kahn's algorithm runs, how do you know the graph had a cycle (so no topological order exists)?
A dependency DAG has 10 vertices and 14 edges. The time complexity O(V + E) corresponds to how many total operations?
Why this works
Why two algorithms? Kahn’s is iterative, uses a queue, and gives cycle detection for free via the leftover count—handy when you also want to report which tasks are stuck. The DFS variant is shorter and reuses the DFS you already know; it is natural when you are already walking the graph for another reason. Both are O(V + E). Pick whichever fits the code you already have; the resulting orders may differ but are equally valid.
Common mistake
Forgetting it is not unique. Two tasks with no path between them can appear in either order, so the same DAG has many valid topological orders. Tests that check for one exact string are brittle. If you need a deterministic order (for reproducible builds), use a priority queue instead of a plain queue in Kahn’s, breaking ties by a fixed key (such as name). The plain-queue version here is deterministic only because the input key order is fixed.
Edge cases
Cycle means no answer, not a wrong answer. Topological sort is undefined for a graph with a cycle—there is genuinely no valid order. Do not return a partial list and pretend it is sorted. Return a clear signal (null, an empty result, or an exception) so the caller knows the dependency graph is broken. The leftover-count check (Kahn) or the in-progress back-edge check (DFS) is what surfaces this.
More practice
Where you will use it. Build systems order compilation units; package managers order installs; spreadsheets recompute cells; task schedulers run jobs; even resolving import dependencies is a topological sort. Whenever you have “X must happen before Y” constraints over a finite set, model them as a DAG and topologically sort. If the sort fails, you have just detected a circular dependency.
Explain what a topological order is, when it exists, how Kahn's algorithm and the DFS variant produce one, how each detects a cycle, and the complexity.
A topological order of a directed acyclic graph (DAG) lists every vertex before all vertices it points to: for each edge u → v, u precedes v. It exists if and only if the graph has no cycle, and is usually not unique.
Kahn’s algorithm: compute every vertex’s in-degree, enqueue the in-degree-0 vertices, then repeatedly pop one into the order and decrement its neighbors, enqueuing any that reach 0. If fewer than V vertices come out, a cycle blocked the rest.
DFS variant: run DFS, push each vertex on exit (post-order), then reverse the stack. A back edge to an in-progress vertex flags a cycle.
Time: O(V + E). Space: O(V). Both algorithms double as cycle detectors.
Topological sort is the engine behind build systems, package managers, schedulers, and dependency resolution. Next: ordered DAGs power shortest-path and scheduling algorithms.