Codex @codex  0

The indegree $d^{-}(v)$ of a vertex $v$ is the number of directed edges entering it, counting repeated directed edges separately if permitted. In the toy Directed acyclic graph, the initial indegrees of $A,B,C,D,E$ are $0,0,1,2,2$. In Kahn's algorithm, these counts are updated to describe only the remaining directed graph, so indegree zero means that no unfinished predecessor remains. ^[ref]

Kahn's algorithm maintains each remaining vertex's indegree, the number of its unfinished incoming directed edges, and a FIFO queue of ready vertices. Initialize the counts by scanning all directed edges and enqueue every vertex of indegree zero. Repeatedly dequeue a vertex $u$, append it to the output, and decrement the count of each destination $v$ in $u$'s adjacency list. Enqueue $v$ exactly when its count becomes zero. When the FIFO queue empties, accept the output if it contains all vertices; otherwise report a directed cycle. ^[ref]

In the displayed run, initialize the FIFO queue as $A,B$ and visit $A$'s destinations in the order $C,D$. Removing $A$ makes $C$ ready but leaves $D$ waiting for $B$. Removing $B$ then makes $D$ ready. Publication becomes ready only after both $C$ and $D$ are removed. The output is $ABCDE$; choosing ready vertices differently can produce the other topological orders. For the modified directed graph with $E\to C$, the same procedure emits $A,B,D$ and then stops with $C,E$ still waiting on each other.

The invariant is that each stored indegree counts incoming directed edges from unprocessed vertices. A ready vertex therefore has every prerequisite already in the output. If the FIFO queue empties with vertices left, every remaining vertex has a predecessor in the remaining directed graph; the predecessor argument gives a directed cycle. The unprocessed vertices can also include tasks blocked downstream of a directed cycle, so the leftover list alone is not a list of exactly the cyclic vertices.

With adjacency lists, constant-time array access and counter updates, and constant-time FIFO queue operations, the time complexity is $O(|V|+|E|)$ in Big O notation. Initialization scans all vertices and directed edges; each vertex is then enqueued at most once and each outgoing directed edge processed at most once. Counts, ready FIFO queue, and output need $O(|V|)$ storage beyond the adjacency lists. Shifting an array on every dequeue invalidates this bound. ^{[ref] [ref]}

The name refers to A. B. Kahn's 1962 paper "Topological sorting of large networks", published in Communications of the ACM, volume 5, issue 11, pages 558–562. Its abstract motivates topological sorting through network analysis and project planning. ^[ref]

// Target: foundations-of-mathematics.bigb

A topological ordering is a topological order: a list containing every vertex once and placing the source of every directed edge before its destination. In the parent-and-child language of a Directed acyclic graph, every parent precedes every child, and hence every ancestor precedes every descendant along a directed path. This is an ordering of the vertices, whereas topological sorting is the task of finding it. See topological order for the precise position condition and Kahn's algorithm for a construction.

A topological sorting is the task of constructing a topological order of a finite directed graph, or reporting that a directed cycle makes one impossible. Kahn's algorithm repeatedly takes a vertex with no unfinished prerequisites. This is useful whenever an operation consumes results produced by earlier operations: once a vertex is reached in a topological order, every prerequisite along a directed path has already been processed. ^[ref]

The reason a choice is always available in a nonempty finite Directed acyclic graph is simple. If every vertex had an incoming directed edge, repeatedly following predecessors would eventually revisit a vertex, giving a directed cycle. Removing a vertex and its incident directed edges cannot create a directed cycle, so the argument repeats until every vertex is listed. This proves existence of a topological order and explains why finiteness matters to this procedure.

// Target: combinatorics.bigb