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

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é G^t 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é G^t.

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 G^t. 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.], 2019 (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., 1983, 427 p. (ISBN 978-0-201-00023-8, lire en ligne)
4. Cormen et al, p. 544.

Bibliographie

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction à l'algorithmique, Dunod, 2002 [détail de l’édition]

Lien externe

• (en) « Strong Components »

• Portail de l'informatique théorique