Sortowanie topologiczne
Liniowe uporządkowanie wierzchołków grafu DAG tak, że dla każdej krawędzi u→v wierzchołek u występuje przed v. „Zależności najpierw”.
Dwa klasyczne algorytmy: algorytm Kahna (zdejmowanie po kolei wierzchołków bez krawędzi wchodzących) oraz oparty na DFS (kolejność postorder, odwrócona). Oba działają w czasie O(V+E). Jeśli graf ma cykl, sortowanie topologiczne nie istnieje.
Napędza systemy budowania (Make, Bazel — które pliki w jakiej kolejności), menedżery pakietów (npm, apt — kolejność instalacji), harmonogramy zadań (Airflow, Dagster), sprawdzanie wymagań wstępnych kursów oraz szeregowanie instrukcji w kompilatorach.