Topological Sort

Order a DAG so every edge points forward (Kahn's algorithm).

The idea

A topological order of a directed graph is a listing of all its vertices in which, for every edge $u \to v$, the vertex $u$ appears before $v$. Every edge points forward along the list.

The definition models scheduling. Give each job a vertex, and draw an edge $u \to v$ whenever $u$ must finish before $v$ may start; a topological order is then a schedule that never places a job ahead of one it depends on.

Not every directed graph has one. A directed cycle is a sequence of edges leading from a vertex back to itself along the arrows, and a graph containing one demands that some job precede itself. A directed graph with no directed cycle is a DAG, and the DAGs are exactly the directed graphs that can be topologically ordered. Kahn's algorithm produces the order and proves that claim.

Algorithm.

Algorithm: Kahn Input: a directed graph Output: a topological order of its vertices, or the report of a directed cycle 1. compute each vertex's in-degree // in-degree = the number of edges pointing into it 2. find a remaining vertex u of in-degree 0 // u depends on nothing that remains: safe to place next if none exists while vertices remain, return "directed cycle" 3. output u next; delete u and its outgoing edges // each deleted edge lowers its target's in-degree by 1 4. if vertices remain, go to step 2 5. return the vertices in the order output // a topological order

In an acyclic graph a vertex of in-degree $0$ always exists among those remaining, so the process never stalls before the graph is empty.

Ways to work on it

• Walkthrough. Topological order, validity, and why cycles block it.
• Practice. Decide whether an ordering is a valid topological sort.
• Hardest. Build a topological order step by step, then validate a proposed one.

Not sure where to start? Take the ten-question placement test.