Topological sort
mediumIndegree zero means nothing is waiting on this. If the queue empties while vertices remain, those vertices are waiting on each other - a cycle, detected with no extra check.
O(V + E)Space O(V)Saved in this browser - no sign-up, nothing sent anywhere.
How topological sort works
A topological order lines up a directed acyclic graph so every edge points forward - dependencies before dependents. Kahn's algorithm, the variant implemented here, builds it from one observation: a vertex with indegree 0 has no unmet prerequisites, so it can safely go first. Output it, delete its outgoing edges, repeat.
Deleting edges is just decrementing counters. When you output u, each successor v loses one pending prerequisite; when indeg[v] hits 0, v joins the ready queue. Every vertex is processed once and every edge decremented once, which is where O(V + E) comes from.
Cycle detection falls out for free. If the queue empties while vertices remain, each leftover vertex still waits on another leftover - they form a cycle, and no valid ordering exists. No colours, no recursion stack, just comparing the output length against V. That is exactly how build tools report circular dependencies.
Step by step
- Count indegrees over the 8-node DAG: A and B have none, D waits on two vertices, H waits on F and G.
- Seed the queue with A and B - nothing blocks them, so either could legally start the order.
- Output A. Its successors lose a prerequisite: C drops to 0 and joins the queue; D drops to 1, still blocked by B.
- Output B. Now D and E both hit indegree 0 - the queue holds C, D, E, any of which may come next.
- C, D and E drain in turn, freeing F and G the moment their last incoming edge is deleted.
- H is freed last, after both F and G. Final order A, B, C, D, E, F, G, H - all 8 output, so no cycle exists.
Complexity
| Worst case time | O(V + E) |
|---|---|
| Space | O(V) |
Reference implementation
Python
from collections import deque
def topo_sort(adj, n):
indeg = {u: 0 for u in adj}
for u in adj:
for v in adj[u]:
indeg[v] += 1
q = deque(u for u in adj if indeg[u] == 0)
out = []
while q:
u = q.popleft()
out.append(u)
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
if len(out) < n:
raise ValueError("graph has a cycle - no valid ordering")
return outJavaScript
function topoSort(adj) {
const indeg = new Map([...adj.keys()].map((u) => [u, 0]));
for (const [, vs] of adj) for (const v of vs) indeg.set(v, indeg.get(v) + 1);
const q = [...indeg].filter(([, d]) => d === 0).map(([u]) => u);
const out = [];
for (let h = 0; h < q.length; h++) {
const u = q[h];
out.push(u);
for (const v of adj.get(u) ?? []) {
indeg.set(v, indeg.get(v) - 1);
if (indeg.get(v) === 0) q.push(v);
}
}
if (out.length < adj.size) throw new Error("cycle detected");
return out;
}Worth noticing
Indegree zero means 'nothing is waiting on this'
A vertex with no incoming edges has no unmet prerequisites, so it can be output immediately. Removing it may free others - which is why the count drops as the algorithm proceeds.
The leftover count detects cycles for free
If the queue empties while vertices remain, those vertices form a cycle: each is waiting on another in the group, so none ever reaches indegree 0. No separate cycle check is needed.
The ordering is usually not unique
Whenever two vertices sit at indegree 0 simultaneously, either may come first. Any valid topological order is a correct answer - which is why build systems and schedulers can parallelise exactly those vertices.
This is what a build system does
Make, Gradle, npm's dependency resolution, spreadsheet recalculation, course prerequisites - all of them topologically sort a dependency graph, and all of them report a cycle as an error.
Common pitfalls
- Skipping the final count check. On a cyclic graph the queue quietly empties early, and without comparing output length to V you return a truncated order as if it were valid.
- Assuming the order is unique. Whenever two vertices sit at indegree 0 together - like D and E here - either may come first, and any valid order is correct.
- Computing indegrees from the adjacency map keys instead of its values. Outgoing lists count out-degree; you must increment the counter of each edge's target.
- Running it on an undirected graph. Topological order is only defined for DAGs - an undirected edge is already a two-vertex cycle.
- Rebuilding the graph to delete edges physically. Decrementing an indegree counter is the deletion; mutating adjacency lists costs extra and breaks reuse.
Where it is used
- Build systems - Make, Gradle, Bazel - compile targets in dependency order and report cycles as errors.
- Package managers resolving install order, and spreadsheets deciding which cells to recalculate first.
- Course Schedule I and II on LeetCode, the canonical interview framing of this exact algorithm.
- Task schedulers parallelising safely: everything simultaneously at indegree 0 can run concurrently.
Frequently asked questions
What is the time and space complexity of topological sort?
O(V + E) time: computing indegrees touches every edge once, then each vertex is queued and dequeued once and each edge decremented once. Space is O(V) for the indegree counters, the queue and the output list.
How does Kahn's algorithm detect a cycle?
By what it fails to output. Vertices on a cycle wait on each other, so none ever reaches indegree 0 and none is ever queued. If the algorithm ends with fewer than V vertices output, the leftovers contain a cycle - no extra machinery needed.
Kahn's algorithm vs DFS-based topological sort - which should I use?
Both are O(V + E). Kahn's - the version here - is iterative, yields vertices in dependency layers, and detects cycles by a simple count. The DFS variant reverses finishing order and needs recursion plus explicit cycle tracking. Kahn's is usually easier to reason about in interviews.
Is the topological order of a DAG unique?
Only when the queue never holds two vertices at once, which forces a single chain - equivalently, when the DAG has a Hamiltonian path. Otherwise several valid orders exist, and schedulers exploit that freedom to run independent vertices in parallel.