Topological Sort Visualizer
Kahn's algorithm, one node at a time. The ready queue and every node's in-degree update as it runs, and building a cycle shows exactly what happens when no order exists: the queue runs dry with nodes left over.
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. shirt, trousers and socks already have nothing pointing at them, so they go straight into the ready queue.
How to use it
- Press Play to run it, or Step to advance one node at a time.
- Switch between the two built-in graphs: one is a valid order, the other is a genuine cycle.
- Watch the in-degree panel. A node joins the ready queue the instant its count reaches zero.
- On the cycle example, notice which nodes never turn green: they sit inside the cycle, or depend on something that does.
Common questions
What is a topological sort used for?+
Ordering tasks so every dependency comes before whatever needs it: build systems compiling files, package managers installing dependencies, spreadsheet formulas recalculating in the right order, and course prerequisite planning are all topological sorts in disguise.
Does a topological order always exist?+
Only when the graph is a DAG, a directed graph with no cycle. A cycle means A must come before B, which must come before A, and no linear order can satisfy both. Kahn's algorithm detects this for free: if it emits fewer nodes than the graph contains, whatever is left over is stuck in or behind a cycle.
Is the topological order unique?+
Usually not. Whenever more than one node is ready at the same time, the algorithm has a real choice, and a different pick produces a different, equally valid order. A problem expecting one exact answer has to specify a tie-break, such as always taking the smallest available node.
How is this different from a graph traversal like BFS?+
BFS explores outward from one starting node and answers questions about distance. A topological sort has no single starting point: it processes the whole graph at once, tracking how many unmet dependencies each node has left, and a node only becomes eligible once every dependency ahead of it has already been placed.