Tri topologique

En théorie des graphes, et plus spécialement en algorithmique des graphes, un tri topologique d'un graphe acyclique orienté (ou dag, de l'anglais directed acyclic graph) est une extension linéaire de l'ordre partiel sur les sommets déterminé par les arêtes, c'est-à-dire un ordre total compatible avec ce dernier. En d'autres termes, il s'agit d'un ordre de visite des sommets tel qu'un sommet soit toujours visité avant ses successeurs.

Pour un graphe représenté en mémoire sous une forme facile à parcourir, par exemple par listes d'adjacence, le calcul d'un tri topologique est simple. Il suffit d'effectuer un parcours en profondeur du graphe, au cours duquel on empile chaque sommet une fois ses successeurs visités. En dépilant, on obtient un tri topologique.

Sans dédier une procédure pour ce traitement (gros graphes), on peut se re-servir d'un parcours en profondeur déjà effectué pour déterminer directement un ordre topologique. En effet, la lecture des sommets dans l'ordre inverse de la numérotation postfixe du parcours en profondeur est un ordre topologique.

Une autre façon de procéder consiste à rechercher une racine (sommet sans prédécesseur), l'enlever, et répéter l'opération autant de fois que nécessaire. C'est facile si l'on peut facilement calculer le nombre de prédécesseurs d'un sommet ; en effet, les racines à une itération sont parmi les successeurs des racines à l'itération précédente, et un compteur des prédécesseurs permet de les reconnaître.

Exemple de tri topologique

Soit $G=(S,A) \,$ un graphe orienté avec $S=\{1,2,3,4,5,6,7,8,9\} \,$ et $A=\{(1,2),(1,8),(2,8),(2,3),(3,6),(4,3),(4,5),(5,6),(9,8)\} \,$

Un ordre topologique sur ce graphe peut donner par exemple la succession des sommets 7,1,2,9,8,4,3,5,6. En effet, chaque sommet apparait bien avant ses successeurs. Il n'y a pas unicité de l'ordre.

Représentation graphique du graphe G

Exemple d'utilisation

• Make