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.

Description

modifier

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

modifier
 
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é

modifier

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

modifier

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

modifier
  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

modifier

Lien externe

modifier