Détecteur SCC de Kosaraju

Pseudocode

Deux parcours en profondeur et un graphe transposé. Rien d'astucieux ne se produit à l'intérieur de chaque passe; tout le travail est accompli par l'ordre dans lequel la seconde s'exécute.

Kosaraju(graphe):
    // Passe 1: enregistrer l ordre de fin
    ordre = []
    pour chaque u non visite: dfs1(u)

    dfs1(u): marquer u visite
             pour chaque arete (u,v): si non visite: dfs1(v)
             ordre.ajouter(u)          // a la fin

    // Passe 2: DFS sur la transposee en ordre de fin inverse
    gt = transposer(graphe)     // inverser chaque arete
    pour chaque u dans inverse(ordre):
        si u non visite:
            l arbre issu de u dans gt est une CFC

Pourquoi cela fonctionne: inverser toutes les arêtes laisse les composantes fortement connexes intactes, car si tu pouvais aller de x à y puis revenir, tu le peux toujours. Ce que l'inversion change, c'est la direction des arêtes entre composantes. Démarrer par le sommet terminé en dernier garantit que tu commences dans une composante source de la condensation, si bien que le second DFS ne peut s'en échapper vers une autre composante.

Exemple détaillé, étape par étape

Exécute Kosaraju sur le graphe orienté déjà utilisé pour Tarjan, afin de comparer directement les deux.

Graphe d'exemple: Arêtes orientées A vers B, B vers C, C vers A, B vers D, D vers E, E vers D, et C vers F.

1. Passe 1 depuis A. Descends A, B, C; C vers A est déjà visité, prends donc C vers F. F n'a aucune arête sortante et termine en premier. C termine ensuite, la recherche remonte vers B et prend B vers D, puis D vers E; E vers D étant déjà visité, E termine, puis D, puis B, puis A.
2. Ordre de fin. Les sommets terminent dans l'ordre F, C, E, D, B, A. En l'inversant on obtient l'ordre de traitement de la passe 2: A, B, D, E, C, F.
3. Transposer le graphe. Chaque arête bascule: B vers A, C vers B, A vers C, D vers B, E vers D, D vers E, F vers C.
4. Passe 2 en démarrant à A. Dans la transposée, A atteint C, C atteint B, et B n'atteint que A, déjà visité. L'arbre couvre A, C et B, la première composante est donc {A, B, C}. Le point crucial est que la recherche n'a pas pu s'échapper vers D ni F, car dans la transposée ces arêtes pointent vers l'intérieur et non vers l'extérieur.
5. La passe 2 se poursuit. Le sommet non visité suivant dans l'ordre est D. Dans la transposée, D atteint B, déjà visité, et E, qui atteint D, déjà visité. La composante est {D, E}. Enfin F reste non visité: dans la transposée il n'atteint que C, déjà visité, c'est donc la composante singleton {F}.

Les composantes sont {A, B, C}, puis {D, E}, puis {F}. Compare avec Tarjan sur le même graphe, qui émet {F}, puis {D, E}, puis {A, B, C}. Les deux sont corrects et trouvent les mêmes trois composantes, mais Kosaraju les émet dans l'ordre topologique direct de la condensation tandis que Tarjan les émet en ordre inverse. Si l'ordre importe à ton code en aval, cette différence est la raison de préférer l'un à l'autre.

Complexité et son origine

Temps: O(V + E) · Espace: O(V + E)

Deux parcours en profondeur coûtent O(V + E) chacun, et construire le graphe transposé exige une passe sur toutes les arêtes, également O(V + E). La somme donne O(V + E) au total. C'est sur l'espace que Kosaraju perd réellement face à Tarjan: il doit stocker la structure d'adjacence transposée, soit une seconde copie complète de la liste d'arêtes en O(V + E), là où Tarjan ne nécessite que O(V) de comptabilité sur le graphe original. Sur un graphe de dizaines de millions d'arêtes cette différence devient déterminante, ce qui explique que Tarjan l'emporte généralement en production bien que les deux soient identiques en temps asymptotique.

Quand utiliser CFC de Kosaraju, et quand l'éviter

Tous les algorithmes linéaires de CFC coûtent O(V + E). Les différences portent sur la mémoire, le nombre de passes et la facilité d'écrire un code correct.

Pièges fréquents

• Utiliser l ordre de fin dans le sens direct au lieu de l inverse. La seconde passe doit traiter les sommets par date de fin décroissante. L'exécuter en ordre croissant démarre dans une composante puits et le DFS déborde entre frontières de composantes, fusionnant des CFC distinctes. C'est le bogue caractéristique de Kosaraju.
• Ajouter à l ordre à la découverte plutôt qu à la fin. Le sommet doit être empilé quand sa récursion s'achève, non lorsqu'il est atteint pour la première fois. L'ordre de découverte ne porte aucune des informations dont dépend l'algorithme.
• Oublier de réinitialiser l ensemble des visités entre les passes. Les deux recherches sont indépendantes. Transporter les marques de visite de la première passe dans la seconde fait que rien n'est exploré et que toutes les composantes reviennent vides.
• Transposer sur place. La seconde passe a besoin du graphe inversé alors que l'ordre de fin provient de l'original. Muter les listes d'adjacence originales plutôt que de construire une transposée distincte corrompt les deux.
• Supposer que cela fonctionne sur des graphes non orientés. La forte connexité est une notion orientée. Dans un graphe non orienté, toute composante connexe est trivialement fortement connexe, et un seul DFS ou Union-Find répond à la question à bien moindre coût.

Questions fréquentes

Comment fonctionne l'algorithme de Kosaraju?

Il exécute un parcours en profondeur sur le graphe original et enregistre l'ordre dans lequel les sommets se terminent. Il inverse ensuite toutes les arêtes et exécute un second parcours en profondeur, en traitant les sommets par date de fin décroissante. Chaque arbre issu de la seconde passe est exactement une composante fortement connexe.

Pourquoi l'inversion des arêtes fonctionne-t-elle?

L'inversion préserve la forte connexité, puisqu'un aller-retour entre deux sommets subsiste lorsque toutes les arêtes basculent. Ce qui change, c'est la direction entre composantes. Démarrer par le sommet terminé en dernier te place dans une composante source de la condensation, et après inversion ses liens sortants deviennent entrants, si bien que la recherche reste piégée dans la composante.

Quelle est la différence entre Kosaraju et Tarjan?

Les deux sont en O(V + E). Kosaraju utilise deux passes de DFS plus une copie transposée du graphe, il lui faut donc O(V + E) d'espace supplémentaire; Tarjan utilise une passe et O(V). Kosaraju est plus simple à expliquer et à implémenter, Tarjan plus rapide et plus léger en pratique. Ils émettent aussi les composantes dans des ordres opposés: Kosaraju en ordre topologique direct de la condensation, Tarjan en ordre inverse.

Quelle est la complexité temporelle de l'algorithme de Kosaraju?

O(V + E) en temps, issue de deux parcours linéaires plus une passe linéaire pour construire la transposée. L'espace est en O(V + E) car le graphe transposé doit être stocké, ce qui constitue la principale différence pratique avec Tarjan.

Kosaraju peut-il trouver des composantes dans un graphe non orienté?

Cela fonctionnerait mais serait inutile. Dans un graphe non orienté, toute composante connexe est déjà fortement connexe, si bien qu'un seul DFS ou une structure Union-Find les trouve en une passe sans construire de transposée.