Info & Theory
A topological sort arranges the vertices of a
directed acyclic graph (DAG) into a line so that every
edge u → v points forward — u always
appears before v. It answers the question
"in what order can I do these tasks given their dependencies?".
Kahn's algorithm
Compute the indegree (number of incoming edges) of each vertex, then:
- Put every
indegree = 0vertex in a queue. - Dequeue a vertex and append it to the output order.
- For each successor, decrement its indegree; if it hits 0, enqueue it.
- Repeat until the queue empties.
Why acyclic matters
If the graph has a cycle, the vertices on it keep a positive indegree forever and never enter the queue. Kahn's algorithm therefore ends having placed fewer vertices than exist — and that shortfall is exactly how it detects a cycle. Try the Add edge button: an edge that points backward turns the DAG into a cyclic graph and the simulation reports that no order exists.
Many valid orders
Whenever two vertices have indegree 0 at the same moment, either may go next, so most DAGs admit many topological orders. A fully chained graph has exactly one; a graph with no edges accepts every permutation.
Complexity
Each vertex is enqueued and dequeued once and each edge is
inspected once, so Kahn's algorithm runs in
O(V + E) time — linear in the size of the graph.
Where it is used
Build systems (make, package managers) compile in
dependency order, course planners respect prerequisites,
spreadsheets recalculate cells, and compilers schedule
instructions — all by topologically sorting a dependency DAG.
About this simulation
This simulation builds a random directed acyclic graph (DAG) — a network of one-way connections with no loops — by only ever drawing edges from a lower-indexed node to a higher-indexed one, which mathematically guarantees the starting graph has no cycle. It then animates Kahn's algorithm: it computes every node's indegree (its number of incoming edges), places all indegree-zero nodes in a queue, and repeatedly dequeues one, appends it to the growing topological order, and decrements the indegree of its successors, adding any that reach zero. The Nodes slider (4–9) sets the graph size and the Speed slider controls how quickly Play advances through the steps.
🔬 What it shows
Each node displays an "in:" badge with its live indegree. A green ring marks an indegree-zero node sitting in the queue and ready to be placed; solid purple marks the node just removed this step; faded purple marks nodes already placed; grey nodes still have unmet dependencies. Edges fade once their source node is removed, and the growing topological order appears as a numbered list beside the canvas.
🎮 How to use it
Drag the Nodes N slider (4–9) to resize the graph and Regenerate to draw a fresh random DAG. Press Play to auto-run Kahn's algorithm (paced by the Speed slider) or Step to advance exactly one dequeue-and-decrement operation at a time. Add edge inserts one extra random edge — usually a forward edge that keeps the DAG valid, but sometimes a backward edge that creates a cycle for you to watch the simulation detect.
💡 Did you know?
Kahn's algorithm was published by Arthur B. Kahn in 1962 in "Topological sorting of large networks" and runs in O(V + E) time. Real build tools such as Make and Bazel use exactly this idea — treating files or packages as nodes and dependencies as edges — to decide a safe compile order and to report a hard error the moment they detect a dependency cycle.
Frequently asked questions
How does the simulation guarantee the starting graph has no cycles?
Every node is given a fixed index from 0 to N−1, and candidate edges are only ever added from a lower index to a higher index (i to j only when i < j). Because an edge can never point backward under this indexing, following any chain of edges always increases the index, so it is impossible to loop back to a node you started from — the graph is acyclic by construction, before Kahn's algorithm even runs.
What do the node colors and the "in:" badge mean?
The "in:" badge shows a node's current indegree, the number of edges still pointing into it. A green ring means indegree zero — the node has no unmet dependencies and sits in the queue ready to be placed. Solid purple marks the node just removed on this step, faded purple marks nodes placed on earlier steps, and plain grey nodes still have at least one unmet dependency.
What happens when I click Add edge?
Add edge inserts one new random edge and restarts the algorithm from scratch. About 60% of the time it chooses a forward edge (lower index to higher index), which keeps the graph a valid DAG. The rest of the time, or whenever no forward edge is left to add, it chooses a backward edge instead, which creates a cycle so you can watch the simulation's cycle detection react to it.
How does the simulation detect and report a cycle?
It runs Kahn's algorithm to completion, dequeuing and placing nodes until the queue empties. If every node has been placed, the sort succeeded. If the queue empties early while nodes remain unplaced, those nodes must lie on a cycle, since a cycle's indegree can never fall to zero, and the simulation lists them under "Cycle among" with a red banner drawn on the canvas.
What is the difference between the Step, Play, and Regenerate controls?
Step performs exactly one iteration of Kahn's algorithm: dequeue one indegree-zero node, append it to the order, and decrement the indegree of its successors. Play repeats that same step automatically, advancing roughly every 28 animation frames divided by the Speed slider value, until the queue is empty. Regenerate discards the current graph and draws a brand-new random DAG at the current Nodes N setting, resetting the algorithm state.