Interactive Lab · DSA & Algorithms

In what order can you finish tasks that depend on each other? Topological sort

Course prerequisites, a build system, a spreadsheet's formulas, "npm install"all the same problem: some tasks can't start until others finish. A topological sort lays them in a legal order. Kahn's algorithm is beautifully simple: find any task with nothing left blocking it (in-degree zero), do it, and cross it off, which unblocks whatever depended on it. Repeat until everything's scheduled. And if you ever get stuck with tasks remaining but none free? Those tasks form a cyclean impossible schedule. Scrub the algorithm and flip in a cycle to watch it fail.

🎬 Watch the 90-second explainer, then schedule the tasks yourself below ↓

▶ The playground, peel off one unblocked course at a time

Arrows point from a prerequisite to the course that needs it. The number on each box is its in-degreehow many prerequisites are still unmet. Green = ready now (in-degree 0); a peeled course is greyed with its position in the order. Flip to Add a cycle and watch the algorithm stall.

graph

step scheduled 0 / 8

🧭 Where this fits

Topological sort schedules everything with dependencies: make/Bazel build graphs, Airflow DAG runs, database-migration ordering, package installs, and course prerequisites (this site's Journey uses one). The stall-means-cycle detection you just watched is precisely how circular imports and impossible build orders get caught.

The code that's actually running, Kahn's algorithm

🔮 Predict, then test

In the valid graph, scrub to the end: all 8 courses land in a legal order, every arrow points left-to-right, so no course starts before its prerequisites. Now flip to Add a cycle (it adds an edge making Data Struct → Algorithms → ML → Data Struct). Predict: the algorithm peels off the two free courses, then jamsevery remaining course is waiting on another that's also waiting, so no in-degree ever hits zero. That stall is the cycle detector: if scheduled < total, a cycle exists. Why is "nothing has in-degree 0, but tasks remain" exactly the signature of a dependency loop?

The takeaway

Your new mental model of topological sort

Only works on a DAG. A topological order exists iff the graph is a directed acyclic graphno cycles. Cycles mean mutually-blocking tasks, so no legal order can exist.
Kahn's = peel the free ones. Track each node's in-degree. Repeatedly remove a node with in-degree 0, append it to the order, and decrement its neighbours, which may free them next. A queue makes each node and edge get touched once: O(V + E).
Free cycle detection. If the loop ends with fewer than V nodes scheduled, the leftovers are trapped in a cycle. Same algorithm answers "is this schedulable at all?"
Orderings aren't unique. Whenever several nodes are free at once, any of them can go next, so a DAG usually has many valid topological orders (this lab breaks ties by name to stay deterministic).
You didn't memorize "topo sort = DFS/Kahn"you watched unblocked tasks peel off one by one, and a cycle jam the whole schedule.

← Graph Search Placement prep →Try: Union-Find