Topological sort by indegree (Kahn's algorithm)
A topological order of a directed graph lists every vertex so that each edge u → v goes from an earlier vertex to a later one. Read the edges as "u must happen before v" (a prerequisite, a build dependency) and a topological order is a schedule that breaks no rule. It exists exactly when the graph has no directed cycle, that is, when it is a DAG.
The indegree of a vertex is the number of edges coming into it: the number of its unfinished prerequisites. Kahn's algorithm (1962) works like a student picking courses: any vertex with indegree 0 has no prerequisites left, so it can go next. Output it, "delete" it by lowering the indegree of each of its successors, and some of them may now reach 0. Repeat until nothing is left.
Pseudocode
Kahn(G):
for each vertex v: indeg[v] = 0
for each edge u -> v: indeg[v] = indeg[v] + 1 // phase 1
S = empty stack // or a queue
for each vertex v:
if indeg[v] == 0: push v onto S // phase 2
order = empty list
while S is not empty: // phase 3
u = pop(S)
append u to order
for each edge u -> v:
indeg[v] = indeg[v] - 1 // remove edge u -> v
if indeg[v] == 0: push v onto S
if length(order) < n: report "graph has a cycle"
return order
The container S only has to hold "vertices that are ready". This page uses a stack (last in, first out); a queue or a priority queue works just as well, only the particular order produced changes.
Reading the animation
- The page's graphs are always DAGs: edges are only generated from a lower-numbered to a higher-numbered vertex.
- Phase 1: every edge is highlighted in turn and a circle travels to the Indegree array, where the target's entry goes up by one (the changed number flashes red). Edges are scanned vertex by vertex, neighbors in increasing number.
- Phase 2: each Indegree entry is highlighted; vertices with indegree 0 are copied into the Zero Indegree Vertices column, which is the stack. New entries are added below the old ones, so the bottom of that column is the top of the stack.
- Phase 3: the lowest entry is popped and moved to the Topological Order column, the vertex is highlighted and filled orange, and each of its outgoing edges lowers an indegree; a vertex whose indegree drops to 0 is pushed.
Worked example
Seven vertices with edges
0 -> 2 1 -> 2 1 -> 3 2 -> 4 3 -> 4 3 -> 5 4 -> 6 5 -> 6
Phase 1 counts incoming edges; phase 2 pushes the vertices with indegree 0 in increasing order:
vertex : 0 1 2 3 4 5 6 indeg : 0 0 2 1 2 1 2 stack (bottom ... top): 0 1
Phase 3, one line per pop (indegrees after the pop's decrements):
pop decrements indeg 0..6 pushed stack order 1 indeg[2]=1, indeg[3]=0 0 0 1 0 2 1 2 3 0 3 1 3 indeg[4]=1, indeg[5]=0 0 0 1 0 1 0 2 5 0 5 1 3 5 indeg[6]=1 0 0 1 0 1 0 1 - 0 1 3 5 0 indeg[2]=0 0 0 0 0 1 0 1 2 2 1 3 5 0 2 indeg[4]=0 0 0 0 0 0 0 1 4 4 1 3 5 0 2 4 indeg[6]=0 0 0 0 0 0 0 0 6 6 1 3 5 0 2 4 6 (no edges) 0 0 0 0 0 0 0 - empty 1 3 5 0 2 4 6
All 7 vertices were output, so the graph is acyclic and the answer is 1, 3, 5, 0, 2, 4, 6. Because the stack is last-in-first-out, vertex 0, pushed first, waits at the bottom until the branch through 3 and 5 is used up. With a queue instead (first in, first out) the same graph gives 0, 1, 2, 3, 4, 5, 6; both are valid. (Both traces were reproduced by running the page's loops in Node and checked against every edge.)
A graph with a cycle. Take 0 → 1, 1 → 2, 2 → 1, 2 → 3. The indegrees are 0, 2, 1, 1. Only 0 is ready; popping it lowers vertex 1 to 1, and then the stack is empty. Only 1 of the 4 vertices was output: vertices 1 and 2 wait for each other forever, and 3 waits for 2.
Why it is correct and why it detects cycles
- The output is a valid order. At every moment
indeg[v]equals the number of edges into v from vertices not yet output (each output vertex subtracts exactly its own edges once). A vertex is pushed only when that number is 0, so all its predecessors are already in the list: every edge u → v has u before v. - On a DAG every vertex gets output. Every non-empty DAG has a vertex of indegree 0: otherwise you could keep walking backwards along incoming edges forever, and with finitely many vertices you would revisit one, i.e. find a cycle. The vertices not yet output form a DAG themselves (a subgraph of a DAG), so while any remain, one of them has current indegree 0 and is waiting in the stack. The loop cannot stop early.
- On a graph with a cycle it stops early. Take the first vertex of a cycle that would be output. Its predecessor on the cycle has not been output yet, so its indegree is still at least 1 and it can never be pushed: no vertex on the cycle (nor anything reachable only through it) is ever output. Hence
length(order) < nis an exact cycle test, and the leftover vertices with positive indegree contain the cycle.
Running time and space
With adjacency lists, phase 1 touches every edge once, Θ(n + m). Phase 2 is Θ(n). In phase 3 every vertex is pushed and popped at most once, and each edge is decremented once when its tail is popped: Θ(n + m). Total Θ(n + m) time, and Θ(n) extra space for the indegree array, the stack and the output. With an adjacency matrix, as this animation uses, listing a vertex's edges scans a row of n entries, so phases 1 and 3 cost Θ(n2). Replacing the stack by a min-heap, to always output the smallest ready vertex, costs O((n + m) log n); stack and queue operations are O(1).
Common mistakes, edge cases and variants
- Skipping the final count. Without checking
length(order) == n, a cyclic graph silently yields a partial order. (This page never generates a cycle, so it does not show the check.) - Counting outdegree instead of indegree, or decrementing the popped vertex instead of its successors.
- Pushing a vertex twice: push only at the moment its indegree becomes exactly 0.
- Several sources, isolated vertices and disconnected graphs need no special care: all indegree-0 vertices are collected in phase 2.
- Ties and uniqueness. Whenever the stack holds two or more vertices, there is more than one topological order. The order is unique exactly when the stack never holds more than one vertex, which happens exactly when the graph has a path through all vertices (a Hamiltonian path).
- Queue by levels. Processing the queue one "round" at a time gives each vertex the earliest round in which it can be done: e.g. the minimum number of semesters for a course plan, or which tasks can run in parallel.
- The DFS alternative (TopoSortDFS.html) lists vertices in decreasing DFS finishing time. It has the same Θ(n + m) cost but uses recursion, and detects cycles through back edges instead of a leftover count.
Where it is used
- Package managers and build tools ordering dependencies and reporting circular dependencies.
- Task schedulers and workflow engines that start a job as soon as all of its inputs are done (the indegree is literally "number of unfinished inputs").
- Spreadsheet recalculation and detection of circular references between cells.
- Course planning, instruction scheduling in compilers, and evaluating neural-network or dataflow graphs layer by layer.