5.4 Topological sorting of DAGs

Motivation

Many scheduling problems are not asking for a numerical optimum. They ask for any legal linear order that respects a collection of prerequisites. A course must follow all of its prerequisite courses; a compiler must process a dependency before the file that imports it; socks must be put on before shoes. Some pairs may have no dependency at all, so their relative order is free.

A directed graph expresses exactly this situation. A vertex is a task, and an edge u -> v says that u must come before v. Topological sorting turns these local constraints into one global sequence. The central questions are:

• when does such a sequence exist?
• why might more than one sequence be valid?
• how can we construct one without repeatedly scanning the whole graph?
• how can failure of the construction certify a directed cycle?

Tutorial 10 develops two complementary answers. Kahn's algorithm works forward from tasks whose prerequisites are already satisfied. The DFS-based algorithm works backward from finishing events: a vertex is placed only after everything reached from it has finished. Both reveal more than an order; both can report that no order exists.

Definitions

Definition

Directed acyclic graph

A directed graph is a pair G = (V, E), where each edge is an ordered pair (u, v). A directed cycle is a sequence v_0 -> v_1 -> ... -> v_k -> v_0 with at least one edge. A directed acyclic graph, or DAG, is a directed graph with no directed cycle.

The direction matters. The edge u -> v is a constraint from u to v; it does not automatically include v -> u. An undirected cycle and a directed cycle are therefore different notions. Topological sorting concerns directed graphs and directed cycles.

Definition

Topological order

A topological order of G = (V, E) is a sequence containing every vertex exactly once such that, for every edge (u, v) in E, u occurs before v. Equivalently, if pos(x) is the position of x, then every edge satisfies pos(u) is strictly smaller than pos(v).

A topological order is not required to be unique. If neither x reaches y nor y reaches x, the graph may leave their relative order unconstrained. Different tie-breaking choices in an algorithm can then produce different, equally correct answers. A topological sort is therefore a constraint-satisfying order, not necessarily the order.

Definition

Indegree, source, and adjacency list

The indegree of v, written indegree[v], is the number of edges entering v. A vertex of indegree zero is a source. An adjacency list stores, for each u, exactly the outgoing neighbours v for which u -> v is an edge.

The adjacency list is a natural match for both algorithms in this unit. Once u is processed, they need to inspect precisely the edges leaving u, not an entire row of |V| possible neighbours.

For DFS cycle detection, a Boolean visited flag is not quite enough. We use three states:

• unmarked: DFS has not started at this vertex;
• temporary: the vertex is on the current recursion path;
• permanent: the vertex and all of its outgoing descendants have finished.

Encountering a temporary vertex means that an edge has returned to an ancestor on the current path. That edge closes a directed cycle.

Theorem/Proposition

Theorem

A directed graph has a topological order exactly when it is a DAG

If a directed graph contains a cycle, no topological order can satisfy all of its edges. Conversely, every finite DAG has at least one topological order.

The converse depends on a small structural fact: every nonempty finite DAG has a source. If every vertex had an incoming edge, start anywhere and repeatedly follow an incoming edge backward. Finiteness would eventually repeat a vertex, creating a directed cycle. Therefore some vertex has indegree zero, can be put first, and its removal leaves another DAG. Repeating this argument constructs an entire order.

Theorem

Kahn's processed-count criterion

Kahn's algorithm outputs all |V| vertices if and only if the graph is a DAG. If the zero-indegree container becomes empty after only k vertices, where k is smaller than |V|, and those vertices have been output, the unprocessed subgraph contains a directed cycle.

This gives a clean implementation rule: do not merely return the partial list. Count how many vertices were output and report a cycle when the count differs from |V|.

Theorem

Reverse DFS finishing order is topological

If DFS completes without encountering an edge to a temporary vertex, adding each vertex to the front of the output when it becomes permanent produces a topological order.

The word finishes is essential. Adding a vertex when DFS first discovers it does not guarantee that all prerequisite edges point forward in the final sequence. The ordering rule uses reverse finishing order, not discovery order.

Proof sketch or proof idea

Why a directed cycle is impossible to order

Suppose a directed cycle is v_0 -> v_1 -> ... -> v_k -> v_0. A topological order would require

pos(v_0), pos(v_1), ..., pos(v_k), pos(v_0) to be strictly increasing from left to right.

The first and last terms would make pos(v_0) strictly smaller than itself, which is impossible. This is stronger than saying that one drawn arrow happens to point left: every linear arrangement of the cycle's vertices must violate at least one edge.

Kahn's invariant and correctness

