Topological Sort

A directed acyclic graph (DAG) is a directed graph with no directed cycles. A topological order (or topological sort) of a DAG $G = (V, E)$ is a total ordering $v_1, v_2, \dots, v_n$ of the vertices such that for every edge $(u, v) \in E$, $u$ appears before $v$ in the ordering. Equivalently, it is any linear extension of the partial order induced by reachability in $G$. Topological order is generally not unique. If a DAG has vertices with no edges between them, they can appear in either relative order. What is invariant is the constraint structure: whichever valid order you produce, every dependency edge must point forward. The key theorem connecting this to DFS is: > A directed graph $G$ has a topological order if and only if $G$ is acyclic. One direction is obvious: if $G$ has a cycle $v_1 \to v_2 \to \cdots \to v_k \to v_1$, no linear order can place $v_1$ before $v_2$, ..., before $v_k$, before $v_1$ — a contradiction. The other direction is where DFS earns its keep: it gives a constructive method to build a topological order whenever no cycle exists, and — crucially — a way to detect that no ordering exists when a cycle does. Recall from DFS Edge Classification and Timestamps that every edge explored by DFS on a directed graph falls into exactly one of four categories, determined by the discovery time $d[v]$ and finish time $f[v]$ of each vertex:

• Tree edge: leads to an undiscovered vertex (part of the DFS forest).
• Back edge: leads to an ancestor in the current DFS tree (the fingerprint of a cycle).
• Forward edge: leads to a proper descendant already finished.
• Cross edge: leads to a vertex in a different subtree or a previously finished tree.

The central theorem tying DFS to cycle detection is: > A directed graph $G$ is acyclic if and only if a DFS of $G$ produces no back edges. Topological sort combines these two facts: run DFS (which, on a DAG, produces only tree, forward, and cross edges), record finish times, and output vertices from largest to smallest finish time. The proof below shows this order satisfies every edge constraint.

The mechanism is deliberately minimal — it is standard DFS with one addition: whenever a vertex finishes (all its outgoing edges explored), push it onto the front of a result list (or append to a list that gets reversed at the end). ``` TOPOLOGICAL-SORT(G): for each vertex u in G.V: u.color = WHITE u.pi = NIL time = 0 L = empty list // will hold the topological order for each vertex u in G.V: if u.color == WHITE: DFS-VISIT(G, u, L) return L // vertices in topological order DFS-VISIT(G, u, L): time = time + 1 u.d = time // discovery time u.color = GRAY for each v in G.Adj[u]: if v.color == WHITE: v.pi = u DFS-VISIT(G, v, L) else if v.color == GRAY: error "cycle detected: graph is not a DAG" // GRAY case above is a back edge; BLACK v is forward/cross, ignore u.color = BLACK time = time + 1 u.f = time // finish time L.prepend(u) // insert u at the FRONT of L ``` The only new step relative to plain DFS is `L.prepend(u)` at the moment `u` is finished (colored BLACK). Because each vertex is prepended to the front of the list exactly when it finishes, the list ends up ordered from latest finish time to earliest — which is precisely the order the algorithm must output. An equivalent, and often more common, implementation appends finish times to a stack and pops the stack at the end, or appends to a list and reverses it once at the end: ``` TOPOLOGICAL-SORT-ALT(G): run DFS(G), recording finish time f[u] for every u sort vertices by f[u] in decreasing order return that ordering ``` In practice one never actually sorts by finish time explicitly — the recursive structure of DFS already emits vertices in exactly the right order if you push each vertex onto a stack the moment it finishes.

Notice in the figure that `Algo` — which depends on `LinAlg`, `Stats`, and `Prog2` — finishes first among its "in-degree neighbors" from the DFS root chosen last, yet still lands at the end of the topological order, because it has the smallest finish time overall. This is exactly the subtlety the correctness proof addresses.

Time complexity: $O(V + E)$. The algorithm is unmodified DFS with $O(1)$ extra work (a list prepend) per finished vertex. DFS itself visits every vertex once ($O(V)$ vertex initializations and colorings) and examines every edge at most once ($O(E)$ across all adjacency-list scans), giving $O(V+E)$ total. This is asymptotically optimal: any correct algorithm must at least read the entire input (every vertex and edge), so $\Omega(V+E)$ is a lower bound, and the algorithm matches it.

Space complexity: $O(V)$ for the color/discovery/finish arrays, the recursion stack (or explicit stack in an iterative version), and the output list, plus $O(V+E)$ for the adjacency-list representation of the input itself (not extra working space).

