Pick an algorithm, enter your own numbers or use a preset, then step through the run. The pseudocode and the explanation follow each step.
Topological sort (Kahn's algorithm)
Order the nodes of a directed graph so every edge points forward. Repeatedly take a node with no incoming edges left. If some nodes never become free, the graph has a cycle.
Precondition: The graph must be directed.
Try it yourself
Add an edge to the valid preset that keeps the graph acyclic. Does the order still start with the same node?
Step through the run
Step 1 of 14
Queue (front on the left)45
waiting
current
finished
Count the incoming edges of every node. Nodes with none can go first.
Labels under values name their role, such as lo, hi, mid, i, j, min, L and R. Faded items are already ruled out or already in place.