Maintain indegree[v] as the number of incoming edges from vertices that have not yet been output. Initially, one pass over all edges computes the real indegrees. Whenever u is output, scan adj[u] and decrement each successor's indegree once, thereby accounting for removal of exactly the edge u -> v.

The invariant has two consequences. First, a vertex enters the available set exactly when every predecessor has already been output, so appending it cannot violate an edge. Second, if unprocessed vertices remain but none has residual indegree zero, that remaining finite graph has no source. By the source fact above, it cannot be a DAG; it contains a cycle.

KAHN(adj, V):
    indegree[v] = 0 for every v in V
    for each u in V:
        for each v in adj[u]:
            indegree[v] += 1

    S = all vertices v with indegree[v] == 0
    order = empty list

    while S is not empty:
        remove one u from S
        append u to order
        for each v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                insert v into S

    if length(order) != |V|:
        return error "directed cycle"
    return order

S may be a queue, stack, set, or priority queue. That choice changes which valid order is returned, not the validity argument. A priority queue can force the smallest available label, but its extra logarithmic cost is not necessary for ordinary topological sorting.

DFS marks, finishing logic, and correctness

During VISIT(u), temporary vertices are exactly the current recursion stack. If an edge reaches a temporary v, the stack contains a path v -> ... -> u, and the new edge u -> v closes a cycle. An edge to a permanent vertex is safe: that vertex has already finished and already appears in the output.

If no cycle is found, consider any edge u -> v. When u is about to finish, either DFS reached and finished v from u, or v was permanent already. In both cases v is already in the output list. Prepending u therefore places u before v. Since the argument applies to every edge, the final list is topological.

DFS-TOPO(adj, V):
    mark[v] = UNMARKED for every v in V
    order = empty list

    for each vertex v in V:
        if mark[v] == UNMARKED:
            VISIT(v)
    return order

VISIT(u):
    if mark[u] == TEMPORARY:
        abort with error "directed cycle"
    if mark[u] == PERMANENT:
        return

    mark[u] = TEMPORARY
    for each v in adj[u]:
        VISIT(v)
    mark[u] = PERMANENT
    add u to the front of order

Complexity with adjacency lists

For Kahn's algorithm, initializing the arrays and finding initial sources costs O(V). Computing indegrees and later decrementing them examine each adjacency list entry once in each pass, hence O(E). With constant-time queue or stack operations, total time is O(V+E) and auxiliary state is O(V) beyond the O(V+E) graph representation.

DFS starts each vertex once and examines every outgoing edge once, so it also takes O(V+E) time. Its marks, output, and recursion stack use O(V) auxiliary space. An adjacency matrix would make neighbour scans cost O(V) per vertex, giving O(V^2) even when the graph is sparse.

Worked examples

Worked example

Checking an order and seeing non-uniqueness

Use the Tutorial 10 graph with edges

A->B, A->D, B->C, B->D, C->D, C->E, C->F, D->E.

The order A, B, C, D, E, F is valid: every edge's tail occurs before its head. The order A, B, C, D, F, E is also valid because no edge compares E with F. By contrast, A, B, C, E, D, F is invalid because D->E points from a later vertex to an earlier one. Checking adjacent pairs is not enough; every graph edge must be checked.

Worked example

Full Kahn trace on the Tutorial 10 graph

The initial indegrees are

A:0, B:1, C:1, D:3, E:2, F:1.

Only A is initially available. The following trace chooses F at the one branching point, matching the tutorial's illustrated run.

Step	Removed	Residual indegree changes	Available after step	Output
start	—	—	{A}	empty
1	A	B:1->0, D:3->2	{B}	A
2	B	C:1->0, D:2->1	{C}	A,B
3	C	D:1->0, E:2->1, F:1->0	{D,F}	A,B,C
4	F	none	{D}	A,B,C,F
5	D	E:1->0	{E}	A,B,C,F,D
6	E	none	empty	A,B,C,F,D,E

All six vertices are output, so the result is a valid topological order. At step 3, choosing D instead would also be safe and would lead to another valid order. The set of available sources is exactly where non-uniqueness becomes visible.

Worked example

Full DFS finishing trace on the same graph

Start DFS at B and inspect C's neighbours in the tutorial order F, E, D. Finishing F prepends it, then finishing E, D, C, and B successively changes the list as follows:

Finish event	Output after prepending
F	F
E	E,F
D	D,E,F
C	C,D,E,F
B	B,C,D,E,F

