Topological Sorting

Graph Theory

Chapter 5 · Topological Sorting

Chapter 4 answered a yes/no question: does this directed graph contain a cycle? When the answer is no — the graph is a DAG (Directed Acyclic Graph) — a much more useful question opens up: what's a valid order to process every vertex in, so that nothing is ever handled before something it depends on?

What a Topological Order Actually Is

A topological sort is a linear ordering of a DAG's vertices such that for every directed edge u → v, u comes before v in the ordering. It only exists for DAGs — Chapter 4's own cycle check is the precondition this chapter builds on. If A → B → A existed, no ordering could ever put both A before B and B before A.

Two genuinely different ways to build one

This chapter covers both, since they reuse the two traversal paradigms Chapter 3 already established: a DFS-based method (reusing Chapter 4's own three-color machinery directly) and Kahn's algorithm, a BFS-style method built on counting incoming edges.

Method 1: DFS-Based — Order by Finish Time, Reversed

Run a DFS exactly like Chapter 4's cycle check, but this time record each vertex the moment it turns black (fully finished — every descendant already processed). Push it onto a stack at that moment. Once the whole DFS is done, popping the stack — i.e. reading it in reverse finish order — is a valid topological order.

Why reverse: a vertex only finishes after all of its descendants have already finished, so it always finishes later than everything it points to — meaning it sits later in the raw finish-order stack. Reversing puts it back in front, ahead of everything it points to. Tracing it directly removes any doubt:

Graph: A→B, A→C, B→C.

Verified directly

DFS from A dives to B, then to C. C has no outgoing edges, so it finishes first (stack: [C]). Back at B, nothing left to explore, B finishes (stack: [C, B]). Back at A, its other neighbor C is already finished (black), so it's skipped — A finishes last (stack: [C, B, A]). Reversing gives the topological order [A, B, C] — exactly matching every edge pointing forward: A before B, A before C, B before C.

Method 2: Kahn's Algorithm — Process What's Ready

Kahn's algorithm works from the opposite direction, and maps much more directly onto how a real scheduler behaves: repeatedly find a vertex with no remaining unprocessed dependencies, output it, then "unlock" whatever becomes newly ready as a result.

The mechanism

Compute every vertex's in-degree (number of incoming edges). Put every vertex with in-degree 0 into a queue. Repeatedly: pop a vertex, output it, then decrement the in-degree of each of its neighbors — any neighbor that drops to 0 joins the queue. Stop when the queue is empty.

Same graph, traced with Kahn's algorithm:

Verified directly

In-degrees: A=0, B=1 (from A), C=2 (from A and B). Only A starts in the queue. Processing A outputs A and decrements B to 0 and C to 1 — B joins the queue. Processing B outputs B and decrements C to 0 — C joins the queue. Processing C outputs C. Result: [A, B, C] — identical to the DFS-based result on this graph.

A Topological Order Usually Isn't Unique

When two vertices have no dependency relationship between them at all, either can legally come first. A slightly larger graph makes this visible: A→C, B→C, C→D — both A and B feed independently into C, which feeds into D.

Method	Order produced
DFS-based	`[B, A, C, D]`
Kahn's algorithm	`[A, B, C, D]`

Both are correct — verified directly

A and B never have an edge between them, so neither ordering violates any dependency: every edge (A→C, B→C, C→D) still points forward in both lists. The two methods disagree only on the order of independent vertices, which is genuinely unconstrained — there is no single "the" topological order for a DAG with any parallelism in it, only a valid one.

Real Relevance: Build Systems & Package Installation

A compiler deciding which source files to build first, or a package manager deciding install order, is running a topological sort on exactly this kind of dependency DAG. Kahn's own framing maps directly onto the real process: "install everything with no remaining unmet dependencies, then see what that unlocks next" is precisely how tools like npm, pip, and make resolve a build order in practice — and it's the natural next step after Chapter 4's own cycle check, which confirms an order exists at all before this chapter finds one.

Topological Sort in Code

def topo_sort_dfs(adj):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {v: WHITE for v in adj}
    finish_stack = []
    def dfs(u):
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == WHITE:
                dfs(v)
        color[u] = BLACK
        finish_stack.append(u)
    for v in adj:
        if color[v] == WHITE:
            dfs(v)
    return finish_stack[::-1]

from collections import deque
def topo_sort_kahn(adj):
    in_degree = {v: 0 for v in adj}
    for u in adj:
        for v in adj[u]:
            in_degree[v] += 1
    queue = deque([v for v in adj if in_degree[v] == 0])
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    return order

deps = {'A': ['C'], 'B': ['C'], 'C': ['D'], 'D': []}
print(topo_sort_kahn(deps))  # ['A', 'B', 'C', 'D']

Hands-On Exercises

Exercise 1

Using this chapter's own DFS-based method, find a topological order for the DAG with edges X→Y, X→Z, Y→W, Z→W. Show the finish-order stack before it's reversed.

📄 View solution

Exercise 2

A build system has files with dependencies: utils.o is needed by both main.o and app, and main.o is needed by app. Using Kahn's algorithm, find a valid build order. Show the in-degree of each file at the start.

📄 View solution

Exercise 3

This chapter's own worked example (A→C, B→C, C→D) produced two different valid orders from its two methods. Explain, in terms of what a topological order is actually required to guarantee, why both [B, A, C, D] and [A, B, C, D] are correct answers rather than one being a mistake.

📄 View solution

Chapter 5 Quick Reference

Topological sort: a linear vertex ordering where every directed edge points forward — only possible on a DAG (Chapter 4's cycle check is the precondition)
DFS-based method: push each vertex when it turns black (finishes); reverse the finish-order stack
Kahn's algorithm: repeatedly output a vertex with in-degree 0, then decrement its neighbors' in-degrees
A topological order is usually not unique — vertices with no dependency relationship can appear in either order
Kahn's "process what's ready, unlock what's next" framing is exactly how build tools and package managers resolve install/compile order
Next chapter: Weighted graphs and shortest-path algorithms