Tri topologique par DFS en post-ordre

Le deuxième algorithme classique de tri topologique utilise DFS avec un traitement en postordre. Après avoir exploré complètement tous les voisins d’un sommet, ainsi que leurs descendants, empilez le sommet. Une fois tous les sommets traités, utilisez pop sur la pile pour lire l’ordre topologique. Un sommet empilé après toutes ses dépendances signifie qu’il vient en premier dans l’ordre — le postordre inversé constitue donc le tri topologique.

Considérez un graphe de dépendances où le cours A nécessite le cours B. Lorsque DFS visite A, il commence par appeler récursivement B. B n’a aucun prérequis, il est donc terminé en premier et empilé en premier. A est ensuite terminé et empilé. Dépiler la pile donne A avant B dans la sortie — mais on inverse le résultat à la fin, ce qui donne B avant A : prendre B d’abord, puis A. Le postordre empile les dépendances avant les éléments qui en dépendent ; la pile inversée est donc un ordre topologique valide.

Utilisez trois états pour les sommets visités : WHITE (0) = non visité, GREY (1) = en cours de traitement, dans la pile d’appels de DFS, BLACK (2) = entièrement traité. Une arête arrière — une arête vers un sommet GREY — indique un cycle. Les arêtes vers des sommets BLACK sont sûres, car ceux-ci ont déjà été entièrement explorés. Ce schéma à trois couleurs détecte correctement tous les cycles dans les graphes orientés.

Utilisez un DFS récursif qui colore les sommets, les empile en postordre et renvoie Faux en cas de détection d’un cycle. Après avoir visité tous les sommets, la pile inversée donne l’ordre topologique.

La limite de récursivité de Python, fixée par défaut à 1000, pose problème pour les grands graphes. Un DFS itératif utilisant une pile explicite permet de l’éviter. L’astuce consiste à empiler d’abord (node, False) ; lorsqu’il est dépilé avec False, empilez (node, True), ce qui signifie « je reviendrai ici après l’exploration », puis empilez tous les voisins non visités avec Faux. Lorsqu’il est dépilé avec True, colorez-le en BLACK et empilez-le dans la pile de résultats.

Les deux s’exécutent en O(V + E). Principales différences : l’algorithme de Kahn (BFS) produit naturellement les sommets dans l’ordre des dépendances les plus en amont et offre une détection des cycles plus simple, fondée sur une vérification de longueur. Le postordre de DFS fonctionne de manière récursive et détecte explicitement les arêtes arrière. L’algorithme de Kahn est préférable lorsque vous voulez obtenir le résultat dans l’ordre direct, sans inversion. DFS est préférable lorsque vous avez besoin du postordre complet à d’autres fins, comme la détection des SCC. Les deux conviennent aux entretiens.

Dans un arbre, le postordre parcourt le sous-arbre gauche → le sous-arbre droit → la racine. Dans un DAG, le DFS en postordre visite toutes les dépendances d’un sommet avant de traiter le sommet lui-même — c’est la même idée généralisée à plusieurs prédécesseurs et à une structure de graphe arbitraire. La racine d’un arbre DFS, c’est-à-dire le sommet de départ, est empilée après tous ses descendants, ce qui la fait apparaître en premier dans la pile inversée — la position topologique correcte pour un sommet sans prédécesseurs.

Dictionnaire extraterrestre : étant donné une liste triée de mots dans une langue extraterrestre, déduisez l’ordre des caractères. Comparez les mots adjacents caractère par caractère pour trouver la première différence — cela donne une arête c1 → c2, ce qui signifie que le premier caractère précède le second. Recueillez toutes ces arêtes et exécutez un tri topologique pour produire l’ordre des caractères extraterrestres. Si un cycle existe, l’ordre est invalide.

Certains problèmes demandent un tri topologique respectant des contraintes supplémentaires, comme le maintien de l’ordre relatif des éléments de la liste d’origine. Combinez l’algorithme de Kahn avec une file de priorité personnalisée ou un pré-tri : conservez l’ordre relatif d’origine des éléments en effectuant un tri stable du contenu de la file d’attente à chaque étape. Ces variantes sous contrainte évaluent une compréhension plus approfondie de la souplesse de l’algorithme.

Voici des expressions indicatrices dans les problèmes d’entretien qui signalent un tri topologique : « dépendances fournies », « prérequis », « ordre des tâches », « ordre de construction », « toutes les tâches peuvent-elles être terminées ? », « trouver une séquence valide ». Si le problème implique un ordre entre des éléments dont certains doivent précéder les autres, construisez un graphe orienté et appliquez le tri topologique de Kahn ou de DFS. La détection des cycles constitue souvent une exigence secondaire du même problème.

DFS et l’algorithme de Kahn peuvent produire des ordres topologiques valides différents pour un même graphe. Les deux sont corrects : un DAG peut posséder plusieurs ordres topologiques valides. Pour vérifier la validité, assurez-vous que, pour chaque arc u → v du graphe, le sommet de départ apparaît avant le sommet d’arrivée dans l’ordre de sortie. Pour les problèmes d’entretien qui exigent un ordre précis, par exemple l’ordre lexicographiquement le plus petit, utilisez Kahn avec un tas min : le postordre de DFS ne produit pas naturellement l’ordre lexicographiquement minimal.

Testez votre compréhension des concepts de Structures de données et algorithmes & Préparation aux entretiens de programmation présentés dans cette leçon.

Dans cette leçon, vous avez appris que le tri topologique en postordre de DFS empile les sommets après l’exploration de toutes leurs dépendances, que le marquage à trois couleurs (WHITE/GREY/BLACK) détecte les cycles via les arêtes arrière vers les sommets GREY et que l’inversion de la pile de postordre produit un ordre topologique valide. Nous allons ensuite appliquer directement le tri topologique aux problèmes Planification des cours I et II.