Dependencies as a directed graph
If task must precede task , draw an arrow . A topological order is a list containing every vertex once, with before for every arrow. A directed cycle makes such an order impossible: following its arrows would require a vertex to appear before itself.
Assume a finite directed multigraph with vertices and directed edges. Parallel arrows count separately, and a self-loop is a directed cycle. We study precedence only: a topological order is not by itself a schedule with durations, resource limits or minimum completion time. The empty graph has the empty order.
Definition 4.3.1
(Topological order and directed cycle)
Let be a finite directed multigraph with vertex set .
- A topological order of is a list in which every vertex of occurs exactly once and, for every directed edge , the vertex occurs before .
- A directed cycle is a sequence of edges with . For it is a self-loop.
- is acyclic if it has no directed cycle.
Remove vertices with no remaining predecessors
For every vertex maintain its indegree in the graph induced by vertices not yet removed. Initialize a queue with all zero-indegree vertices. Repeatedly remove a vertex from the queue, append it to the output, and for each outgoing edge decrement the destination's remaining indegree. Whenever a remaining destination reaches zero, add it to the queue. If the queue becomes empty, stop.
Theorem 4.3.2
(Ordering or a certificate of a cycle)
The algorithm outputs all vertices exactly when the graph has no directed cycle. If it outputs all vertices, their output order is topological. If it stops early, the remaining graph contains a directed cycle.
Proof
(Counters, output order and the stuck set)
Call a vertex removed once it has been taken from the queue, and let the counter of be the number of edges (with multiplicity) from unremoved vertices to . Initially nothing is removed, so each counter is the indegree. When is removed, each edge is decremented once, so the counters stay exact. A vertex enters the queue exactly when its counter reaches zero (or is zero at the start), and counters never increase, so each vertex is queued, and hence output, at most once.
Order. A vertex is queued only when its counter is zero, that is, when every predecessor has already been removed, and the counter stays zero until is removed. So every edge between output vertices has output before . If all vertices are output, the output is therefore a topological order.
Early stop. Suppose the queue is empty and the set of unoutput vertices is nonempty. A vertex of with counter zero would have been queued and then removed, so every vertex of has a positive counter: it has an incoming edge from a vertex of . Start at any and choose with , then with , and so on. Since is finite, some vertex repeats, say with . The edges read backwards form a directed cycle inside .
Cycle prevents full output. If all vertices were output, the output would be a topological order, which places the vertices of a directed cycle in positions with , which is impossible (for , ). So the algorithm outputs all vertices if and only if is acyclic.
Proof X-ray
Where the invariant and finiteness are used
The proof has two halves that use different facts. The order claim and the stuck-set claim both rest on one invariant: the counter of a vertex equals the number of its remaining in-edges, counted per edge. That equality is the only bridge between the algorithm's state (an empty queue) and the graph's structure (every remaining vertex has a remaining predecessor). The cycle-prevents-output half does not use the algorithm at all, only the definition of a topological order.
The non-obvious move is walking backwards through predecessors inside the stuck set. It terminates because the set is finite; on an infinite graph such as the integers with edges every vertex has a predecessor, yet there is no cycle. The repeated vertex closes the walk into a cycle. Nothing forces the walk to start on a cycle: it may begin at a vertex downstream of one, and only the repeated portion is the cycle.
For a concrete witness after an early stop, scan the edges of the remaining graph and store one remaining predecessor for each remaining vertex. Follow predecessor pointers until a vertex repeats; reverse the repeated pointer sequence to list its directed cycle. A self-loop yields a one-edge witness. This extra scan and traversal take time.
Proposition 4.3.3
(Linear running time)
With adjacency lists, the algorithm uses operations and auxiliary space, excluding the input graph and the output list.
Proof
(Each vertex and each edge is handled once)
Computing all indegrees scans each edge once. Each vertex is queued at most once, so it is removed at most once, and at its removal its outgoing edges are scanned once each. The total work is for vertices plus for edges. The queue, the counters and the output hold at most items each.
Worked scan and a subtle remainder
Worked example 4.3.4
(Independent choices give different orders)
Take vertices with edges , , , and . Initially have indegree zero. If the FIFO queue starts in that order, removing and makes available behind . The output is . It respects all four arrows; other queue orders can produce other valid topological orders.
Worked example 4.3.5
(A stopped run and its cycle witness)
Take , , , , . The counters are , , , , . Only is queued; removing it lowers to , and the queue is empty with the only output. The remaining vertices are . Store a remaining predecessor for each: , , , . Starting at the pointers give , and repeats. The repeated part is ; reversing the pointers gives the cycle . The walk began at , which is not on the cycle, and the first output vertex points into the cycle without being on it.
Worked example 4.3.6
(Parallel edges and a self-loop)
Take two parallel edges and one edge . The counters are , , . Removing decrements twice, once per edge, giving , so is queued. Removing lowers to . The output is . Now take a single vertex with a self-loop . Its counter is , nothing has counter zero, the queue starts empty, and the output is empty. The remaining graph is , with , so the pointer repeats at once and the witness is the one-edge cycle .
Counterexample mode
Not every remaining vertex lies on a cycle
With , , and , no vertex has indegree zero, so all three remain. The cycle is ; remains downstream of it but is not on a directed cycle. Early stopping proves that a cycle exists in the remainder, not that every remaining vertex belongs to one.
Common mistakes
Common mistake
(Decrementing once per neighbor instead of once per edge)
Suppose a graph has two parallel edges and nothing else into . The counter of starts at . An implementation that decrements once for each distinct out-neighbor of lowers it only to . Then is never queued, the algorithm stops with remaining, and it reports a cycle in an acyclic graph. The counter must track edges, so decrement once for every outgoing edge.
Common mistake
(Expecting the FIFO output to be the smallest order)
A FIFO queue does not generally produce the lexicographically smallest order. For with isolated , starting the queue as gives , while is smaller. To guarantee the smallest order under a fixed total ordering, a min-priority queue needs a separate rule and analysis; an arbitrary FIFO order makes no such promise.
Exercises
Quick check
(For , , , and isolated , give one topological order.)
Start from the vertices of indegree zero.
Solution · Answer
One order is : and precede , and precedes .
Quick check
(Explain why two parallel arrows require two indegree decrements when is removed.)
Compare the counter with the remaining graph.
Solution · Answer
Both are incoming edges to and both disappear when is removed. Decrementing only once leaves the counter inconsistent with the remaining graph.
Quick check
(For , , , identify a cycle and a vertex outside that cycle which remains.)
Find which vertices have indegree zero first.
Solution · Answer
The cycle is ; is not on it but remains because its predecessor remains.
Quick check
(Does a self-loop permit a topological order? What witness does the stopped algorithm return?)
Ask where the vertex would have to sit relative to itself.
Solution · Answer
No: it would require a vertex to precede itself. Following its remaining predecessor pointer returns that self-loop as a cycle witness.