Algorithme de Kosaraju
En informatique, l'algorithme de Kosaraju est un algorithme de calcul des composantes fortement connexes d'un graphe orienté. Il effectue deux parcours en profondeur et a une complexité linéaire en la taille du graphe.
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
Description
modifierSoit G un graphe. L'algorithme opère en deux étapes[1] :
- Exécuter l'algorithme de parcours en profondeur sur G et noter le post-ordre (c'est-à-dire l'ordre suffixe, ou ordre de remontée) du parcours, puis l'inverser.
- Exécuter l'algorithme de parcours en profondeur sur le graphe transposé Gt de G, en suivant l'ordre donné par la première étape.
Les arbres produits par le deuxième parcours sont les composantes fortement connexes (CFC).
Exemple
modifier
Considérons le graphe G donné dans la figure à droite.
- Un premier parcours de G pourrait par exemple commencer par w duquel on explore q. L'exploration de q termine. Puis celle de w. Puis on recommence à explorer depuis v, on continue avec t puis s, par exemple. Dans cet exemple, l'ordre suffixe de ce parcours est q, w, s, t, v.
- Effectuons maintenant un parcours de Gt. L'ordre suffixe inverse est v, t, s, w, q. Commençons le parcours en explorant v : on obtient la composante fortement connexe {v, s, t}. Maintenant, t et s ont déjà été explorés. Continuons en explorant w : on obtient la composante fortement connexe {w}. Continuons en explorant q : on obtient la composante fortement connexe {q}.
Complexité
modifierSi le graphe est donné sous forme de liste d'adjacence, l'algorithme a une complexité linéaire en fonction du nombre de sommets et d'arcs de G.
Histoire
modifierCet algorithme a été élaboré par S. Rao Kosaraju, professeur d'algorithmique à l'université Johns-Hopkins. La légende raconte qu'il enseignait l'algorithme de Tarjan à ses étudiants. Ayant oublié ses notes de cours, Kosaraju improvise un algorithme, et c'est en se trompant qu'il aurait trouvé cet algorithme [2]. Dans leur livre Data Structures and Algorithms (Addison-Wesley, 1983)[3], Alfred V. Aho, John E. Hopcroft et Jeffrey D. Ullman créditent S. Rao Kosaraju de cet algorithme qui est publié par Micha Sharir (en) indépendamment en 1981[4].
Notes et références
modifier- Cormen et al, Section 22.5.
- Jeff Erickson, Algorithms, [S.N.], (ISBN 1-7926-4483-3 et 978-1-7926-4483-2, OCLC 1128024005, lire en ligne), p. 242
- (en) Alfred V. Aho, John E. Hopcroft et Jeffrey Ullman, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., , 427 p. (ISBN 978-0-201-00023-8, lire en ligne)
- Cormen et al, p. 544.
