Motivation

Un ordre topologique n'existe que lorsque le graphe ne contient pas de cycles. Nous en construisons un avec l'algorithme de Kahn, qui supprime de manière répétée un sommet n'ayant plus d'arêtes entrantes.

Pourquoi apprendre le tri topologique ?

• Ordonnancement avec contraintes : les systèmes de build, la planification de tâches, les prérequis de cours et le recalcul de feuilles de calcul s'appuient tous sur celui-ci.
• Détection de cycles : si vous ne pouvez pas ordonner chaque sommet, le graphe contient forcément un cycle.
• Fondation pour les algorithmes de DAG : les chemins les plus courts et les plus longs dans un DAG sont calculés dans l'ordre topologique.

Plusieurs ordres valides peuvent exister. Pour obtenir une réponse prévisible, nous supprimons toujours le sommet avec le numéro le plus petit dont le degré entrant est 0.