Topological Sorting
List the vertices of a directed graph so that every edge points forward, like scheduling courses after their prerequisites. It's possible exactly when the graph is a Directed Acyclic Graph (DAG). Two ways to do it: reverse the pop order of a Depth-First Search (DFS), or keep removing sources.
Editing: click empty space to add a vertex · click vertex A, then vertex B, to add the edge A → B (click again to remove it; B then A reverses it) · drag to move · ✖ mode deletes a vertex or an edge. Ties are broken alphabetically.
How to read this
DFS-based. Blue is the vertex on top of the stack, yellow is the out-neighbor being checked, purple vertices are still on the stack, green ones have been popped. The small numbers are push, pop order. When a vertex is popped it takes the rightmost free slot in the line below, so the reversed pop order builds itself from right to left. A dashed purple edge is a back edge: it points to a vertex still on the stack, which closes a directed cycle (its vertices turn red).
Source removal. A source is a vertex with no incoming edges (in-degree 0, green in the table). Each step deletes one source and its outgoing edges, which lowers the in-degree of its neighbors (red cells). Deleted vertices fill the line from left to right. If vertices remain but none is a source, every one of them has an incoming edge, so there must be a cycle.
The line. The final order is drawn left to right with every edge as an arc. If the order is correct, every arrow points right.
Try this
- Courses preset, DFS-based: the pop order is C5, C4, C3, C1, C2, so the answer is C2, C1, C3, C4, C5. Switch to source removal: C1, C2, C3, C4, C5. Both are correct: a DAG can have several topological orders.
- Load the cyclic preset. DFS finds a back edge; source removal gets stuck with no source. Delete one edge of the highlighted cycle and run again.
- In the courses preset, add the edge C5 → C1. Predict which algorithm notices the cycle first (in steps). Try it.
- "Many sources" preset: how many vertices have in-degree 0 at the start? Source removal can pick any of them, which is why this graph has many valid orders.
- Levitin Exercise 4.2.4 asks if the push order would work too. Compare the push order with the answer on the courses preset to find a counterexample.