Topological Sort
Scenario
You are building a university course registration system. Students must take prerequisites before advanced classes.
How do you automatically generate a valid semester-by-semester sequence for a student to take their courses?
Why it exists
Problem: When tasks have dependencies (A must happen before B), we need a way to schedule them so no task is executed before its prerequisites are met.
Naive approach: Guessing an order and checking if it violates dependencies is extremely slow (factorial time).
Better idea: Use Kahn's algorithm (or DFS). Count how many prerequisites each task has. Do the tasks with zero prerequisites first. Once a task is done, its dependents have one less prerequisite. Repeat until all tasks are done.
Mental model
Find jobs that have no blockers. Do them. Doing them removes blockers for other jobs. Now see if any new jobs have no blockers. Repeat.
Topological sort orders a DAG linearly. A cycle means each node in the cycle depends on the other, so no linear order can exist. A topological sort fails if and only if the graph has a cycle. We teach Kahn's algorithm (BFS-based): compute in-degrees, enqueue all zero in-degree nodes, pop them, append to the output, and decrement their neighbors' in-degrees. If a neighbor hits zero, enqueue it. If the final output length is less than the number of vertices, a cycle exists.
Repeated decision: Which node currently has in-degree zero?
Explanation
A topological sort provides a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every edge `u → v`, `u` comes before `v`.
**DAG Only:** Topological sort is only possible if there are no cycles. If A depends on B, and B depends on A, who goes first? Nobody can. Therefore, if a topological sort fails to process every node, it is proof that a cycle exists.
### Kahn's Algorithm (BFS-based)
Kahn's algorithm is the most intuitive way to perform a topological sort:
1. Compute the **in-degree** (number of incoming edges) for every node.
2. Put all nodes with an in-degree of `0` into a Queue. (These have no prerequisites).
3. While the queue is not empty:
- Pop a node, add it to your output list.
- For each of its neighbors, decrement their in-degree by 1. (You've satisfied one of their prerequisites).
- If a neighbor's in-degree drops to `0`, enqueue it.
4. If the output list has fewer than `V` nodes at the end, the graph has a cycle.
Hand-trace (Graph: 0→2, 1→2, 2→3):
- In-degrees: 0: 0, 1: 0, 2: 2, 3: 1.
- Queue: [0, 1]. Output: [].
- Pop 0. Append to Output: [0]. Decrement 2's in-degree to 1.
- Pop 1. Append to Output: [0, 1]. Decrement 2's in-degree to 0. Enqueue 2.
- Pop 2. Append to Output: [0, 1, 2]. Decrement 3's in-degree to 0. Enqueue 3.
- Pop 3. Append to Output: [0, 1, 2, 3]. Queue empty.
- Output length is 4 (all nodes). Success!
*(Note: A DFS-based variant also exists, where you push nodes to a stack after all their neighbors are visited, then reverse the stack. Kahn's is generally preferred for its straightforward cycle detection).*
Key points
- DAG Requirement: Topological sort ONLY works on Directed Acyclic Graphs. Cycles make linear ordering impossible.
- In-Degree Tracking: Kahn's algorithm hinges on accurately maintaining the count of unsatisfied dependencies (in-degrees).
- Cycle Detection Bonus: Kahn's algorithm natively detects cycles. If the output array length is less than V, the unprocessed nodes form a cycle.
Pattern: Kahn's Algorithm (In-Degree BFS)
Recognition cues:
- Scheduling tasks with prerequisites.
- Finding a valid build order for dependencies.
Failure signals
- Trying to topological sort an undirected graph (meaningless).
- Failing to account for disconnected components (Kahn's handles this automatically if you enqueue all 0-degree nodes initially).
Engineering examples
Build Systems and Package Managers
Compiling source files or installing packages in the correct order.
Make, npm, Docker, and React's effect hooks all use topological sorting to guarantee dependencies are resolved before execution.
When not to use
- Graphs with cycles: Topological sort is mathematically impossible if a cycle exists.
Common mistakes
- Forgetting that multiple valid sorts can exist: If multiple nodes have an in-degree of 0 at the same time, any of them can be processed next. There is rarely just one unique topological sort.
- Not checking for cycles at the end: If you don't verify that the final output list contains all V nodes, your algorithm will silently return a partial/incorrect order when given a cyclic graph.
Glossary
- DAG
- Directed Acyclic Graph. A directed graph with no cycles. Topological sort is only possible on a DAG.
- in-degree
- The number of incoming edges pointing to a specific node.
- linear ordering
- An ordering of vertices where for every directed edge u -> v, vertex u comes before v.
Recall questions
- What happens if you try to perform a topological sort on a graph with a cycle?
- What is the repeated decision made at each step of Kahn's algorithm?
- What data structure is typically used to hold the nodes with in-degree zero in Kahn's algorithm?
Questions & answers
Find the correct compilation order for a set of modules with dependencies.
Use Kahn's algorithm to compute in-degrees and extract a valid topological order.
Approach: Classic topological sort.
Course Schedule II: Return the ordering of courses you should take to finish all courses.
Run Kahn's algorithm. If output length equals numCourses, return the output. Otherwise, return an empty array (cycle exists).
Approach: Topological sort with cycle detection.
Interesting facts
- Spreadsheet software like Excel uses topological sorting to determine the order in which cells should be recalculated when you change a value.
Continue learning
Previous: Cycle Detection
Previous: BFS on graphs
Related: Cycle Detection
Related: BFS on graphs