Topological Sort

Topological sort figures out what order to do tasks in, when some tasks need others done first — you cannot take Physics before Math. It lines up every task so each requirement comes before whatever depends on it. This only works when tasks do not depend on each other in a circle, like A needing B while B also needs A. That circular case is called a cycle, and it has no valid order.

1. 1Pick a task you have not fully explored yet, and dive into everything it depends on first. This step is a depth-first search — explore as deep as you can before backing up.
2. 2Once you have explored all of a task's dependents, mark it 'finished' and push it onto a stack. It is now safe to schedule.
3. 3After you explore every task, read the stack back to front. That gives you a valid order, where every requirement comes before what needs it.

Use it to schedule tasks with dependencies — a build system figuring out compile order, course prerequisites, or installing packages so each one goes in before the packages that need it.

• ⚠Running it on a graph with a cycle, where A needs B and B needs A. There is no valid order, and simple code can loop forever.
• ⚠Pushing a task onto the stack too early, before you fully explore all of its dependents. That breaks the ordering guarantee.