Correctness proof. The claim to prove is: > If $G$ is a DAG, the list $L$ produced by decreasing finish time is a valid topological order — for every edge $(u,v) \in E$, $u$ precedes $v$ in $L$, i.e. $f[u] > f[v]$. Proof. Fix an edge $(u, v) \in E$. Consider the moment DFS first discovers $u$ (colors it GRAY). There are three cases for $v$'s color at that instant: 1. $v$ is WHITE. Then the edge $(u,v)$ is explored and becomes a tree edge (or DFS recurses into $v$ via this exact call). By the parenthesis structure of DFS — the fact that the intervals $[d[x], f[x]]$ for any two vertices are either nested or disjoint — $v$'s whole DFS visit (discovery through finish) is nested strictly inside $u$'s visit interval, because DFS-VISIT$(u)$ does not return until the recursive call on $v$ (and everything it spawns) completes. Hence $f[v] < f[u]$. 2. $v$ is GRAY. Then $v$ is an ancestor of $u$ in the current DFS tree, so $(u,v)$ is a back edge. But $G$ is a DAG by hypothesis, and the standard DFS cycle-detection theorem (from DFS Edge Classification and Timestamps) says a directed graph has a back edge in some DFS if and only if it has a cycle. A back edge here, together with the tree path from $v$ down to $u$, produces a directed cycle $v \to \cdots \to u \to v$ — contradicting acyclicity. So this case cannot occur. 3. $v$ is BLACK. Then $v$ has already finished, meaning $f[v]$ was already set — and it was set before $u$ finishes (indeed before $u$ was even necessarily discovered, or at least before $u$'s current exploration point). Since $u$ has not yet finished (we are still inside DFS-VISIT$(u)$, which hasn't reached its own finishing step), $f[u]$ will be assigned at some later time value than $f[v]$'s already-fixed value. So $f[u] > f[v]$. In every possible (non-error) case, $f[u] > f[v]$. Since $L$ lists vertices in decreasing finish-time order, $u$ appears before $v$ in $L$ whenever $(u,v) \in E$. This holds for every edge simultaneously, so $L$ is a valid topological order. $\blacksquare$ The proof is airtight because case 2 is ruled out by acyclicity — this is the one place the DAG hypothesis is used, and it is exactly why the algorithm doubles as a cycle detector: if DFS ever encounters a GRAY neighbor, the graph is not a DAG, and no topological order exists. A correct implementation must check for this and abort/report failure rather than silently returning a bogus order.

Tradeoffs. Topological sort via DFS is simple and asymptotically optimal, but it is not unique (many valid orders may exist) and does not itself find the "best" or "canonical" order under secondary criteria (e.g., lexicographically smallest — Kahn's algorithm with a priority queue is preferred there, at $O((V+E)\log V)$). The DFS-based method is also inherently recursive, so on extremely deep DAGs it may need an explicit stack to avoid recursion-depth limits in some languages.

Consider a small build system: source files with `#include` dependencies, where an edge $u \to v$ means "$u$ includes $v$, so $v$ must compile first." Suppose the dependency graph is: ``` main.c -> util.c main.c -> parser.c parser.c -> lexer.c parser.c -> util.c lexer.c -> util.c ``` Adjacency lists (iterated in this listed order): ``` main.c: [util.c, parser.c] util.c: [] parser.c: [lexer.c, util.c] lexer.c: [util.c] ``` Run DFS starting from `main.c` (first vertex in the outer loop):

Resulting finish times: `util.c`=3, `lexer.c`=6, `parser.c`=7, `main.c`=8. Reading off in decreasing finish-time order:

Check every edge points forward in this list:

• `main.c → util.c`: main.c is position 1, util.c is position 4. ✓
• `main.c → parser.c`: position 1 before position 2. ✓
• `parser.c → lexer.c`: position 2 before position 3. ✓
• `parser.c → util.c`: position 2 before position 4. ✓
• `lexer.c → util.c`: position 3 before position 4. ✓

Every dependency is respected: `util.c` compiles first (it depends on nothing), then `lexer.c`, then `parser.c`, then `main.c` — this exactly matches intuition, since `main.c` is the top-level file depending (directly or transitively) on everything else, and the sort correctly places it last, i.e., "compile last." Notice that `util.c` was discovered second but finishes first — it is a leaf with no dependencies, so DFS immediately closes it out. This is the crux of why topological order uses finish time, not discovery time: discovery order here would wrongly suggest `util.c` should come right after `main.c`, which happens to still work in this instance but is not the theorem being used — decreasing finish time is the property that is provably always correct.

Topological sorting as a combinatorial concept predates modern computer science — it is a special case of finding a linear extension of a partial order, studied in order theory throughout the 20th century. Its algorithmic formulation using DFS, however, is inseparable from the broader development of systematic graph-traversal techniques for digraphs, brought to computer science largely through the work on structured algorithm design and complexity analysis in the 1970s.

Build systems and compilers. Tools such as `make`, `ninja`, Bazel, and Gradle model source files, targets, and libraries as a dependency DAG; topological sort determines a valid compilation/linking order, and cycle detection catches circular dependency bugs before a build even starts.

Package and module managers. `npm`, `pip`, `apt`, and language module resolvers (Python imports, Java class loading) topologically order packages so that every dependency is installed or initialized before anything that needs it.

Spreadsheet and dataflow engines. Formula-dependency graphs in spreadsheets, and dataflow graphs in systems like Apache Spark or TensorFlow's static graph mode, are topologically sorted to decide a legal evaluation order that guarantees every input is computed before it is consumed.

Workflow orchestration. Systems like Apache Airflow, Argo Workflows, and CI/CD pipelines (GitHub Actions, GitLab CI) represent job dependencies as a DAG and use topological order to schedule jobs, often parallelizing independent branches of the order.

Course/task scheduling. University degree-audit systems and generic task schedulers with prerequisite constraints use exactly this algorithm to validate and generate feasible sequences.

Algorithmic foundation for further graph theory. Topological sort is the entry point to DAG-specific optimizations: single-source shortest paths on a DAG can be solved in one linear pass by relaxing edges in topological order — the very first specialization covered in the Single-Source Shortest Paths Framework — and critical-path analysis in project scheduling (PERT/CPM) is a direct application of this same DAG shortest/longest-path technique.

Ask the tutor: How does the topological order computed here get used to solve single-source shortest paths on a DAG in a single linear pass?