Composantes Fortement Connexes (Kosaraju)
Deux DFS sur le graphe et son transposé
Enonce
Implémenter kosaraju(G) qui renvoie la liste des composantes fortement connexes (chacune sous forme de liste de sommets).
Tester sur un graphe contenant 3 CFC distinctes : par exemple {0:[1], 1:[2], 2:[0,3], 3:[4], 4:[5,6], 5:[3], 6:[]}.
Signature attendue
def kosaraju(G: dict) -> list:📖 Rappel de cours
Dans un graphe orienté, deux sommets $u$ et $v$ sont dans la même composante fortement connexe (CFC) s'il existe un chemin de $u$ à $v$ et un chemin de $v$ à $u$. Les CFC partitionnent les sommets.
Algorithme de Kosaraju (1978) :
- DFS sur $G$ : noter l'ordre de fin des sommets (post-ordre)
- Construire le graphe transposé $G^T$ (toutes les arêtes inversées)
- DFS sur $G^T$ en visitant les sommets dans l'ordre inverse du post-ordre. Chaque arborescence du second DFS est une CFC.
Pourquoi ça marche :
Les CFC d'un graphe et de son transposé sont identiques. En attaquant $G^T$ depuis le sommet de plus haut post-ordre dans $G$, on est sûr de rester dans une seule CFC : on ne peut pas « déborder » vers une autre CFC car cela demanderait un cycle dans le DAG des CFC.
Application phare : compilateurs (analyse de variables vivantes), 2-SAT, analyse de dépendances cycliques.
← Exercices sur les graphes en Python — BFS, DFS, Dijkstra
Exercices du meme theme
- Détection de Cycle (graphe orienté)
- Diamètre d'un Arbre
- Algorithme de Floyd-Warshall
- Algorithme A* sur Grille
- Flot Maximal — Edmonds-Karp
- Critère de Delaunay (in-circle)
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.