Topological Sort
Topological order
A large project is often divided into smaller activities with precedence constraints: some must finish before others begin. An Activity-on-Vertex (AOV) network uses vertices for activities and directed edges for their required order.
If there is a directed path from V to W, V must appear before W. An ordering satisfying every such constraint is a topological order. An AOV network admitting one must be a directed acyclic graph (DAG).
Kahn's algorithm constructs the order. Let L store the output. Put zero-indegree vertices into L and remove them from the graph. Repeat while zero-indegree vertices remain. If L contains every vertex, sorting succeeded; if vertices remain but none has indegree 0, a cycle prevents a topological order.
For example, schedule these computer science courses:
| Course code | Course name | Prerequisites |
|---|---|---|
| C1 | Programming fundamentals | None |
| C2 | Discrete mathematics | None |
| C3 | Data structures | C1、C2 |
| C4 | Calculus I | None |
| C5 | Calculus II | C4 |
| C6 | Linear algebra | C5 |
| C7 | Algorithm analysis and design | C3 |
| C8 | Logic and computer design | None |
| C9 | Computer organization | C8 |
| C10 | Operating systems | C7、C9 |
| C11 | Compilers | C7、C9 |
| C12 | Databases | C7 |
| C13 | Theory of computation | C2 |
| C14 | Computer networks | C10 |
| C15 | Numerical analysis | C6 |
Schedule courses: remove only zero-indegree vertices
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
| Semester | Courses |
|---|---|
| Semester 1 | C1、C2、C4、C8 |
| Semester | Courses |
|---|---|
| Semester 1 | C1、C2、C4、C8 |
| Semester 2 | C3、C5、C9、C13 |
| Semester | Courses |
|---|---|
| Semester 1 | C1、C2、C4、C8 |
| Semester 2 | C3、C5、C9、C13 |
| Semester 3 | C6、C7 |
| Semester | Courses |
|---|---|
| Semester 1 | C1、C2、C4、C8 |
| Semester 2 | C3、C5、C9、C13 |
| Semester 3 | C6、C7 |
| Semester 4 | C10、C11、C12、C15 |
| Semester | Courses |
|---|---|
| Semester 1 | C1、C2、C4、C8 |
| Semester 2 | C3、C5、C9、C13 |
| Semester 3 | C6、C7 |
| Semester 4 | C10、C11、C12、C15 |
| Semester 5 | C14 |
Topological sorting: detect and repair a cycle
Unlock the complete interactive lab, deeper explanations, and curated reference answers.
KNOWLEDGE QUIZ
KNOWLEDGE QUIZ
Schedule tasks and check for cycles
Schedule tasks by completing all current zero-indegree vertices each round. Give the rounds and one valid topological order. Then add F→B, determine whether completion remains possible, and draw the blocking directed cycle.