The outer loop then reaches unmarked A. Its successors B and D are already permanent, so A finishes immediately and is prepended. The final order is A,B,C,D,E,F. Notice that vertices enter the front in the reverse of their finishing sequence.

Worked example

The same cycle exposed in two ways

Add E->B to the tutorial graph. The edges B->C->E->B form a directed cycle (and B->C->D->E->B is another one).

Kahn removes A, after which no remaining vertex has residual indegree zero; it outputs only one of six vertices and reports a cycle. DFS starting at B temporarily marks B,C, finishes F, and then temporarily marks E, because C's neighbours are inspected in the stated order F,E,D. From E, the edge back to temporary B reports B->C->E->B immediately; D has not yet been visited. Neither algorithm should return its partial list as though it were a valid answer.

Common mistakes

Common mistake

Treating every displayed sequence as a topological order

A sequence is not valid merely because most arrows point forward or because each adjacent pair looks reasonable. Test every edge u->v and require pos(u) to be strictly smaller than pos(v).

Common mistake

Recomputing every indegree in every Kahn round

Repeatedly rescanning all edges can turn a linear graph pass into much more work. Compute the indegree array once, then decrement a successor exactly when one of its incoming edges is removed.

Common mistake

Calling Kahn's partial output a successful sort

An empty available set means success only when all vertices have been output. Otherwise the residual graph contains a cycle. Always compare the processed count with |V|.

Common mistake

Using one visited bit for DFS cycle detection

A visited vertex might be permanently finished or might still be on the active recursion path. Only the second case proves a directed cycle, so temporary and permanent marks must be distinguished.

Common mistake

Appending on DFS discovery

Topological DFS ordering uses the finishing event. Prepending at finish, or equivalently pushing at finish and reversing later, is what puts each vertex before its outgoing descendants.

Summary

• A topological order lists every vertex once and respects every directed edge.
• Such an order exists exactly for DAGs; a directed cycle creates contradictory before-relations.
• Kahn's algorithm maintains residual indegrees and repeatedly outputs a zero-indegree vertex. Fewer than |V| outputs certify a cycle.
• DFS uses unmarked, temporary, and permanent states. An edge to a temporary vertex certifies a cycle; reverse finishing order gives the topological order.
• Multiple available Kahn sources or different DFS exploration orders can produce different valid answers.
• With adjacency lists, both algorithms run in O(V+E) time and use O(V) auxiliary state beyond the graph storage.

Exercises

Checkpoint

1. In the Tutorial 10 graph, after Kahn outputs A and then B, what are the residual indegrees of C, D, E, and F, and which vertex is available next?

Update only the edges leaving the two vertices already removed.

Checkpoint

2. Suppose Kahn's algorithm outputs 7 vertices from a graph with 9 vertices and then its zero-indegree container becomes empty. What may the algorithm conclude?

Compare the processed count with the total vertex count.

Checkpoint

3. During DFS, an edge u->v reaches a permanently marked v. Does this prove a cycle? Explain the contrast with reaching a temporarily marked v.

Permanent means the recursive work at v has already returned.

Checkpoint

4. For edges P->R and Q->R, with no edge or path between P and Q, give two topological orders and explain why both are legal.

Both prerequisites must precede R, but they do not constrain each other.

Checkpoint

5. Explain from the adjacency-list loops, rather than by memorization, why Kahn's algorithm is O(V+E).

Count initial vertex work and the number of times an adjacency entry is read.

Solutions

Solution · Solution 1

After removing A, the residual indegrees are C:1, D:2, E:2, F:1 and B is available. Removing B changes C from 1 to 0 and D from 2 to 1. Thus the requested values are C:0, D:1, E:2, F:1, and C is the only available next vertex.

Solution · Solution 2

It must report that the graph contains a directed cycle. The two unprocessed vertices belong to a residual subgraph with no source; the seven-vertex prefix is not a topological order of the original nine-vertex graph.

Solution · Solution 3

No. A permanent v has already finished, so the edge can point to an already placed descendant or previously completed region without closing the current DFS path. A temporary v is still on the recursion stack. The stack gives a path v -> ... -> u, and u->v closes that path into a directed cycle.

Solution · Solution 4

Both P,Q,R and Q,P,R are valid. Each places P and Q before R, so both edges point forward. With no path between P and Q, their relative order is unconstrained.

Solution · Solution 5

Initializing arrays and collecting initial sources takes O(V). The indegree construction pass reads every adjacency entry once, for O(E). During the main loop every vertex is removed at most once and every outgoing adjacency entry is read once more when its edge is removed, giving another O(V+E). Adding these terms remains O(V+E).