Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Tri topologique
Résumé
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 un ordre total sur l'ensemble des sommets, dans lequel s précède t pour tout arc d'un sommet s à un sommet t.
En d'autres termes, un tri topologique est une extension linéaire de l'ordre partiel sur les sommets déterminés par les arcs.
Soit un graphe orienté avec et .
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 apparaît bien avant ses successeurs. Il n'y a pas unicité de l'ordre.
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ésempilant, 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.
L'algorithme de tri topologique d'un graphe fonctionne sur le même principe que l'algorithme de parcours en profondeur en rajoutant une notion de date de début et de date de fin. L'ordre topologique sera à la fin les sommets dans l'ordre du tableau de date de fin.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.