You have tasks with dependencies — you can’t pour the foundation after the walls. A topological sort lines up the tasks so every dependency comes before the thing that needs it. Repeatedly take any task with nothing left blocking it, remove it, and repeat. It only works if there are no cycles — a circular dependency is unschedulable. It’s how build systems and spreadsheets order their work. Slide to lay out the order.
A topological sort of a DIRECTED ACYCLIC GRAPH (DAG) is a linear ordering of nodes such that every edge u→v places u before v. Kahn’s algorithm repeatedly removes a node with IN-DEGREE ZERO (nothing depends-on-it remaining) and decrements its successors, in O(V+E). An ordering exists IF AND ONLY IF the graph is acyclic — a cycle is an unsatisfiable circular dependency. It schedules builds (make), resolves package installs, evaluates spreadsheet cells, and orders course prerequisites. A fail-loud self-check throws unless the produced order respects every edge. ◆ real graph algorithm, node-verified.
A DAG is shown; if a cycle existed, no valid order could exist (the algorithm would report it). The ordering-respects-all-edges property is exact; multiple valid orders can exist when nodes are independent.