= Kahn's algorithm
{c}
= Kahn algorithm
{c}
{synonym}
<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>. https://raw.githubusercontent.com/kevin-wayne/algs4/master/src/main/java/edu/princeton/cs/algs4/TopologicalX.java[Sedgewick and Wayne, TopologicalX: queue-based topological sorting]{ref}
\Image[/kahn-ready-queue-and-cycle.png]
{title=Computed ready-queue trace and the obstruction caused by a reverse dependency}
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. https://raw.githubusercontent.com/kevin-wayne/algs4/master/src/main/java/edu/princeton/cs/algs4/TopologicalX.java[Sedgewick and Wayne, TopologicalX: time and extra-space bounds]{ref} https://raw.githubusercontent.com/kevin-wayne/algs4/master/src/main/java/edu/princeton/cs/algs4/Digraph.java[Sedgewick and Wayne, Digraph: adjacency lists and outgoing-edge iteration]{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. https://doi.org/10.1145/368996.369025[Kahn, Topological sorting of large networks (1962): publisher's record and abstract]{ref}
// Target: foundations-of-mathematics.bigb
Back to article page
