Topological Sort

Definition

A topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge $u \to v$, vertex $u$ appears before vertex $v$ in the ordering. A topological ordering exists iff the graph is a DAG (no directed cycles). If cycles exist, no such ordering is possible: a cycle $a \to b \to c \to a$ would require $a$ before $b$ before $c$ before $a$, a contradiction.

DFS-Based Algorithm

Run a full DFS on the graph. As each vertex finishes (colour changes from grey to black), prepend it to a list. The final list is a topological order.

Pseudocode:

TOPOLOGICAL-SORT(G):
  for each v in G.V:
    v.colour = WHITE
  L = empty list         // will hold result
  for each v in G.V:
    if v.colour == WHITE:
      DFS-VISIT-TOPO(G, v)
  return L

DFS-VISIT-TOPO(G, u):
  u.colour = GREY
  for each v in G.Adj[u]:
    if v.colour == GREY: report "cycle exists"
    if v.colour == WHITE:
      DFS-VISIT-TOPO(G, v)
  u.colour = BLACK
  prepend u to L

Running time: $\Theta(|V| + |E|)$ with adjacency lists.

Why Reverse Finish Time?

For any edge $u \to v$ in a DAG, DFS produces $f[v] < f[u]$. Proof: when $(u,v)$ is explored, $v$ cannot be grey (that would be a back edge → cycle, impossible in DAG). If $v$ is white, $v$ becomes a descendant of $u$, so $f[v] < f[u]$ by the parenthesis theorem. If $v$ is black, then $f[v] < d[u] < f[u]$, so again $f[v] < f[u]$. In all cases $v$ finishes before $u$. Sorting by decreasing $f[v]$ therefore places $u$ (later finish) before $v$ (earlier finish), satisfying $u \to v$.

Source-Removal Algorithm (Alternative)

An alternative approach repeatedly removes sources (vertices with in-degree 0):

TOPOLOGICAL-SORT-SOURCES(G):
  compute in-degree[v] for all v
  Q = queue of all vertices with in-degree 0
  L = []
  while Q not empty:
    u = DEQUEUE(Q)
    append u to L
    for each v in G.Adj[u]:
      in-degree[v] = in-degree[v] - 1
      if in-degree[v] == 0:
        ENQUEUE(Q, v)
  if |L| != |V|: graph has a cycle
  return L

Also $\Theta(|V| + |E|)$. This version is sometimes called Kahn’s algorithm and has the advantage of detecting cycles explicitly (if $|L| < |V|$, a cycle exists).

Worked Example

DAG with vertices $\{A,B,C,D,E\}$ and edges: $A \to B$, $A \to C$, $B \to D$, $C \to D$, $D \to E$.

DFS method: Run DFS starting from $A$:

• Visit $A$ (d=1), then $B$ (d=2), then $D$ (d=3), then $E$ (d=4). $E$ finishes (f=5), $D$ finishes (f=6), $B$ finishes (f=7). Back to $A$, visit $C$ (d=8), $C$ finishes (f=9). $A$ finishes (f=10).
• Finish times (decreasing): A(10), C(9), B(7), D(6), E(5).
• Topological order: $A, C, B, D, E$.

Source-removal method:

• Initial in-degrees: A=0, B=1, C=1, D=2, E=1.
• Pick A (indeg 0). Remove A: decrease B→0, C→0. Queue: [B, C]. Output: [A].
• Pick B. Remove B: decrease D→1. Queue: [C]. Output: [A,B].
• Pick C. Remove C: decrease D→0. Queue: [D]. Output: [A,B,C].
• Pick D. Remove D: decrease E→0. Queue: [E]. Output: [A,B,C,D].
• Pick E. Remove E. Output: [A,B,C,D,E].

Both methods produce valid topological orders (note: A, C, B differs from A, B, C — both are valid since B and C are incomparable).

Applications

• Task scheduling: tasks with prerequisites; topological order gives a valid execution sequence.
• Build systems: make uses topological sort to determine which targets to build first.
• Course prerequisite planning: courses with dependencies form a DAG.
• SSSP on DAGs: relaxing edges in topological order solves SSSP in $\Theta(|V|+|E|)$, even with negative edge weights (but no cycles).

Summary

Property	Detail
Exists iff	Graph is a DAG
DFS method	Output in decreasing $f[v]$ order
Source removal	Repeatedly remove in-degree-0 vertices
Time (both)	$\Theta(V+E)$
DAG SSSP	Relax edges in topological order, $\Theta(V+E)$

Past paper questions: y2026p1q10 (topological sort algorithm, DAG transitive closure).