Topologisch sorteren
Lineaire ordening van de knopen van een DAG zodat bij elke pijl u→v knoop u vóór v komt. "Afhankelijkheden eerst".
Twee klassieke algoritmen: het algoritme van Kahn (haal steeds knopen zonder inkomende pijlen weg) en de DFS-variant (post-order, omgekeerd). Beide O(V+E). Bestaat niet als de graaf een cykel bevat; dan is topologisch sorteren onmogelijk.
Drijft buildsystemen aan (Make, Bazel: welke bestanden in welke volgorde), pakketbeheerders (npm, apt: installatievolgorde), taakplanners (Airflow, Dagster), controles op vakkenvoorwaarden en instructieplanning in compilers.