Composantes fortement connexes avec Kosaraju
Exécutez DFS sur le graphe initial pour obtenir l’ordre de fin, transposez le graphe, puis exécutez de nouveau DFS dans l’ordre de fin inverse afin d’identifier les composantes fortement connexes.
Composantes fortement connexes avec Kosaraju est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.
Définition des composantes fortement connexes
Une composante fortement connexe (SCC) d’un graphe orienté est un ensemble maximal de sommets tel qu’il existe un chemin de chaque sommet vers tout autre sommet de l’ensemble. Par exemple, si les sommets A, B et C forment un cycle (A→B→C→A), ils appartiennent tous à la même SCC. Un sommet isolé, sans boucle sur lui-même, constitue sa propre SCC. Les SCC révèlent la structure cyclique d’un graphe orienté.
Algorithme de Kosaraju : deux passes DFS
L’algorithme de Kosaraju trouve toutes les SCC en O(V + E) à l’aide de deux passes DFS. Passe 1 : exécutez DFS sur le graphe d’origine et empilez les sommets selon leur ordre de terminaison, c’est-à-dire en postordre. Passe 2 : exécutez DFS sur le graphe transposé, ou inversé, en traitant les sommets dans l’ordre inverse de leur terminaison, en utilisant pop sur la pile. Chaque arbre DFS de la passe 2 constitue une SCC.
Pourquoi l’algorithme de Kosaraju fonctionne
Lors de la passe 1, la SCC dont l’arbre DFS se termine en dernier est celle qui n’a pas d’arcs sortants vers d’autres SCC, une SCC « puits » dans le DAG de condensation. Dans le graphe transposé, cette SCC n’a aucun arc entrant provenant d’autres SCC : un DFS lancé depuis celle-ci reste donc confiné à cette SCC pendant la passe 2. Chaque DFS suivant de la passe 2 reste dans sa propre SCC, car tous les arcs entre SCC ont été inversés et ramènent vers des SCC déjà visitées.
Passe 1 : construire l’ordre de terminaison
Exécutez DFS sur le graphe d’origine et empilez chaque sommet lorsqu’il a terminé, en postordre. Les composantes ne nous intéressent pas pendant cette passe : seul l’ordre de terminaison compte. Le dernier sommet à terminer appartiendra à une SCC « source » du DAG de condensation.
from collections import defaultdict
def kosaraju(n, edges):
graph = defaultdict(list)
rev_graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
rev_graph[v].append(u) # reversed edges
visited = set()
finish_stack = []
def dfs1(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited:
dfs1(nxt)
finish_stack.append(node) # push after all neighbours done
for i in range(n):
if i not in visited:
dfs1(i)
return finish_stack, rev_graphPasse 2 : DFS sur le graphe transposé
Utilisez pop pour retirer les sommets de la pile des terminaisons, en commençant par le plus grand temps de terminaison, puis exécutez DFS sur le graphe transposé. Chaque DFS lancé depuis un sommet non visité découvre exactement une SCC. Marquez tous les sommets atteints par ce DFS comme appartenant à la même composante.
from collections import defaultdict
def kosaraju_full(n, edges):
graph = defaultdict(list)
rev_graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
rev_graph[v].append(u)
visited = set()
finish_stack = []
def dfs1(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited: dfs1(nxt)
finish_stack.append(node)
for i in range(n):
if i not in visited: dfs1(i)
visited.clear()
sccs = []
def dfs2(node, component):
visited.add(node)
component.append(node)
for nxt in rev_graph[node]:
if nxt not in visited: dfs2(nxt, component)
while finish_stack:
node = finish_stack.pop()
if node not in visited:
component = []
dfs2(node, component)
sccs.append(component)
return sccs
# Graph with SCCs: {0,1,2} and {3}
edges = [(0,1),(1,2),(2,0),(1,3)]
print(kosaraju_full(4, edges)) # [[3], [0,2,1]] or similarTransposition du graphe
Le graphe transposé inverse chaque arc : si le graphe d’origine contient u → v, le graphe transposé contient v → u. La transposition conserve les SCC : si A et B appartiennent à la même SCC dans le graphe d’origine, ils restent dans la même SCC dans le graphe transposé, puisque tous les chemins sont inversés mais restent connectés. Construire le graphe transposé lors de la lecture des entrées, comme ci-dessus, évite une étape de transposition distincte.
Version itérative pour les grands graphes
Pour les grands graphes, remplacez le DFS récursif par un DFS itératif utilisant une pile explicite afin d’éviter la limite de récursion de Python. La version itérative empile les nœuds, les traite et conserve un marqueur « retour » distinct pour simuler un parcours en postordre.
def dfs1_iterative(start, graph, visited, finish_stack):
stack = [(start, iter(graph[start]))]
visited.add(start)
while stack:
node, neighbours = stack[-1]
try:
nxt = next(neighbours)
if nxt not in visited:
visited.add(nxt)
stack.append((nxt, iter(graph[nxt])))
except StopIteration:
stack.pop()
finish_stack.append(node)
print('Iterative DFS for large graphs avoids recursion limit')Algorithme de Tarjan : autre approche des SCC
L’algorithme de Tarjan trouve les SCC en un seul parcours DFS, contre deux parcours pour celui de Kosaraju. Il maintient une pile de nœuds et attribue à chaque nœud un temps de découverte et une valeur de lien faible. Lorsque le temps de découverte d’un nœud est égal à sa valeur de lien faible, ce nœud est la racine d’une SCC. L’algorithme de Tarjan est légèrement plus complexe à implémenter, mais évite de construire le graphe transposé. Les deux algorithmes sont en O(V + E).
Applications des SCC
Les SCC sont utilisées pour : (1) l’optimisation des compilateurs — identifier les fonctions mutuellement récursives ; (2) l’analyse des réseaux sociaux — trouver les communautés très soudées ; (3) le problème 2-SAT — déterminer la satisfiabilité de clauses à deux littéraux ; (4) l’exploration du Web — identifier les groupes de pages comportant de nombreux liens croisés ; (5) la condensation DAG — après avoir trouvé les SCC, la condensation du graphe est un DAG, ce qui permet l’analyse topologique de graphes cycliques.
Condensation DAG
La condensation d’un graphe orienté contracte chaque SCC en un nœud unique et ajoute une arête entre deux super-nœuds s’il existe une arête entre leurs SCC constitutives. Le résultat est toujours un DAG — vous pouvez y exécuter un tri topologique. Cela permet d’appliquer à des graphes orientés généraux des algorithmes qui ne fonctionnent que sur les DAG, comme DP, en travaillant sur leur condensation.
def build_condensation(n, edges, sccs):
# Assign each node to its SCC index
scc_id = [0] * n
for idx, component in enumerate(sccs):
for node in component:
scc_id[node] = idx
# Build condensation edges
condensation_edges = set()
for u, v in edges:
su, sv = scc_id[u], scc_id[v]
if su != sv:
condensation_edges.add((su, sv))
return list(condensation_edges)
edges = [(0,1),(1,2),(2,0),(1,3)]
sccs = [[3],[0,1,2]]
print(build_condensation(4, edges, sccs)) # [(0,1)] or [(1,0)]Nombre de SCC et propriétés des graphes
Le nombre de SCC dans un graphe orienté révèle sa structure cyclique. Un DAG possède n SCC, car chaque nœud constitue sa propre SCC. Un graphe fortement connexe possède exactement 1 SCC. En général, les SCC forment un DAG une fois condensées : c’est la condensation. Si le DAG de condensation possède une source unique, c’est-à-dire un nœud de degré entrant 0, et un puits unique, c’est-à-dire un nœud de degré sortant 0, certaines propriétés de connexité sont vérifiées dans la condensation. Ces propriétés sont étudiées dans des problèmes portant sur l’accessibilité après l’ajout d’un nombre minimal d’arêtes.
Vérification rapide
Évaluez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris que : les SCC sont des ensembles maximaux dans lesquels chaque nœud est accessible depuis tous les autres ; Kosaraju utilise deux parcours DFS — le premier sur le graphe initial pour déterminer l’ordre de fin, puis le second sur le graphe transposé ; et la condensation de tout graphe orienté est un DAG utilisable pour poursuivre l’analyse. Nous allons ensuite construire des structures de données TrieNode pour insert, search et les opérations sur les préfixes.
Apprends Python avec un tuteur IA — gratuit
Écris et exécute du vrai code dans ton navigateur, obtiens de l'aide instantanée d'un tuteur IA disponible 24h/24, et reprends là où tu t'es arrêté sur le web ou dans l'app.
- Cours
- 30
- Leçons
- 120
Questions Fréquemment Posées
La leçon « Composantes fortement connexes avec Kosaraju » est-elle gratuite ?
Oui — le texte complet de « Composantes fortement connexes avec Kosaraju » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Composantes fortement connexes avec Kosaraju » ?
Exécutez DFS sur le graphe initial pour obtenir l’ordre de fin, transposez le graphe, puis exécutez de nouveau DFS dans l’ordre de fin inverse afin d’identifier les composantes fortement connexes. Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?
Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.
Combien de temps prend la leçon « Composantes fortement connexes avec Kosaraju » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?
Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Algorithme de Kahn : tri topologique par BFS
- Tri topologique par DFS en post-ordre
- Planification de cours I et II
- Composantes fortement connexes avec Kosaraju