Topological sort

Order a DAG so every arrow points forward: prerequisites first. Exists iff there's no cycle.

Two algorithms, both familiar

• Kahn's (BFS-flavored): repeatedly remove a node with in-degree 0, freeing its dependents
• DFS (depth-flavored): reverse of finish-order
• Both O(V+E); both detect cycles (no order exists)
• "Which traversal, plus what?" again

Watch Kahn peel the graph

Green = ready (in-degree 0) · orange = placing · dark = blocked (shows remaining in-degree). The ready frontier sweeps left to right.

Guessing almost never works

12 edges → 1 in ~741 random orders is valid. Topo sort: valid every time, O(V+E).

The order isn't unique

• A DAG is a partial order; a topo sort is a linear extension
• Incomparable tasks (no path between them) can go either way
• Kahn's and DFS return different valid orders — both correct
• Test the property (every edge forward), not one exact sequence

Takeaway

graphlib.TopologicalSorter ships with Python 3.9+ — batteries included. No valid order ⇒ your dependencies have a cycle (often the real finding). Next: weights break the "every edge = one step" assumption → Dijkstra.