Motivation
Lesson 2 of 9 in Coddy's Topological Sort - Graph Algorithms course.
A topological order only exists when the graph has no cycles. We build one with Kahn's algorithm, which repeatedly removes a vertex that has no remaining incoming edges.
Why learn Topological Sort?
- Ordering with constraints: build systems, task scheduling, course prerequisites, and spreadsheet recalculation all rely on it.
- Cycle detection: if you cannot order every vertex, the graph must contain a cycle.
- Foundation for DAG algorithms: shortest and longest paths in a DAG are computed in topological order.
Many valid orders can exist. To get one predictable answer, we always remove the smallest-numbered vertex whose in-degree is 0.
Try it yourself
This lesson doesn't include a code challenge.
Test yourselfThis lesson includes a short quiz. Start the lesson to answer it and track your progress.
