Why This Matters
Build systems, package managers, course planners, workflow engines, spreadsheets, and compilers all need dependency order. Topological sort is the algorithmic form of "do prerequisites first."
Core Idea
A topological order exists only for a directed acyclic graph.
Kahn's algorithm:
compute indegree for every vertex
queue all vertices with indegree 0
while queue is not empty:
remove a vertex v
append v to order
for each edge v -> u:
decrement indegree[u]
if indegree[u] == 0: enqueue u
If not all vertices are output, the graph has a cycle.
Non-Example or Failure Mode
A cyclic dependency graph cannot be topologically sorted. If task A needs B and B needs A, there is no valid first task.
Worked Example
Edges: parse -> typecheck, typecheck -> compile, compile -> package.
The only valid order is parse, typecheck, compile, package, although larger graphs can have many valid topological orders.
Common Mistakes
| Mistake | Correction |
|---|---|
| Running it on undirected graphs. | Topological order is for directed dependency graphs. |
| Forgetting cycle detection. | Output length less than vertex count means cycle. |
| Assuming the order is unique. | Many DAGs have multiple valid orders. |
| Reversing edge meaning. | Decide whether edge points from prerequisite to dependent or the reverse. |
Diagnostic Questions
| Question type | Question | Answer signal |
|---|---|---|
| Definition | What kind of graph is required? | Directed acyclic graph. |
| Example / non-example | Can a graph with cycle have a topo order? | No. |
| Computation | What does indegree zero mean? | No remaining prerequisites under the chosen edge convention. |
| Transfer | Why do workflow engines need it? | Jobs must run after their dependencies. |
Exercises
Beginner:
- Topologically sort a small prerequisite graph.
- Identify whether a directed graph has a cycle.
- List two valid orders for a DAG with independent tasks.
Intermediate:
- Implement Kahn's algorithm.
- Implement DFS-based topological sort and compare output.
Challenge:
- Return all tasks involved in a dependency cycle instead of just failing.
Diagram Recommendation
Type: dependency DAG with queue trace.
Caption: "Indegree-zero nodes become available as prerequisites finish."
Purpose: Connect graph structure to build and workflow scheduling.
Next Topics
References
- Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). DFS and DAG shortest paths.
- MIT OpenCourseWare. 6.006 Introduction to Algorithms, graph algorithms.