Topological Sort and Cycle Detection
Definition
When does an order exist?
Suppose the graph has a cycle: A before B, B before C, C before A. No ordering is possible because all nodes must come before each other.
On the other hand, every graph with no cycles (a DAG) always has a topological ordering. This is because a DAG has at least one node with an in-degree of zero. From this, we can "peel" nodes off layer by layer without violating any dependency rules.
Deriving Kahn's algorithm
To start, we can push all the nodes with in-degree 0 to the stack, and remove it from the DAG. Once remove these nodes from the DAG, the nodes it used to point to are now of in-degree 0, and they too can be pushed to the stack, and removed from the graph. Continue doing this until no nodes remain, and the stack now contains a valid topological ordering.
Emitted nodes turn green. If the queue runs dry early, whatever is left over gets a shaded outline: it sits inside a cycle, or depends on one.
Every node starts tagged with its in-degree: how many arrows point at it. A, B and H already have nothing pointing at them, so they go straight into the ready queue.
Ready queuein-degree 0
Emitted, in order
In-degreestill blocking it
This is Kahn's algorithm—not only can it create topological orderings—it can also detect cycles. If the algorithm finishes with a stack that has fewer nodes than the graph contains, no nodes left contain an in-degree of zero, therefore there must be a cycle. An implementation of Kahn's algorithm is found in the sections below.
Emitted nodes turn green. If the queue runs dry early, whatever is left over gets a shaded outline: it sits inside a cycle, or depends on one.
Every node starts tagged with its in-degree: how many arrows point at it. A already has nothing pointing at it, so it goes straight into the ready queue.
Ready queuein-degree 0
Emitted, in order
In-degreestill blocking it
The other way to do it
If you need to do a depth-first search anyway, you can also use it to create a topological sorting.
Run a DFS on every node in the DAG. When a node finishes, meaning you have fully explored everything reachable from it, push it onto a list. At the end, reverse the list.
Detecting cycles takes one extra piece of state: if the DFS ever meets an edge back to a node that is currently open, meaning you are still inside its call, that is a cycle.
Kahn's version is easier to reason about and gives you the cycle check for free. The DFS version is more compact if you already have a DFS in front of you and do not want the in-degree bookkeeping. Both of these algorithms run in O(V + E) time and O(V) space.
The implementation
function topologicalSortKahn(nodeCount, edges) {
const adj = Array.from({ length: nodeCount }, () => []);
const inDegree = new Array(nodeCount).fill(0);
for (const [before, after] of edges) {
adj[before].push(after);
inDegree[after]++; // one more thing blocking it
}
const ready = [];
for (let v = 0; v < nodeCount; v++) if (inDegree[v] === 0) ready.push(v);
const order = [];
while (ready.length > 0) {
const v = ready.pop();
order.push(v);
for (const next of adj[v]) {
if (--inDegree[next] === 0) ready.push(next);
}
}
// Anything left un-emitted is stuck behind a cycle.
return order.length === nodeCount ? order : null;
}Returning null rather than a partial order is intended behavior which signals that the graph contains a cycle.
Common mistakes
Assuming the order is unique. It usually is not, tests that compare against one specific expected order will fail on a perfectly correct implementation unless the problem pinned down a tie-break.
Skipping the count check. Without it, a graph with a cycle returns a short list that looks like a valid order until something downstream breaks.
Forgetting isolated nodes. A task with no dependencies in either direction has in-degree 0 and belongs in the output. If you seed the ready collection from the edge list rather than from every node, those nodes vanish silently.
Check yourself
Kahn's algorithm emits 6 nodes on a graph with 8. What does that mean?