Topological sort
This is Kahn’s algorithm. It counts, for every node, how many edges point *into* it. Any node with a count of zero has nothing that must come before it, so it can be emitted next; removing it decreases the count of everything it points at, which may free more nodes. The queue holds exactly the nodes that are currently free.
Its frontier
A queue of nodes with nothing left before them.
When it is the right choice
Any time dependencies have to be turned into an order: build systems, module loading, course prerequisites, spreadsheet recalculation, task scheduling. It is also the cheapest reliable way to find out whether a directed graph has a cycle at all — which is what the next paragraph is about.
How it works
- Count the edges pointing into every node.
- Put every node with a count of zero into the queue.
- Take a node from the queue and add it to the order.
- For each edge leaving it, decrease the count at the other end.
- Any node whose count reaches zero joins the queue.
- If the order ends up shorter than the graph, the nodes left over are in a cycle and there is no valid order.
Worth noticing
- What happens with a cycle is the honest half of this page. Load the graph with a cycle: the queue empties while nodes remain, and the algorithm reports that no order exists and names the nodes that are stuck. It does not emit a partial order and call it an answer, which is the failure worth knowing about — a silently truncated topological sort is a build system that quietly skips a dependency.
- The order is not unique. Whenever the queue holds more than one node, any of them could be taken; this page takes the one added first, which makes the run reproducible but is not the only correct answer.
- Watch the queue rather than the graph. Every node in it is free right now, and the moment a node is emitted the queue can grow by several at once — which is what "these tasks can run in parallel" looks like.
Cost
- Best
- O(V + E)
- Average
- O(V + E)
- Worst
- O(V + E)
- Extra space
- O(V)
- Runs on
- a directed acyclic graph; a directed graph with a cycle
- Largest grid
- 11 by 7 cells
- Largest graph
- 14 nodes, 28 edges
The limits are pedagogical rather than technical: this tool keeps a cost and a predecessor for every node in every recorded step, so the size of the graph sets the size of the trace directly, and a run has to stay short enough to sit and watch. A graph that would take more than three thousand steps on this algorithm is refused before a single step is generated, from a formula in the number of nodes and edges rather than by running it and finding out.
Graphs are generated from a seed, so the link in your address bar draws exactly the graph on your screen — no part of it is random in a way a reload could change.