Algorithme de Kosaraju

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 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, t, s}. 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}.

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.

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

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

• (en) « Strong Components »