Algorithme de Kosaraju

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.
Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

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 ?

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.

Description

Soit G un graphe. L'algorithme opère en deux étapes[1] :

  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.
  2. 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

Exemple de graphe orienté G et son graphe transposé Gt.

Considérons le graphe G donné dans la figure à droite.

  1. 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.
  2. 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é

Si 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

Cet 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

  1. ↑ Cormen et al, Section 22.5.
  2. ↑ Jeff Erickson, Algorithms, [S.N.], (ISBN 1-7926-4483-3 et 978-1-7926-4483-2, OCLC 1128024005, lire en ligne), p. 242
  3. ↑ (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)
  4. ↑ Cormen et al, p. 544.

Bibliographie

Lien externe

  • (en) « Strong Components »
  • icône décorative Portail de l'informatique théorique