Tri topologique
Ordre linéaire des nœuds d'un DAG tel que pour chaque arête u→v, u précède v. « Les dépendances d'abord ».
Deux algorithmes classiques : l'algorithme de Kahn (retirer un à un les nœuds sans arête entrante) et l'approche basée sur le DFS (parcours postfixe, inversé). Les deux sont en O(V+E). Impossible si le graphe contient un cycle — le tri topologique n'existe alors pas.
Utilisé par les systèmes de build (Make, Bazel — quels fichiers construire et dans quel ordre), les gestionnaires de paquets (npm, apt — ordre d'installation), les ordonnanceurs de tâches (Airflow, Dagster), la vérification des prérequis de cours, et l'ordonnancement d'instructions dans les compilateurs.