Calculateur de Tri Topologique

Pseudocode

Deux formulations standard, toutes deux linéaires. Kahn progresse depuis les sommets sans prérequis; la variante DFS travaille à rebours depuis les dates de fin.

// Kahn: retirer a repetition un sommet sans arete entrante
calculer degreEntrant[v] pour chaque sommet
file = tous les sommets de degreEntrant 0
ordre = []

tant que la file est non vide:
    u = file.retirer()
    ordre.ajouter(u)
    pour chaque arete (u, v):
        degreEntrant[v] -= 1
        si degreEntrant[v] == 0: file.ajouter(v)

si ordre.longueur < V: le graphe contient un cycle

// Variante DFS: inverse de l ordre de fin
lancer un DFS; empiler chaque sommet a sa fin
la pile depilee donne un ordre topologique valide

Kahn possède un avantage pratique qu'il vaut la peine de connaître: comme il détecte un cycle en comptant combien de sommets il a réussi à émettre, les sommets restants sont exactement ceux impliqués dans un cycle ou situés en aval. Cela le rend bien plus utile qu'un simple booléen lorsqu'il faut signaler quelles dépendances sont circulaires.

Exemple détaillé, étape par étape

Exécute Kahn sur un petit graphe de dépendances de compilation, où une arête X vers Y signifie que X doit être construit avant Y.

Graphe d'exemple: Arêtes orientées A vers C, B vers C, C vers D et B vers D.

1. Calculer les degrés entrants. A vaut 0, B vaut 0, C vaut 2 (depuis A et B), D vaut 2 (depuis C et B). La file démarre avec A et B.
2. Émettre A. L'ordre est [A]. Décrémente C à un degré entrant de 1. Ce n'est pas encore zéro, C n'est donc pas enfilé.
3. Émettre B. L'ordre est [A, B]. Décrémente C à 0, C est donc enfilé. Décrémente D à 1.
4. Émettre C. L'ordre est [A, B, C]. Décrémente D à 0, D est donc enfilé.
5. Émettre D. L'ordre est [A, B, C, D]. La file est vide et les quatre sommets ont été émis, il n'existe donc aucun cycle.

Un ordre valide est A, B, C, D. Note que B, A, C, D l'est tout autant: A et B n'ont aucun prérequis et leur ordre relatif n'est pas contraint. L'ordre topologique n'est unique que si le graphe forme une seule chaîne, raison pour laquelle les tests devraient vérifier que chaque arête pointe vers l'avant plutôt que de comparer à une séquence attendue.

Complexité et son origine

Temps: O(V + E) · Espace: O(V)

Calculer tous les degrés entrants exige un parcours de toutes les arêtes, O(E). Chaque sommet est enfilé et défilé exactement une fois, O(V). Chaque arête est examinée exactement une fois, lorsque sa source est émise et que le degré entrant de la cible est décrémenté, encore O(E). L'espace contient le tableau des degrés entrants, la file et la liste de sortie, tous en O(V). La variante DFS a les mêmes bornes, la pile de récursion remplaçant la file. Aucune ne peut être améliorée, puisque tout algorithme correct doit lire chaque arête pour connaître les contraintes.

Quand utiliser Tri Topologique, et quand l'éviter

Kahn et DFS produisent des ordres également valides. Choisis selon ce dont tu as besoin en plus de l'ordonnancement.

Pièges fréquents

• L exécuter sur un graphe cyclique sans s en apercevoir. Un graphe cyclique n'admet aucun ordre topologique. Kahn émettra silencieusement un ordre partiel à moins que tu ne compares la longueur de la sortie à V. Cette vérification est le test de cycle, et l'omettre produit un ordre de compilation plausible mais incomplet.
• Attendre une réponse unique. Deux sommets quelconques sans chemin entre eux peuvent apparaître dans n'importe quel ordre. Comparer à une séquence codée en dur fait échouer les tests sur des implémentations correctes; vérifie plutôt que chaque arête pointe vers l'avant dans la sortie.
• Confondre le sens des arêtes. Si une arête X vers Y signifie « X dépend de Y », l'ordre topologique est l'inverse de celui que tu veux. Corrige la convention une seule fois, à l'endroit où le graphe est construit, plutôt que d'inverser la sortie en espérant que ça tombe juste.
• L appliquer à des graphes non orientés. L'ordre topologique n'est défini que pour les graphes orientés acycliques. Une arête non orientée est un cycle de longueur deux, donc aucun graphe non orienté possédant une arête n'admet d'ordre topologique.
• Récursion trop profonde dans la variante DFS. Une chaîne de dépendances de plusieurs dizaines de milliers de sommets fera déborder la pile d'appels. Kahn est itératif et n'a pas cette limite, ce qui explique en partie la préférence des outils de compilation.

Questions fréquentes

À quoi sert le tri topologique?

Il ordonne les sommets d'un graphe orienté acyclique de sorte que chaque arête pointe vers l'avant, ce qui répond à la question de savoir dans quel ordre des tâches peuvent s'exécuter compte tenu de leurs dépendances. Il planifie les systèmes de compilation comme Make et Gradle, résout l'ordre d'installation des paquets, ordonne les cours à prérequis, séquence l'évaluation des cellules de tableur et planifie l'exécution des instructions dans les compilateurs.

Quelle est la différence entre Kahn et l'approche DFS?

Kahn retire à répétition les sommets de degré entrant nul à l'aide d'une file, en progressant depuis ce qui n'a aucun prérequis. L'approche DFS lance un parcours en profondeur et émet les sommets dans l'ordre inverse de leur fin. Les deux sont en O(V + E) et donnent des ordres valides. Kahn est itératif et signale quels sommets sont dans des cycles; DFS est plus court mais récursif.

Un graphe peut-il avoir plusieurs ordres topologiques?

Presque toujours. Deux sommets quelconques sans chemin orienté entre eux peuvent apparaître dans n'importe quel ordre, si bien qu'un graphe à V sommets et peu d'arêtes peut admettre énormément d'ordres valides. L'ordre n'est unique que si le graphe contient un chemin hamiltonien, ce qui pour un DAG signifie une chaîne unique traversant tous les sommets.

Comment détecter un cycle pendant un tri topologique?

Avec Kahn, compte les sommets émis: s'il en sort moins de V, les restants sont dans un cycle ou en aval, car aucun n'a jamais atteint un degré entrant nul. Avec la variante DFS, une arête arrière vers un sommet encore présent dans la pile de récursion prouve un cycle.

Quelle est la complexité temporelle du tri topologique?

O(V + E) en temps et O(V) en espace, aussi bien pour Kahn que pour la variante DFS. Chaque sommet est traité une fois et chaque arête examinée une fois. C'est optimal, puisque tout algorithme doit au minimum lire toutes les arêtes de dépendance.