Topological Sort

The problem

A DAG (directed acyclic graph) is a directed graph with no directed cycle. A topological order lists all nodes so that for every edge $u \to v$, $u$ comes before $v$.

Everyday meaning: tasks with prerequisites, build steps that depend on each other, courses that need other courses. The order tells you what can be done first.

Two facts:

• A topological order exists if and only if the graph has no directed cycle.
• It is usually not unique. Independent nodes can appear in any relative order.