Topological Sort: The Order Behind Build Systems, Course Prerequisites, and Spreadsheets
Some tasks have to happen before others, and topological sort is the algorithm that turns a tangle of "this before that" rules into one valid, executable order.
A college course catalog full of prerequisites -- Calculus I before Calculus II, both before a physics course that requires them -- doesn't dictate one single correct schedule; it just rules out the schedules that break a "this before that" rule. Plenty of different valid orderings can satisfy every prerequisite simultaneously. Topological sort is the algorithm that takes exactly that kind of tangle of ordering rules and produces one of those valid full orderings.
Formally, topological sort operates on a directed acyclic graph -- a graph of nodes and one-way, "must come before" edges between them, with no cycles, meaning there's no way to follow the edges in a loop back to where you started. The algorithm's output is a single linear ordering of every node such that, for every edge in the graph, the node it points from appears before the node it points to -- every dependency rule satisfied at once, in one flat list.
The "acyclic" requirement isn't a minor technical footnote -- it's the difference between the problem being solvable at all and not. A graph with a genuine cycle (task A requires task B, which in turn requires task A) has no valid linear ordering whatsoever, since satisfying one dependency necessarily breaks the other. This is exactly what a build tool or package manager means by a "circular dependency" error: it attempted a topological sort, found a cycle, and correctly reported that no valid build order exists until the cycle itself is broken.
This shows up constantly in real software, often without being named: a build system uses it to decide what order to compile files in when some depend on others already being built; a spreadsheet uses it to decide what order to recalculate cells in when one cell's formula references another's value; and a task scheduler uses it to sequence jobs that depend on earlier jobs' output being ready first. In every case, the underlying problem is identical -- a set of "this before that" rules, and a need for one order that honors every one of them.
The practical value of recognizing a topological-sort problem when it shows up is knowing it has a well-understood, efficient solution already: rather than hand-rolling ordering logic and hoping it holds up as dependencies grow more tangled, the same graph-based algorithm that schedules a course catalog scales cleanly to a build system with thousands of interdependent files.