Topological Sort
Given a set of tasks with dependencies, produce an order in which each task comes after everything it depends on. Kahn's algorithm does it by repeatedly taking whatever currently has no unmet dependencies — and as a free bonus, if it ever runs out of such tasks with work remaining, it has proved your dependency graph has a cycle.
This isn't a canned animation. DryRun compiles and executes the code below, then draws every step from the real trace — the same values your machine would produce.
The code
int main() {
int n = 6;
vector<vector<int> > adj(n);
adj[5].push_back(2); adj[5].push_back(0);
adj[4].push_back(0); adj[4].push_back(1);
adj[2].push_back(3); adj[3].push_back(1);
vector<int> indeg(n, 0);
for (int u = 0; u < n; u++) {
for (int i = 0; i < (int)adj[u].size(); i++) indeg[adj[u][i]]++;
}
vector<int> order;
for (int i = 0; i < n; i++) if (indeg[i] == 0) order.push_back(i);
int head = 0;
while (head < (int)order.size()) {
int u = order[head++];
for (int i = 0; i < (int)adj[u].size(); i++) {
int v = adj[u][i];
indeg[v]--;
if (indeg[v] == 0) order.push_back(v);
}
}
if ((int)order.size() < n) cout << "cycle" << endl;
else for (int i = 0; i < n; i++) cout << order[i] << ' ';
return 0;
}The order vector doubles as the queue and the result, so the finished ordering is still there to inspect rather than being consumed.
How it works, step by step
In-degree counts unmet dependencies
indeg[v] is the number of prerequisites v still has. A node with in-degree zero has nothing blocking it and can be emitted immediately. The whole algorithm is a bookkeeping exercise on this one number.
Emitting a node releases its dependents
When u is placed in the order, every edge u to v is satisfied, so indeg[v] drops by one. A node joins the ready set at the exact moment its last prerequisite is emitted — not before, and only once.
Each node is enqueued exactly once
The push happens only on the transition to zero, which occurs once per node. That is why the ready set never contains duplicates and why the loop is linear.
A short output means a cycle
If some nodes never reach in-degree zero, they are all waiting on each other. The loop stops with fewer than n emitted, which is a proof of a cycle rather than a heuristic — a DAG always admits a full ordering.
The order is not unique
Whenever several nodes have in-degree zero simultaneously, any of them may go next. Different container choices produce different valid orderings, so tests that compare against one fixed expected sequence are testing the wrong thing.
Complexity
Building the in-degree array scans every edge once and the main loop scans every edge once more, so the cost is linear in graph size; the space is the in-degree array plus the ready set, both bounded by V.
Common bugs
Pushing when in-degree is merely low rather than zero
Writing if (indeg[v] <= 0) or pushing before the decrement enqueues a node while it still has unmet dependencies, producing an order that violates the constraints. Worse, a node can be pushed twice and appear twice in the output. The push belongs strictly inside the transition to exactly zero.
Treating a short result as success
If you print the order without checking its length against n, a cyclic graph produces a partial ordering that looks entirely plausible. The size check is the cycle detector, and skipping it turns a hard error into silently wrong output.
Counting out-degree instead of in-degree
It is easy to increment indeg[u] instead of indeg[adj[u][i]] when building the array. The algorithm then starts from sinks rather than sources and produces a reversed or nonsensical order. On a symmetric test graph it can even look correct.
Expecting one specific valid order
With several ready nodes at once, any of them is a legal next choice. Swapping the ready set from a queue to a stack changes the output entirely while both remain correct. If you need determinism, use a min-heap to always take the smallest id, and say so explicitly.
Each of these is easier to see than to describe — step through it and watch the values change. Run it in DryRun.
Frequently asked
What is a topological sort?
A linear ordering of a directed graph's vertices such that every edge points forwards — if there is an edge from u to v, then u appears before v. It models dependency resolution: build systems, course prerequisites, and task schedulers all need one. Only directed acyclic graphs have a topological order.
How does Kahn's algorithm work?
It counts each node's in-degree, starts with every node whose in-degree is zero, and repeatedly emits one of them. Emitting a node decrements the in-degree of each of its successors, and any successor that reaches zero joins the ready set. The process runs until the ready set empties.
How does topological sort detect cycles?
If the algorithm finishes with fewer than V nodes emitted, the remaining nodes form a cycle. Every node in a cycle depends on another node in that cycle, so none of their in-degrees can ever reach zero. This makes Kahn's algorithm a cycle detector at no extra cost.
Is the topological order unique?
Usually not. Any time two or more nodes have in-degree zero simultaneously, either can legitimately come next, so most graphs admit many valid orderings. The order is unique only when there is exactly one ready node at every step, which means the graph contains a Hamiltonian path.