Topological sort
Each arrow means one task must happen before another. Count how many arrows point into each task. Anything waiting on nothing can go now; placing it removes its outgoing arrows, which may leave other tasks waiting on nothing. Repeat until every task is placed.
ready: front on the left
Each arrow means "must come before". Find an order where every node comes after everything it depends on.
1function topoSort(adj) {2 const indeg = new Array(adj.length).fill(0);3 for (const list of adj) for (const v of list) indeg[v]++;4 const ready = [];5 indeg.forEach((d, u) => { if (d === 0) ready.push(u); });6 const order = [];7 while (ready.length > 0) {8 const u = ready.shift();9 order.push(u);10 for (const v of adj[u]) {11 if (--indeg[v] === 0) ready.push(v);12 }13 }14 return order.length === adj.length ? order : null;15}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | V + E | every node and arrow is handled once |
| average | V + E | any graph |
| worst | V + E | the same for every graph |
| space | V | a count per node, plus the ready queue |
Where it breaks
- A cycle means no answer. Pick A cycle: B, C and D each wait on another, so their counts never reach zero and they are never placed. Placing fewer than all the nodes is how the algorithm reports a cycle.
- The order is not unique. Pick Getting dressed: A and E both wait on nothing, so either could go first. Any order the algorithm produces is valid, but different queues give different answers.
- Where it shows up. Build systems compiling files, spreadsheets recalculating cells, package managers installing dependencies, and course planners all solve this exact problem.