Topological Sort

Module 4.11 — Kahn's algorithm (BFS-based) on DAGs

Graph:
Speed:
Step 0 / 0
MathCS101StatsCS201MLDB
Unprocessed
In Queue
Processing
Done
Number = in-degree

Topological Order

Press Play to start

Queue (in-degree = 0)

(empty)

In-Degree Table

Math—
CS101—
Stats—
CS201—
ML—
DB—

Kahn's Algorithm

1. Calculate in-degree of all vertices
2. Enqueue all vertices with in-degree 0
3. While queue not empty:
a. Dequeue vertex u → output
b. For each neighbor v: in-degree[v]--
c. If in-degree[v] == 0: enqueue v
4. If output.length < V → cycle exists!

Use Cases

• Course prerequisite ordering
• Build dependency resolution
• Task scheduling
• Package manager installs