Topological Sorting (DAG Ordering)

Linear ordering of DAG nodes respecting edge directions; basis for dependency resolution and DAG dynamic programming.

Overview

A topological order of a directed acyclic graph (DAG) arranges vertices linearly so every directed edge u→v places u before v. It exists iff the graph has no directed cycle.

Applies To

DAGs

Output

Linear order

Variants

Kahn / DFS

Core Approaches

Kahn's Algorithm: Maintain vertices with in-degree 0 in queue; remove layer by layer.
DFS Postorder: Reverse finishing times of DFS on DAG.
Kahn gives natural cycle detection (leftover vertices).

Use Cases

Build / compile dependency resolution
Task scheduling with prerequisites
Course prerequisite ordering
Linearization before DP on DAG (longest path, etc.)

Complexity

Time

O(n + m)

Space

O(n + m)

Queue / Stack

O(n)

Both Kahn and DFS traverse each vertex and edge once ignoring constant overheads.

Cycle Detection

Kahn: If queue empties early and not all vertices output ⇒ cycle exists.
DFS: Detect back edges using color/recursion stack.

Comparison

Method	Mechanism	Cycle Signal	Stability
Kahn	Queue of in-degree 0	Remaining vertices	Depends on queue order
DFS	Reverse finish times	Back edge	Depends on DFS order

Quick Facts

Graph Type: Directed Acyclic (DAG)
Multiple Orders: Usually non-unique
Detects Cycles: Yes (implicitly)
Foundation For: DP on DAG

Next Steps

Understand the degree decay process (Kahn) then animate queue evolution.

Theory Simulation All Graph Algorithms

Back: Prim's Next: SCC