Topological Sort — Mathematics Knowledge System

Overview

A topological sort of a directed acyclic graph (DAG) is a linear ordering of its vertices such that for every directed edge (u, v), u appears before v in the ordering. Such an ordering exists if and only if the graph has no directed cycle — this is precisely why the graph must be a DAG. Topological sort is typically computed either via a DFS-based algorithm that appends vertices to the front of the order as they finish, or via Kahn's algorithm, which repeatedly removes vertices with in-degree 0. Topological sorts are generally not unique; a DAG can admit multiple valid orderings whenever some vertices are unconstrained relative to each other.

Intuition

Think of getting dressed: you must put on socks before shoes, and a shirt before a jacket, but socks and shirt have no required order relative to each other. A topological sort is any valid sequence respecting all these 'must come before' constraints simultaneously — exactly the problem faced by build systems (compile dependencies before dependents), spreadsheet software (recompute a cell only after its inputs), and course scheduling (prerequisites before the course they unlock).

Formal Definition

Definition

For a directed acyclic graph G = (V, E), a topological order is a sequence:

v_1, v_2, \dots, v_n \text{ such that } (v_i, v_j) \in E \Rightarrow i < j

Topological order condition

\text{A topological order exists} \iff G \text{ is acyclic}

Existence criterion

\text{Kahn's algorithm: repeatedly remove a vertex with } \deg^{-}(v) = 0 \text{, append it, update in-degrees}

Kahn's algorithm

Worked Examples

Compute in-degrees: A=0, B=1, C=1, D=2. Only A has in-degree 0, so remove it first.
$\text{Order: } A$
Removing A drops in-degree of B to 0 and C to 0. Process B next (alphabetically), then C, updating D's in-degree each time.
$\text{Order: } A, B, C$
After removing B and C, D's in-degree drops from 2 to 0 (both A→...→D paths' direct edges B→D, C→D are now accounted for). Remove D last.
$\text{Order: } A, B, C, D$

Answer: A, B, C, D (one valid topological order; B and C could also be swapped).

Practice Problems

Difficulty 3/10

A DAG has edges X→Y and Y→Z only (a simple chain). What is the unique topological order?

Difficulty 5/10

A spreadsheet has cells A1=B1+1, B1=C1+1, C1=A1+1 (each cell's formula depends on the next, forming a cycle). Can a topological sort of the dependency graph be computed? What does a real spreadsheet program do in this situation?

Difficulty 4/10

A DAG has edges A→C and B→C only (A and B both point to C, with no edge between A and B). List all valid topological orders.

Quiz

Summary

A topological sort orders a DAG's vertices so every directed edge points from earlier to later in the sequence.
Such an ordering exists if and only if the graph is acyclic; Kahn's algorithm builds it by repeatedly removing in-degree-0 vertices.
Topological sorts are generally not unique, and the same DFS/Kahn's-based ideas power build systems, spreadsheet recalculation, and course scheduling.

References

WebsiteWikipedia — Topological sorting