Topological sort

The problem it solves

Courses with prerequisites. Build targets with dependencies. Spreadsheet cells that reference other cells. Database migrations that must run in order. All of these are the same object — a directed graph where an edge A → B means “A must come before B” — and the same question: in what order can everything legally be done? A topological sort produces such an order, or proves that none exists, and the proof of impossibility has a name every engineer has cursed at: a circular dependency.

That dual output is the practical point. Topological sort isn’t just an ordering algorithm; it’s the standard cycle detector for directed graphs. When your build tool, package manager, or migration runner reports “dependency cycle detected”, this algorithm — or its DFS twin — is what noticed.

The intuition — and where it breaks down

Getting dressed. Socks before shoes, shirt before jacket — but socks-versus-shirt? No constraint at all, either order is fine. Each morning you effectively run Kahn’s algorithm: put on anything with no unmet prerequisites (socks, shirt — both “ready”), and each item you finish may unlock others (shoes become ready the moment socks are on). Keep dressing ready items until you’re dressed — or until you discover your belt requires your trousers which require your belt, at which point you are provably stuck.

The mechanism is counting, nothing deeper. Each item tracks its indegree — how many prerequisites remain. Ready means indegree zero. Completing an item decrements the indegree of everything it points to, and whatever hits zero joins the ready queue. When the queue empties, either everything got placed (a valid order, built greedily) or some items never reached zero — and those leftovers are exactly the members of cycles, each waiting on another forever.

Where the analogy misleads: mornings feel like they have one right order, but a DAG typically admits many — every moment the ready queue holds two items, either could go next, and the count of valid orders multiplies. “The topological sort” is almost always “a topological sort”. The visualization’s ready-queue panel makes the fan-out visible; the guiding question on the DAG preset asks you to watch for it.

Loading…

A walkthrough you can check

Edges: A→C, B→C, C→D, B→D. Indegrees: A:0, B:0, C:2, D:2.

1. Ready queue starts with both zero-indegree nodes: [A, B].
2. Place A. Its edge into C clears: C’s indegree 2 → 1. Nothing reaches zero. Queue: [B].
3. Place B. C: 1 → 0 — ready, enqueued. D: 2 → 1. Queue: [C].
4. Place C. D: 1 → 0, enqueued.
5. Place D. Four placed of four: valid order A, B, C, D.

Now add the edge D→B and rerun mentally: B starts at indegree 1, only A is initially ready, placing A clears C to 1 — and then the queue is empty with three nodes unplaced. B, C, D form the cycle (B→C→D→B), and the deficit itself is the detection: no separate cycle-finding pass, no extra code. Fewer than V placed ⟺ cycle. The visualization marks the stragglers rejected at that moment.

The invariant

Two clauses, both load-bearing. Every placed node had all its prerequisites placed before it — so the output order is valid by construction, not by later verification. The ready queue contains exactly the unplaced nodes with zero unplaced prerequisites — so the algorithm can never wedge while legal moves exist. Termination with a deficit therefore proves no legal move existed, which is the cycle certificate.

The indegree counter is the invariant’s bookkeeping: it must count only unplaced prerequisites, which is why it decrements at placement time and why a node enters the queue exactly once — at the moment its count first touches zero. Entering twice (a classic bug from checking == 0 in the wrong place) places a node twice and corrupts everything downstream.

Complexity, derived

Setup: one pass over edges to count indegrees — O(E) — and one pass over nodes to seed the queue — O(V). Main loop: each node enqueued and dequeued exactly once (O(V)); each edge decrements exactly one counter exactly once, when its source is placed (O(E)). Total O(V + E), the same shape as BFS because it is BFS’s discipline applied to constraint-clearing, with the counters panel confirming the edge-inspection count live.

Variants worth having loaded: replace the FIFO queue with a min-heap and the output becomes the lexicographically smallest valid order (cost: log factor) — a common problem variant. The DFS formulation — run DFS, emit nodes as their frames finish, reverse — produces a valid order in the same O(V + E), detects cycles via back edges instead of deficits, and is the one to reach for when you’re already inside a DFS for other reasons. Kahn’s advantage is operational: it yields items in executable order as it runs, which is what schedulers actually want.

What people get wrong

Validating the output on a cyclic graph instead of the count. On a cyclic input, Kahn’s happily emits the acyclic portion — a partial order that looks fine. The correctness check is placed == V, and forgetting it converts “cycle detector” into “cycle concealer”.

Seeding one zero-indegree node instead of all. The queue must start with every source. Starting from one produces a valid but incomplete exploration on forest-shaped DAGs — another bug that passes small connected tests.

Decrementing the wrong side. Placing A decrements the indegree of the nodes A points to. Reversed, the algorithm computes garbage that still terminates, which is the worst kind of wrong.

Assuming uniqueness. “Why might two runs give different orders?” is the follow-up; the answer — ties in the ready queue are unconstrained — is one sentence, plus the observation that a unique topological order exists iff the ready queue never holds two items, i.e. the DAG contains a Hamiltonian path.

Implementation notes across languages

Python: since 3.9, graphlib.TopologicalSorter ships in the standard library — it exposes prepare()/get_ready()/done(), which is Kahn’s dressed for concurrency (multiple ready tasks can run in parallel), and knowing it exists is a strong signal. Hand-rolled: deque + defaultdict(int). Java: ArrayDeque for the ready set; indegrees in an int[]. C++: same, queue<int> + vector<int>. In all of them the graph wants adjacency-list form; building indegrees from an edge list is the one O(E) preprocessing pass. The engineering note that outlives interviews: real dependency systems (npm, cargo, make -j) run exactly this algorithm with the ready queue feeding a thread pool — topological sort is parallel scheduling, which is the best one-line answer to “where would you use this?”.