Topological Sort Visualizer — Kahn's

A topological order lists the nodes of a directed graph so that every edge points forward: prerequisites before the courses that need them, a build step before the steps that use its output, socks before shoes. This Topological Sort Visualizer runs Kahn’s algorithm on a graph you type and lets you watch it one step at a time: which node is taken, which edges disappear, which in-degrees fall to zero and join the queue.

Worked Example: The Six-Node Classic

The tool opens on the graph most tutorials use: 5 2, 5 0, 4 0, 4 1, 2 3, 3 1.

• Start: 4 and 5 have no incoming edges, so both go in the queue.
• Take 4: its edges to 0 and 1 go, leaving each with in-degree 1.
• Take 5: 0 and 2 drop to 0 and join the queue.
• Then 0, 2, 3 and 1, giving the order 4 5 0 2 3 1 in six steps.

Because two nodes were ready at the start, the tool notes that other orders are also valid. Load Sample moves on to getting dressed with named nodes, a chain of course prerequisites, and a graph with a cycle.

How the Math Behind Kahn's Algorithm Works

Count each node’s incoming edges, its in-degree. Every node with in-degree 0 can go first, so it enters a queue. Repeatedly take a node from the queue, append it to the order and delete its outgoing edges; any neighbour whose in-degree reaches 0 joins the queue. Each node and each edge is handled once, so the whole run is O(V + E). With Smallest label first the queue becomes a min-heap, which returns the lexicographically smallest of all valid orders at O((V + E) log V); on the dressing example that puts shirt, socks and tie ahead of undershorts. The drawing places each node in the column of its longest path from a source, so every arrow points to the right.

Edge Cases: Cycles, Self-Loops and Ties

If the queue empties before every node is ordered, the leftovers lie on or behind a cycle, and no topological order exists. The tool then searches those nodes for an actual loop and prints it, such as 2 → 3 → 4 → 2, outlined in red on the drawing. A self-loop is caught before the run with ““1 1” is a self-loop, so no topological order can exist.” Repeated edges are counted once, and the drawing handles up to 60 nodes and 400 edges. The order is the only valid one exactly when a single node was ready at every step.