Topological Sort is dependency resolution in graph form: it orders the tasks in a Directed Acyclic Graph (DAG) so that every prerequisite appears before the work that depends on it.

Kahn’s algorithm is the intuitive version — repeatedly pick a task with no remaining prerequisites (in-degree 0), “complete” it, and unblock everything waiting on it.

How It Works

1. Compute in-degrees: count the incoming edges of each vertex.
2. Seed the queue: enqueue all vertices with in-degree 0 — they have no dependencies.
3. Process: dequeue a vertex, append it to the result, and decrement the in-degree of every neighbor.
4. Detect new roots: whenever a neighbor’s in-degree hits 0, enqueue it.
5. Repeat until the queue is empty. If the result contains all vertices, the sort succeeded; otherwise a cycle exists.

Key Insight

A DAG always has at least one in-degree-0 vertex. Kahn’s algorithm exploits that by peeling: each peel “removes” a dependency-free vertex, which may create new in-degree-0 vertices.

If the process stalls with vertices still unprocessed, the graph must contain a cycle (mutual dependencies) — no valid order exists. The resulting sequence satisfies every edge direction: u always precedes v when u → v.

Worked Example

Run Kahn’s algorithm on the visualizer’s DAG preset:

• In-degrees: A=0, B=1, C=1, D=1, E=2, F=2, G=1.
• Queue [A] → process A → B and C drop to in-degree 0 → queue [B, C].
• Process B → D in-degree 0, E in-degree 1 → queue [C, D].
• Process C → E in-degree 0 → queue [D, E].
• Process D → F in-degree 1 → queue [E].
• Process E → F in-degree 0 → queue [F].
• Process F → G in-degree 0 → queue [G] → process G.

Result: A, B, C, D, E, F, G — every edge points forward in this sequence. Note that the order isn’t unique: C before B would also be valid.

Edge Cases & Pitfalls

• Cycles — if the result is shorter than V, the graph is cyclic: no topological order exists. This is also the standard cycle-detection check.
• Multiple valid orders — any order respecting edges is correct; Kahn’s returns whichever the queue order produces.
• Disconnected DAGs — multiple roots seed the queue; the result still interleaves components correctly.
• Self-loops — a node with an edge to itself keeps in-degree ≥ 1 forever: correctly reported as a cycle.

Comparison With DFS Ordering

Applications

• Build systems (Make, Bazel) — compiling modules in dependency order
• Package managers (npm, pip, apt) — resolving dependency graphs
• Course prerequisites — a valid sequence of classes
• Task scheduling — ordering jobs under constraints
• Spreadsheet recalculation — ordering cell dependencies

Practice Trajectory

1. Hand-run Kahn’s algorithm on the visualizer DAG starting from the same in-degree table.
2. Construct a second valid ordering and explain why both are correct.
3. Add one edge that creates a cycle and show which vertices remain unprocessed.
4. Explain why topological sort requires a DAG, not just a directed graph.
5. Implement Kahn’s algorithm and detect a cycle by comparing result size to vertex count.