Le Tri Topologique expliqué, avec du Code

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

Qu'est-ce qu'un Tri Topologique ?

Un tri topologique est un ordre linéaire des nœuds d'un graphe orienté acyclique (DAG) tel que, pour chaque arête orientée de u vers v, le nœud u apparaît avant le nœud v. En clair : alignez tout pour que chaque flèche pointe vers l'avant.

Deux conditions sont inscrites dans cette définition. Le graphe doit être orienté (les dépendances ont un sens : A avant B n'est pas la même chose que B avant A) et acyclique (sans cycle). Si A doit venir avant B et B avant A, aucun ordre valide ne peut exister. Les arbres et les DAG sont ici de proches cousins ; pour le côté arbres, voir les arbres enracinés.

Quand en Avez-vous Besoin

Le tri topologique est la réponse dès qu'un problème ressemble à "faites ces choses dans un ordre qui respecte leurs prérequis". Vous le reconnaîtrez à ces signaux :

• Dépendances : "La tâche X exige que la tâche Y soit terminée d'abord."
• Ordonner ou planifier : "Dans quel ordre puis-je suivre ces cours ?"
• Construire et compiler : "Compiler les modules pour que chaque import existe déjà."
• Résolution : "Installer les paquets pour que chaque dépendance soit installée avant ce qui en a besoin."

C'est l'un des schémas les plus courants en entretien technique, d'où sa présence dans le guide des algorithmes de graphes pour les entretiens de code et il constitue une étape de la feuille de route de la théorie des graphes.

L'Algorithme de Kahn, Pas à Pas

La méthode la plus intuitive est l'algorithme de Kahn. Il s'appuie sur un nombre par nœud : le degré entrant, le nombre d'arêtes entrantes. Un nœud de degré entrant 0 n'a aucun prérequis en attente, on peut donc le placer ensuite sans risque.

La boucle est simple : prenez n'importe quel nœud de degré entrant 0, produisez-le et retirez ses arêtes sortantes, ce qui abaisse le degré entrant de ses voisins. Répétez jusqu'à ce qu'il ne reste rien. Exécutons-le sur ce DAG. Chaque nœud porte sa position dans un ordre valide.

Voici le déroulé. La file contient les nœuds dont le degré entrant a atteint 0. Nous commençons par A, le seul nœud qui ne dépend de rien.

Remarquez qu'après avoir pris A, le degré entrant de B et de C est tombé à 0 en même temps. L'un ou l'autre pouvait suivre, et c'est précisément pourquoi un DAG a en général de nombreux ordres valides. Voir les degrés entrants chuter sur un graphe en direct rend la chose évidente, ce que vous pouvez essayer dans le visualiseur d'algorithmes.

Implémentation en Python

L'algorithme de Kahn se traduit presque directement en code. Nous calculons chaque degré entrant, amorçons une file avec les nœuds de degré entrant nul, puis la vidons.

from collections import deque, defaultdict

def topological_sort(num_nodes, edges):
    graph = defaultdict(list)
    in_degree = [0] * num_nodes

    for u, v in edges:          # l'arête u -> v signifie u avant v
        graph[u].append(v)
        in_degree[v] += 1

    # Amorcer avec chaque nœud sans prérequis.
    queue = deque(n for n in range(num_nodes) if in_degree[n] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbour in graph[node]:
            in_degree[neighbour] -= 1        # retirer l'arête
            if in_degree[neighbour] == 0:    # plus aucun prérequis
                queue.append(neighbour)

    # Si un nœud n'a jamais atteint le degré entrant 0, un cycle l'a bloqué.
    if len(order) == num_nodes:
        return order
    return []   # cycle détecté, aucun ordre valide

La vérification finale est la partie élégante : s'il manque un nœud dans la sortie, ces nœuds sont piégés dans un cycle. Ainsi, le même code qui ordonne un DAG détecte aussi si le graphe était bel et bien un DAG.

L'Approche DFS

Il existe une seconde méthode classique fondée sur le parcours en profondeur. Lancez le DFS et, lorsqu'un nœud termine (tous ses descendants sont explorés), empilez-le. L'ordre topologique est la pile lue à l'envers.

L'intuition : un nœud ne termine qu'après que tout ce vers quoi il pointe a terminé, donc dans l'ordre inverse de fin, il se place avant tous ses descendants. La version DFS n'a pas besoin de tenir les degrés entrants, mais vous devez tout de même vous prémunir contre les cycles en suivant les nœuds du chemin de récursion courant. Les deux approches sont également valides ; celle de Kahn est souvent plus facile à raisonner, tandis que le DFS est plus compact.

Les Cycles et Pourquoi ils le Cassent

Un ordre topologique existe si et seulement si le graphe est acyclique. La raison est immédiate : un cycle A → B → A exige que A vienne avant B et B avant A en même temps, ce qui est impossible sur une ligne.

La conséquence utile : le tri topologique est aussi un détecteur de cycles. Dans l'algorithme de Kahn, si vous ne parvenez pas à produire les V nœuds, les nœuds restants forment au moins un cycle. Dans la version DFS, rencontrer un nœud déjà présent sur votre chemin courant signale un cycle.

C'est pourquoi les questions d'entretien de type "Course Schedule", qui demandent en réalité "est-ce seulement possible ?", se résolvent par un tri topologique.

Complexité

Les deux algorithmes sont optimaux : ils touchent chaque nœud et chaque arête exactement une fois.

Ce coût linéaire est la raison pour laquelle le tri topologique passe à l'échelle sur d'immenses graphes de dépendances. Pour voir comment il se compare à tous les autres algorithmes de graphes, voir le guide de complexité et l'aide-mémoire d'une page.

Applications Concrètes

• Systèmes de compilation : Make, Bazel et consorts trient topologiquement les cibles pour que les dépendances soient construites d'abord.
• Gestionnaires de paquets : npm, pip et apt déterminent l'ordre d'installation à partir d'un DAG de dépendances.
• Planification de tâches et de jobs : tableurs recalculant des cellules, pipelines CI ordonnant les étapes, planificateurs de cours.
• Compilateurs : ordonner les déclarations et évaluer les expressions pour que chaque symbole soit défini avant son usage.