L'algorithme de Kosaraju permet de trouver les composantes fortement connexes (CFC) d'un graphe orienté. Une CFC est un ensemble de sommets où chaque sommet peut atteindre tous les autres. L'algorithme effectue deux parcours en profondeur : le premier enregistre l'ordre dans lequel les sommets terminent leur exploration, et le second s'exécute sur le graphe dont toutes les arêtes ont été inversées, en traitant les sommets dans l'ordre inverse de fin. Chaque arbre du second parcours correspond à une CFC. La complexité est de O(V + E).
Si l'on réduit chaque CFC à un seul nœud, on obtient un graphe orienté sans cycle. C'est pourquoi les CFC apparaissent dans l'analyse de dépendances, la détection d'interblocages, le problème 2-SAT, et tout problème où il faut d'abord éliminer les cycles.
Les deux passes, étape par étape
- Lancer un DFS sur tout le graphe. Quand un sommet termine (tous ses voisins sortants sont traités), on l'ajoute à une liste.
- Inverser toutes les arêtes pour obtenir le graphe transposé.
- Parcourir la liste des fins d'exploration du dernier au premier. Pour chaque sommet non encore visité, lancer un DFS sur le graphe transposé. Tout ce que ce parcours atteint forme une CFC.
Les deux boucles doivent démarrer depuis chaque sommet non visité, pas seulement depuis le sommet 0, car le graphe peut ne pas être connexe.
Un exemple concret
Prenons 8 sommets et ces arêtes :
0 → 1, 1 → 2, 2 → 0 (cycle A: 0, 1, 2)
2 → 3
3 → 4, 4 → 5, 5 → 3 (cycle B: 3, 4, 5)
6 → 5
6 → 7, 7 → 6 (cycle C: 6, 7)
Les CFC attendues sont 2, 5 et 7.
Première passe
On démarre le DFS en 0 et on suit 0 → 1 → 2 → 3 → 4 → 5. Le sommet 5 n'a nulle part où aller de nouveau, donc il termine en premier, puis 4, puis 3. De retour en 2, il ne reste rien, donc 2, 1 et 0 terminent. Le sommet 6 n'a pas été visité, on part donc de là : 5 est déjà traité, on va donc en 7, qui termine, puis 6. L'ordre de fin est :
5, 4, 3, 2, 1, 0, 7, 6
Seconde passe
On inverse toutes les arêtes et on traite les sommets depuis la fin de cette liste : 6 en premier. Dans le graphe inversé, 6 ne peut atteindre que 7, donc 7 est la première CFC. Le prochain sommet non visité est 0, qui atteint 2 et 1 dans le graphe inversé, ce qui donne 2. L'arête 2 → 3 pointe désormais 3 → 2, mais 2 est déjà assigné, donc le parcours s'arrête là. Enfin, 3 atteint 5 et 4, ce qui donne 5.
Pourquoi ça fonctionne
Considérons le graphe des CFC (chaque composante réduite à un seul nœud), qui est sans cycle. Lors de la première passe, le sommet qui termine en dernier appartient toujours à une composante « source », c'est-à-dire sans arête entrante venant d'autres composantes non assignées. Inverser les arêtes transforme cette source en puits, donc un DFS lancé depuis ce sommet ne peut pas sortir de sa propre composante. Une fois cette composante retirée, le même raisonnement s'applique à la suivante.
En entretien, c'est généralement le niveau de preuve attendu : l'ordre de fin sélectionne une composante de départ sûre, et l'inversion des arêtes empêche le second parcours de déborder sur d'autres composantes.
Implémentation en Python
Cette version utilise un DFS itératif, ce qui évite d'atteindre la limite de récursion de Python sur les graphes profonds.
from collections import defaultdict
def kosaraju(n, edges):
graph = defaultdict(list)
reverse = defaultdict(list)
for u, v in edges:
graph[u].append(v)
reverse[v].append(u)
# Pass 1: record vertices in the order they finish (iterative DFS)
visited = [False] * n
order = []
for start in range(n):
if visited[start]:
continue
visited[start] = True
stack = [(start, iter(graph[start]))]
while stack:
node, neighbors = stack[-1]
for nxt in neighbors:
if not visited[nxt]:
visited[nxt] = True
stack.append((nxt, iter(graph[nxt])))
break
else:
stack.pop()
order.append(node)
# Pass 2: DFS on the reversed graph, latest finish time first
visited = [False] * n
components = []
for start in reversed(order):
if visited[start]:
continue
visited[start] = True
component = []
stack = [start]
while stack:
node = stack.pop()
component.append(node)
for nxt in reverse[node]:
if not visited[nxt]:
visited[nxt] = True
stack.append(nxt)
components.append(component)
return components
edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3), (6, 5), (6, 7), (7, 6)]
print(kosaraju(8, edges)) # [[6, 7], [0, 2, 1], [3, 5, 4]]
L'ordre des sommets au sein de chaque composante dépend du parcours, donc comparez les composantes en tant qu'ensembles dans vos tests. Nous avons vérifié cette implémentation contre une vérification par force brute de l'accessibilité sur 2 000 graphes aléatoires.
Complexité
| Étape | Temps |
|---|---|
| Premier DFS | O(V + E) |
| Construction du graphe inversé | O(V + E) |
| Second DFS | O(V + E) |
| Total | O(V + E) |
L'espace est de O(V + E) pour les deux listes d'adjacence, plus O(V) pour le tableau des visites, l'ordre de fin et la pile.
Les erreurs qui cassent tout
Le bug le plus courant consiste à enregistrer les sommets dès que le DFS les atteint plutôt qu'au moment où ils terminent. Viennent ensuite l'oubli d'inverser l'ordre de fin pour la seconde passe, l'exécution de la seconde passe sur le graphe original au lieu du graphe inversé, la non-réinitialisation du tableau des visites entre les deux passes, et le démarrage uniquement depuis le sommet 0, ce qui fait sauter les parties non connexes. Le DFS récursif peut aussi provoquer un débordement de pile sur de longues chaînes, c'est pourquoi le code ci-dessus est itératif.
Bons cas de test : un sommet unique, un sommet avec une boucle sur lui-même, un grand cycle, une chaîne à sens unique (chaque sommet est sa propre CFC), deux cycles reliés par une arête, et un graphe non connexe.
Kosaraju vs. Tarjan
Les deux ont une complexité de O(V + E). Kosaraju effectue deux passes et construit le graphe inversé, ce qui le rend plus facile à expliquer et à implémenter correctement. L'algorithme de Tarjan le fait en une seule passe sans graphe inversé, mais il suit les indices de découverte et les valeurs low-link sur une pile, ce qui représente davantage d'état à gérer. En entretien, utilisez celui que vous pouvez implémenter correctement et expliquer. Si l'intervieweur demande une seule passe, c'est un signal pour Tarjan.
S'entraîner sur les problèmes de graphes
Tracez l'exemple ci-dessus à la main une fois avant d'écrire du code ; la plupart des bugs se manifestent par un ordre de fin erroné. Guides connexes : Floyd–Warshall pour les plus courts chemins entre toutes les paires, Bellman–Ford pour les graphes avec arêtes négatives, et notre aide-mémoire Big O. Si vous utilisez YesToTheOffer en entraînement de code, son aide au codage par capture d'écran peut vérifier votre approche, et la transcription de session montre si vous avez expliqué votre raisonnement clairement.
Entraînez-vous aux entretiens de codage avec des retours
Capture d'écran de l'aide au codage et transcription de votre session d'entraînement. 30 minutes gratuites.
