topological ordering of a DAG
Some things must happen before others: you put on socks before shoes, compile a library before the program that uses it, take the prerequisite course before the advanced one. Draw an arrow from each task to the tasks that depend on it and you get a directed graph. A topological ordering is a way to line all the tasks up in a single row so that every arrow points forward — no task ever appears before something it depends on. It is the answer to 'in what order can I do all of these without violating any dependency?'.
Such an ordering exists exactly when the directed graph has no cycle — a DAG, a directed acyclic graph. (A cycle would mean a task that must come before itself, which is impossible to lay out in a line.) There are two standard ways to produce one. Kahn's method: repeatedly find a vertex with no incoming edges (nothing it must wait for), output it, and delete it along with its outgoing edges; the count of incoming edges per vertex is maintained as you go. The DFS method is even slicker: run DFS, and when a vertex finishes (all its descendants are done), push it onto the front of a list; the finished list, read front to back, is a valid topological order. Why does DFS-finish-order work? Because in a DAG there are no back edges, so for every edge u->v, v finishes before u — meaning u is pushed onto the front after v, so u lands before v in the final order, exactly as the arrow demands. Both methods run in O(n + m).
Topological sort is the backbone of build systems, task schedulers, spreadsheet recalculation, and dynamic programming on a DAG (it gives the order to fill in states so dependencies are ready). Two honest points. First, the ordering is usually not unique — when several tasks are mutually independent, any order among them is fine, so a DAG can have many valid topological orders. Second, if you run a topological-sort algorithm on a graph that has a cycle, it cannot finish: Kahn's method will run out of zero-incoming vertices with some left over, and that leftover set is precisely a witness that a cycle exists. So topological sort doubles as a cycle test on directed graphs.
Course prerequisites: calc1 -> calc2, calc1 -> linalg, calc2 -> diffeq, linalg -> diffeq. One valid order: calc1, linalg, calc2, diffeq. Another: calc1, calc2, linalg, diffeq. Both keep every arrow pointing forward. There is no order if you add diffeq -> calc1, because that creates a cycle.
Independent tasks (calc2 and linalg) can swap freely, so a DAG typically has many valid topological orders.
Topological order requires a DAG: a directed cycle makes it impossible, and the algorithm's failure to finish (leftover vertices in Kahn's method) is itself the proof a cycle exists.