Algorithme de Kosaraju

Un article de Wikipédia, l'encyclopédie libre.

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 | modifier le code]

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 (i.e. suffixe) 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 | modifier le code]

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

Complexité[modifier | modifier le code]

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 | modifier le code]

Cet algorithme a été trouvé par S. Rao Kosaraju, professeur d'algorithmique à l'université Johns-Hopkins. On 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[réf. nécessaire]. Dans leur livre Data Structures and Algorithms (Addison-Wesley, 1983)[2], 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[3].

Notes et références[modifier | modifier le code]

  1. Cormen et al, Section 22.5.
  2. (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)
  3. Cormen et al, p. 544.

Bibliographie[modifier | modifier le code]

Lien externe[modifier | modifier le code]