El algoritmo de Kosaraju encuentra los componentes fuertemente conexos (CFC) de un grafo dirigido. Un CFC es un grupo de vértices donde cada vértice puede alcanzar a cualquier otro. El algoritmo realiza dos búsquedas en profundidad: la primera registra el orden en que los vértices terminan, y la segunda se ejecuta sobre el grafo con todas las aristas invertidas, tomando los vértices en orden inverso al de finalización. Cada árbol de la segunda búsqueda es un CFC. Se ejecuta en tiempo O(V + E).
Si comprimes cada CFC en un solo nodo, lo que queda es un grafo dirigido sin ciclos. Por eso los CFC aparecen en el análisis de dependencias, la detección de interbloqueos, 2-SAT y cualquier problema donde haya que colapsar los ciclos primero.
Las dos pasadas, paso a paso
- Ejecuta DFS sobre todo el grafo. Cuando un vértice termina (todos sus vecinos salientes están listos), agrégalo a una lista.
- Invierte todas las aristas para obtener el grafo traspuesto.
- Recorre la lista de finalización de atrás hacia adelante. Para cada vértice aún no visitado, ejecuta DFS sobre el grafo traspuesto. Todo lo que alcance esa búsqueda es un CFC.
Ambos bucles deben comenzar desde cada vértice no visitado, no solo desde el vértice 0, porque el grafo puede no estar conectado.
Un ejemplo resuelto
Toma 8 vértices y estas aristas:
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)
Los CFC deberían ser 2, 5 y 7.
Primera pasada
Comienza el DFS en 0 y avanza 0 → 1 → 2 → 3 → 4 → 5. El vértice 5 no tiene a dónde ir que no haya visitado, así que termina primero, luego 4, luego 3. De vuelta en 2 no queda nada, así que terminan 2, 1 y 0. El vértice 6 no ha sido visitado, así que empieza ahí: 5 ya está terminado, así que ve a 7, que termina, y luego 6. El orden de finalización es:
5, 4, 3, 2, 1, 0, 7, 6
Segunda pasada
Invierte todas las aristas y procesa los vértices desde el final de esa lista: 6 primero. En el grafo invertido, 6 solo puede alcanzar a 7, así que 7 es el primer CFC. El siguiente no visitado es 0, que alcanza a 2 y 1 en el grafo invertido, dando 2. La arista 2 → 3 ahora apunta 3 → 2, pero 2 ya está asignado, así que la búsqueda se detiene ahí. Por último, 3 alcanza a 5 y 4, dando 5.
Por qué funciona
Piensa en el grafo de los CFC (cada componente comprimido en un solo nodo), que no tiene ciclos. En la primera pasada, el vértice que termina último siempre pertenece a un componente "fuente", uno sin aristas que lleguen desde otros componentes no asignados. Invertir las aristas convierte esa fuente en un sumidero, así que un DFS iniciado ahí no puede salir de su propio componente. Una vez que ese componente se elimina, el mismo argumento se aplica al siguiente.
En una entrevista, ese suele ser el nivel de demostración que se espera: el orden de finalización elige un componente de inicio seguro, e invertir las aristas evita que la segunda búsqueda se filtre hacia otros componentes.
Implementación en Python
Esta versión usa DFS iterativo, así que no alcanzará el límite de recursión de Python en grafos profundos.
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]]
El orden de los vértices dentro de cada componente depende del recorrido, así que compara los componentes como conjuntos en tus pruebas. Verificamos esta implementación contra una comprobación de alcanzabilidad por fuerza bruta en 2.000 grafos aleatorios.
Complejidad
| Paso | Tiempo |
|---|---|
| Primer DFS | O(V + E) |
| Construcción del grafo invertido | O(V + E) |
| Segundo DFS | O(V + E) |
| Total | O(V + E) |
El espacio es O(V + E) para las dos listas de adyacencia, más O(V) para el arreglo de visitados, el orden de finalización y la pila.
Errores que lo rompen
El bug más común es registrar los vértices cuando el DFS los alcanza por primera vez en lugar de cuando terminan. Otros son olvidar invertir el orden de finalización para la segunda pasada, ejecutar la segunda pasada sobre el grafo original en vez del invertido, no limpiar el arreglo de visitados entre pasadas, y comenzar solo desde el vértice 0, con lo que se saltan las partes desconectadas. El DFS recursivo también puede desbordar la pila en cadenas largas, por eso el código de arriba es iterativo.
Buenos casos de prueba: un solo vértice, un vértice con un auto-bucle, un ciclo grande, una cadena unidireccional (cada vértice es su propio CFC), dos ciclos unidos por una arista, y un grafo desconectado.
Kosaraju vs. Tarjan
Ambos se ejecutan en O(V + E). Kosaraju hace dos pasadas y construye el grafo invertido, lo que lo hace más fácil de explicar y de implementar correctamente. El algoritmo de Tarjan lo hace en una sola pasada sin grafo invertido, pero rastrea índices de descubrimiento y valores low-link en una pila, lo que implica más estado que mantener en orden. En una entrevista, usa el que puedas implementar correctamente y explicar. Si el entrevistador pide una sola pasada, esa es una señal para usar Tarjan.
Practicar problemas de grafos
Traza el ejemplo de arriba a mano una vez antes de escribir código; la mayoría de los bugs se manifiestan como un orden de finalización incorrecto. Guías relacionadas: Floyd–Warshall para caminos más cortos entre todos los pares, Bellman–Ford para grafos con aristas negativas, y nuestra chuleta de Big O. Si usas YesToTheOffer en la práctica de programación, su ayuda de codificación por captura de pantalla puede revisar tu enfoque, y la transcripción de la sesión muestra si explicaste tu razonamiento con claridad.
Practica entrevistas de programación con retroalimentación
Captura de pantalla de ayuda de programación y una transcripción de tu sesión de práctica. 30 minutos gratis.
