Start simple. Think about getting dressed. You put socks on before shoes, and a shirt before a jacket. Some things must come before others, but things that don't depend on each other — like socks and a hat — can be done in any order. A topological sort is just a to-do list that never asks you to do something before the things it depends on are finished.
Name the pieces. Draw each task as a node and draw an arrow from A to B whenever A must come before B. That picture is a directed graph. As long as there is no loop of "A before B before … before A" (which could never be satisfied), we call it a DAG — a Directed Acyclic Graph. The key number for each node is its in-degree: how many arrows point into it, i.e. how many unfinished prerequisites it still has. A node with in-degree $0$ has nothing blocking it, so it is ready to go. For example, shoes have one arrow coming in (from socks), so their in-degree is $1$; socks have none, so in-degree $0$, and socks go first.
Make it precise. Kahn's algorithm turns this into a recipe. Put every in-degree-$0$ node into a queue. Repeatedly remove one, append it to the answer, and for each arrow it points along, subtract $1$ from that neighbour's in-degree; the moment a neighbour drops to $0$, add it to the queue. Each node is enqueued exactly once and each edge is handled once, so the running time is $T = O(V+E)$ for $V$ nodes and $E$ edges. If the finished list is shorter than $V$, some nodes never reached in-degree $0$ — they are trapped in a cycle, so no valid ordering exists. When several nodes are ready at the same moment, any order among them is correct, which is exactly why one DAG can have many valid topological sorts.
Try this in the sim above. Press ▶│ (step forward) repeatedly to advance one step at a time and read the message bar as it narrates each move. Drag the n slider to change how many elements the stepper walks through, then replay from the start. Use the speed buttons (0.25× to 8×) to slow the trace right down so you can follow every comparison, then speed it back up.
§3 — Complexity Analysis & Derivation
Symbol
Meaning
n
Input size
T(n)
Time complexity
W(n)
Worst case
A(n)
Average case
Step 1 -- DAG Requirement. Topological sort only exists for Directed Acyclic Graphs (DAGs). If a cycle exists: no valid topological ordering (vertex in cycle can't come before itself). Kahn's algorithm detects cycles -- if output has fewer than V vertices, a cycle exists.
Step 2 -- In-degree and Source Vertices. In-degree of vertex v = number of incoming edges. Source vertices (in-degree=0) have no prerequisites -- they can start first. Initialize queue with all sources.
Step 3 -- BFS-based Processing. Dequeue a vertex u (all prerequisites satisfied). Add to result. For each outgoing edge (u,v): decrement in-degree[v]. If in-degree[v] reaches 0: v's prerequisites are all done, enqueue v.
Step 4 -- Time Complexity. Each vertex enqueued/dequeued once: O(V). Each edge processed once: O(E). Total: O(V+E). Same as BFS/DFS.
Step 5 -- Multiple Valid Orderings. If multiple vertices have in-degree 0 simultaneously: any order among them is valid. The choice depends on tie-breaking. To get lexicographically smallest: use a min-priority queue instead of FIFO queue.
A topological ordering of a DAG is a linear order of vertices such that for every directed edge (u,v), u appears before v. Intuition: if A must happen before B, A comes first in the ordering. Multiple valid orderings may exist.
How does Kahn's algorithm detect cycles? concept+
After processing, if len(result) < V: some vertices were never enqueued (their in-degree never reached 0). These vertices are all part of cycles (circular dependencies). The algorithm naturally detects this without extra DFS.
How does DFS-based topological sort differ from Kahn's? concept+
DFS: run DFS, record post-order timestamps, sort vertices by decreasing post-order. O(V+E). Kahn's (BFS): iteratively remove source vertices. O(V+E). Both give valid topological orders. Kahn's more naturally detects cycles and gives BFS-order topology.
Where is topological sort used in build systems? applied+
Makefile processes targets in topological order of dependencies. CMake, Gradle, Maven resolve build dependency graphs. npm/pip package managers resolve installation order. Linux kernel module loading order. Spring framework bean initialization order.
Can a graph have a unique topological sort? nonobv+
Yes -- if the DAG is a Hamiltonian path (a linear chain). Then there is exactly one topological ordering. In general, more DAG edges = fewer valid orderings. A complete DAG (Hamiltonian path) has exactly 1. An empty DAG (no edges) has n! orderings.
What is the Coffman-Graham algorithm? deep+
For scheduling tasks on 2 processors with DAG dependencies to minimize total completion time: uses a topological sort variant (Coffman-Graham, 1972). Assigns tasks to processors greedily in reverse topological order. O(V+E) preprocessing + O(V log V) scheduling. Optimal for 2 processors, approximate for k>2.
§5 — Misconceptions & Errors
Conceptual Misconceptions
✗ Topological sort works on any directed graph.
✓ Topological sort requires a DAG. Directed graphs with cycles have no valid topological ordering.
✗ Topological sort is unique.
✓ Unique only if the DAG is a linear chain (Hamiltonian path). Most DAGs have multiple valid topological orderings.
✗ DFS topological sort gives the same order as Kahn's.
✓ Both give valid topological orderings but usually DIFFERENT orderings. Both are correct. DFS gives reverse post-order; Kahn's gives BFS-level order.
Implementation Errors
✗ In-degree 0 means the vertex has no outgoing edges.
✓ In-degree = incoming edges count. Out-degree = outgoing edges. In-degree 0 means no prerequisites (nothing points TO this vertex), not that it points to nothing.
✗ Forgetting to check if result has V vertices (cycle detection).
✓ Without checking len(result)==V, the algorithm silently produces an incomplete ordering for cyclic graphs. Always validate output size.
✗ Re-initializing in-degree during the algorithm.
✓ In-degree values are decremented during processing. Re-initializing resets the algorithm. Only compute in-degrees once at the start.