Componentes fuertemente conexas con Kosaraju
Ejecute DFS en el grafo original para obtener el orden de finalización, transponga el grafo y vuelva a ejecutar DFS en orden inverso de finalización para identificar las SCC.
Componentes fuertemente conexas con Kosaraju es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 4 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.
Definición de las componentes fuertemente conexas
Una componente fuertemente conexa (SCC) de un grafo dirigido es un conjunto maximal de nodos tal que existe un camino desde cada nodo hasta cualquier otro nodo del conjunto. Por ejemplo, si los nodos A, B y C forman un ciclo (A→B→C→A), todos pertenecen a la misma SCC. Un nodo individual sin un bucle sobre sí mismo constituye su propia SCC. Las SCC revelan la estructura cíclica de un grafo dirigido.
Algoritmo de Kosaraju: dos pasadas de DFS
El algoritmo de Kosaraju encuentra todas las SCC en O(V + E) mediante dos pasadas de DFS. Pasada 1: ejecute DFS en el grafo original e inserte los nodos en una pila siguiendo el orden de finalización (postorden). Pasada 2: ejecute DFS en el grafo transpuesto (invertido), procesando los nodos en orden inverso de finalización (extrayéndolos de la pila). Cada árbol de DFS de la pasada 2 es una SCC.
Por qué funciona Kosaraju
En la pasada 1, la SCC cuyo árbol de DFS termina último es la que no tiene aristas salientes hacia otras SCC: una SCC «sumidero» en el DAG de condensación. En el grafo transpuesto, esta SCC no tiene aristas entrantes desde otras SCC, por lo que un DFS iniciado en ella permanece confinado dentro de la misma SCC. Cada DFS posterior de la pasada 2 permanece dentro de su propia SCC, porque todas las aristas entre SCC se invirtieron y conducen de vuelta a SCC ya visitadas.
Pasada 1: construir el orden de finalización
Ejecute DFS en el grafo original e inserte cada nodo en una pila después de que termine (postorden). En esta pasada no importan las componentes; solo importa el orden de finalización. El último nodo en finalizar pertenecerá a una SCC «origen» del DAG de condensación.
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_graphPasada 2: DFS en el grafo transpuesto
Extraiga los nodos de la pila de finalización (comenzando por el mayor tiempo de finalización) y ejecute DFS en el grafo transpuesto. Cada DFS iniciado desde un nodo no visitado descubre exactamente una SCC. Marque todos los nodos alcanzados en este DFS como pertenecientes a la misma componente.
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 similarTransposición del grafo
El grafo transpuesto invierte todas las aristas: si el grafo original contiene u → v, el transpuesto contiene v → u. La transposición conserva las SCC: si A y B pertenecen a la misma SCC en el grafo original, siguen perteneciendo a la misma SCC en el transpuesto, ya que todos los caminos se invierten, pero siguen conectándolos. Construir el grafo transpuesto durante el análisis de la entrada, como se muestra arriba, evita un paso de transposición independiente.
Versión iterativa para grafos grandes
Para grafos grandes, sustituya el DFS recursivo por un DFS iterativo que utilice una pila explícita para evitar el límite de recursión de Python. La versión iterativa apila nodos, los procesa y mantiene un marcador independiente de 'return' para simular el recorrido en postorden.
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')Algoritmo de Tarjan: alternativa para las SCC
El algoritmo de Tarjan encuentra las SCC en una sola pasada de DFS, frente a las dos pasadas de Kosaraju. Mantiene una pila de nodos y asigna a cada nodo un tiempo de descubrimiento y un valor low-link. Cuando el tiempo de descubrimiento de un nodo coincide con su valor low-link, ese nodo es la raíz de una SCC. El algoritmo de Tarjan es ligeramente más complejo de implementar, pero evita construir el grafo transpuesto. Ambos tienen una complejidad de O(V + E).
Aplicaciones de las SCC
Las SCC se utilizan en: (1) Optimización de compiladores — para identificar funciones mutuamente recursivas. (2) Análisis de redes sociales — para encontrar comunidades muy cohesionadas. (3) Problema 2-SAT — para determinar la satisfacibilidad de cláusulas de 2 literales. (4) Rastreo web — para identificar grupos de páginas con enlaces cruzados densos. (5) DAG de condensación — después de encontrar las SCC, la condensación del grafo es un DAG, lo que permite realizar análisis topológicos de grafos cíclicos.
DAG de condensación
La condensación de un grafo dirigido contrae cada SCC en un único nodo y añade una arista entre dos supernodos si existe una arista entre sus SCC constituyentes. El resultado siempre es un DAG, por lo que se puede ejecutar una ordenación topológica sobre él. Esto permite aplicar algoritmos que solo funcionan en DAG, como la programación dinámica, a grafos dirigidos generales trabajando sobre su condensación.
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)]Número de SCC y propiedades del grafo
El número de SCC de un grafo dirigido revela su estructura cíclica. Un DAG tiene n SCC, ya que cada nodo constituye su propia SCC. Un grafo fuertemente conexo tiene exactamente 1 SCC. En general, al condensarlas, las SCC forman un DAG: la condensación. Si el DAG de condensación tiene una única fuente (nodo con grado de entrada 0) y un único sumidero (nodo con grado de salida 0), se cumplen ciertas propiedades de conectividad. Estas propiedades se ponen a prueba en problemas de alcanzabilidad después de añadir un número mínimo de aristas.
Comprobación rápida
Evalúe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Resumen de la lección
En esta lección aprendió: las SCC son conjuntos máximos en los que se puede llegar a cualquier nodo desde cualquier otro, Kosaraju utiliza dos pasadas de DFS: la primera sobre el grafo original para obtener el orden de finalización y la segunda sobre el grafo transpuesto, y la condensación de cualquier grafo dirigido es un DAG que puede utilizarse para análisis posteriores. A continuación, crearemos estructuras de datos TrieNode para las operaciones de inserción, búsqueda y prefijos.
Preguntas frecuentes
¿La lección «Componentes fuertemente conexas con Kosaraju» es gratis?
Sí — el texto completo de «Componentes fuertemente conexas con Kosaraju» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Componentes fuertemente conexas con Kosaraju»?
Ejecute DFS en el grafo original para obtener el orden de finalización, transponga el grafo y vuelva a ejecutar DFS en orden inverso de finalización para identificar las SCC. Practicas DSA Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar DSA Interview Prep?
No se requiere experiencia previa. DSA Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 4 de 4.
¿Cuánto tiempo toma la lección «Componentes fuertemente conexas con Kosaraju»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de DSA Interview Prep?
Sí. Cada lección de DSA Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Algoritmo de Kahn: ordenación topológica con BFS
- Ordenación topológica con DFS en postorden
- Course Schedule I y II
- Componentes fuertemente conexas con Kosaraju