Topological Sort

Topological Ordering

A topological ordering of a directed acyclic graph (DAG) is a linear ordering of vertices such that for every directed edge u → v, u comes before v in the ordering. In other words, every dependency is resolved before the node that depends on it.

Topological ordering exists if and only if the graph has no directed cycles. This makes it perfect for problems involving prerequisites, dependencies, build systems, and task scheduling.

One valid topological order: CS101 → MATH101 → STATS101 → CS201 → CS301 (or MATH101 → CS101 → STATS101 → CS201 → CS301). Multiple valid orderings exist for most DAGs.

Kahn's Algorithm (BFS Approach)

Kahn's algorithm uses in-degree counting. Nodes with in-degree 0 have no prerequisites and can be taken immediately. We repeatedly remove a node with in-degree 0, add it to the result, and decrement the in-degree of its neighbors.

DFS-Based Topological Sort

The DFS approach uses post-order traversal. Perform DFS on each unvisited node. When a node's recursion finishes (all descendants processed), prepend it to the result. The intuition: a node appears after all nodes reachable from it.

Cycle Detection

Both Kahn's and DFS-based topological sort naturally detect cycles:

For pure cycle detection (no ordering needed), you can also run DFS with a visited map — if you ever encounter a node on the current recursion path, there is a cycle.

When to Use

• Prerequisite / dependency resolution: Course Schedule problems.
• Build systems: determining compilation order from a dependency graph.
• Deadlock detection: finding cycles in resource allocation graphs.
• Alien Dictionary: deriving character order from a sorted word list.
• Kahn's when BFS-style processing is more natural (in-degree tracking).
• DFS when you are already using DFS for other graph processing and want ordering as a byproduct.
• Must have a DAG: if the graph has cycles, topological sort is impossible.

Problems