Le tri topologique ordonne linéairement les sommets d'un DAG (graphe orienté acyclique) de sorte que chaque arête u->v ait u avant v. Il répond à la question « dans quel ordre puis-je accomplir ces tâches compte tenu de leurs dépendances ? »
Deux approches courantes : (supprimer répétitivement les nœuds avec in-degree 0) ou (post-ordre inversé). Un ordre valide existe .
from collections import deque
def topo_sort(graph):
indeg = {u: 0 for u in graph}
for u in graph:
for v in graph[u]:
indeg[v] += 1 # count incoming edges
queue = deque([u for u in indeg if indeg[u] == 0])
order = []
while queue:
u = queue.popleft()
order.append(u)
for v in graph[u]:
indeg[v] -= 1 # "remove" the edge
if indeg[v] == 0:
queue.append(v)
return order if len(order) == len(graph) else None # None -> cycle
topo_sort({'shirt': ['tie'], 'tie': ['jacket'], 'jacket': []})
# -> ['shirt', 'tie', 'jacket']
Utilisez pour les systèmes de compilation, l'ordonnancement de tâches, les prérequis de cours et la résolution de dépendances. Si le résultat est plus court que V, le graphe a un cycle (pas d'ordre valide). L'ordonnancement n'est généralement pas unique.
L'ordonnancement des dépendances est omniprésent — compilateurs, gestionnaires de paquets, recalcul de feuilles de calcul, pipelines CI.
Le tri topologique sert également à la détection de cycles pour les graphes orientés.
Reconnaître un problème comme « un ordre sous contraintes » et utiliser le tri topologique est un signal fort de séniorité.