Tri topologique
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de
|
|
En théorie des graphes, et plus spécialement en algorithmique des graphes, un tri topologique d'un graphe orienté acyclique (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 : lue de haut en bas, la pile obtenue est un tri 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.
