Why does Kahn's topological sort return a short list rather than fail when the graph has a cycle?

## What the algorithm actually does Kahn's method is the emit-and-delete construction made concrete. Count incoming edges per node (`indeg`), seed a queue with every node whose count is zero, then repeatedly take a node out, append it to the output, and decrement the count of each node it points to — enqueuing any that hit zero. The loop condition is "the ready queue is non-empty". That is the whole algorithm, and reading it carefully is the point of the question: **there is no cycle test anywhere in it.** ## Why cycle nodes are never emitted The invariant is: a node is enqueued exactly when every one of its predecessors has already been emitted. Now take any node `c` on a cycle. It has a predecessor `p` on the same cycle. For `c` to be enqueued, `p` must first be emitted; for `p` to be emitted, its own cycle predecessor must be emitted; walk around the ring and the requirement returns to `c` itself. No node on the ring can be first, so none is ever enqueued, and the same argument extends to every node reachable from the ring, since those keep an undecremented incoming edge too. So the loop ends normally with the queue empty. It does not error, it does not loop forever, and the list it returns is a correct topological order of the part of the graph it managed to process. That is what makes the bug dangerous: the output is *valid*, just not *complete*. ## The check, and what it tells you Compare `length(order)` with the number of nodes: | Outcome | Meaning | |---|---| | `length(order) == V` | The graph is a DAG; the list is a full topological order | | `length(order) < V` | The graph has at least one cycle | | `length(order) > V` | Impossible — each node is emitted at most once | The unemitted set is not noise. It is exactly the union of all cycles and everything reachable from them, which is precisely the set a user needs to see. You can even name an actual cycle cheaply: among the leftover nodes, every one still has residual in-degree above zero, and the source of any such remaining edge is itself a leftover node. So walk backwards from any leftover node through remaining edges; the walk can never get stuck, and because the node set is finite it must revisit a node — and the segment between the two visits is a concrete cycle to print. ## Cost Building `indeg` touches every edge once: O(V + E). Every node is enqueued and dequeued at most once, and every edge is decremented at most once, so the main loop is also O(V + E). Extra space is O(V) for the counts plus O(V) for the queue, on top of the graph itself. The completeness check is a single integer comparison — the cheapest safety net in the whole algorithm, which makes omitting it indefensible rather than a performance tradeoff. ## Variations that do not change correctness The ready set does not have to be a queue. A stack works, and so does a heap keyed on anything you like. The invariant only says "emit a node whose predecessors are all emitted", and any node currently in the ready set satisfies that. Different disciplines yield different valid orders — the choice is about which order you want, never about whether the output is correct. ## The failure story The canonical incident: a recalculation or dependency pipeline runs the in-degree method, gets back a list, iterates it, and finishes green. Some nodes never ran because they were downstream of a small cycle someone introduced that week. Nothing crashed, nothing logged, the outputs from the skipped work were simply stale. The fix is not in the algorithm — the algorithm did what it says — it is the one assertion the caller never wrote. When you write this in an interview, add the length check and say out loud why it is there; it is a strong signal at middle level.