Buscador SCC de Kosaraju

Pseudocódigo

Dos búsquedas en profundidad y un grafo transpuesto. Dentro de cada pasada no ocurre nada ingenioso; todo el trabajo lo hace el orden en que se ejecuta la segunda.

Kosaraju(grafo):
    // Pasada 1: registrar el orden de finalización
    orden = []
    para cada u no visitado: dfs1(u)

    dfs1(u): marcar u visitado
             para cada arista (u,v): si no visitado: dfs1(v)
             orden.añadir(u)          // al terminar

    // Pasada 2: DFS sobre la transpuesta en orden inverso
    gt = transponer(grafo)      // invertir cada arista
    para cada u en inverso(orden):
        si u no visitado:
            el árbol que crece desde u en gt es una SCC

Por qué funciona: invertir todas las aristas deja intactas las componentes fuertemente conexas, ya que si podías ir de x a y y volver, sigues pudiendo. Lo que sí cambia la inversión es la dirección de las aristas entre componentes. Empezar por el vértice que terminó el último garantiza que arrancas en una componente que es fuente de la condensación, de modo que el segundo DFS no puede escaparse de ella hacia otra componente.

Ejemplo resuelto, paso a paso

Ejecuta Kosaraju sobre el mismo grafo dirigido usado en el ejemplo de Tarjan, para poder compararlos directamente.

Grafo de ejemplo: Aristas dirigidas A a B, B a C, C a A, B a D, D a E, E a D, y C a F.

1. Pasada 1 desde A. Desciende por A, B, C; entonces C a A ya está visitado, así que toma C a F. F no tiene aristas salientes y termina el primero. C termina a continuación, luego la búsqueda retrocede a B y toma B a D, luego D a E, y como E a D ya está visitado E termina, después D, después B, después A.
2. Orden de finalización. Los vértices terminan en el orden F, C, E, D, B, A. Invirtiéndolo se obtiene el orden de procesamiento de la pasada 2: A, B, D, E, C, F.
3. Transponer el grafo. Cada arista se da la vuelta: B a A, C a B, A a C, D a B, E a D, D a E, F a C.
4. Pasada 2 empezando en A. En la transpuesta, A alcanza C, y C alcanza B, y B solo alcanza A, que ya está visitado. El árbol cubre A, C y B, así que la primera componente es {A, B, C}. Lo crucial es que la búsqueda no pudo escaparse hacia D ni hacia F, porque en la transpuesta esas aristas apuntan hacia dentro, no hacia fuera.
5. La pasada 2 continúa. El siguiente vértice no visitado en el orden es D. En la transpuesta D alcanza B, ya visitado, y E, que alcanza D, ya visitado. La componente es {D, E}. Por último F sigue sin visitar: en la transpuesta solo alcanza C, ya visitado, así que es la componente unitaria {F}.

Las componentes son {A, B, C}, luego {D, E}, luego {F}. Compáralo con Tarjan sobre el mismo grafo, que emite {F}, luego {D, E}, luego {A, B, C}. Ambos son correctos y ambos hallan las mismas tres componentes, pero Kosaraju las emite en orden topológico directo de la condensación mientras que Tarjan las emite en orden inverso. Si a tu código posterior le importa el orden, esa diferencia es la razón para elegir uno u otro.

Complejidad y de dónde sale

Tiempo: O(V + E) · Espacio: O(V + E)

Dos búsquedas en profundidad cuestan O(V + E) cada una, y construir el grafo transpuesto requiere una pasada sobre todas las aristas, también O(V + E). Sumando queda O(V + E) en total. El espacio es donde Kosaraju pierde de verdad frente a Tarjan: debe almacenar la estructura de adyacencia transpuesta, que es una segunda copia completa de la lista de aristas con O(V + E), mientras que Tarjan solo necesita O(V) de contabilidad sobre el grafo original. En un grafo con decenas de millones de aristas esa diferencia es el factor decisivo, y por eso Tarjan suele ganar en producción aunque los dos sean idénticos en tiempo asintótico.

Cuándo usar Algoritmo de Kosaraju (CFC) y cuándo no

Todos los algoritmos lineales de SCC cuestan O(V + E). Las diferencias están en memoria, número de pasadas y facilidad para escribir el código correctamente.

Errores frecuentes

• Usar el orden de finalización hacia adelante en lugar de invertido. La segunda pasada debe procesar los vértices en orden decreciente de tiempo de finalización. Ejecutarla en orden creciente arranca dentro de una componente sumidero y el DFS se derrama entre fronteras de componentes, fusionando SCC separadas. Este es el fallo que define a Kosaraju.
• Añadir al orden en el descubrimiento y no al terminar. El vértice debe apilarse cuando su recursión se completa, no cuando se alcanza por primera vez. El orden de descubrimiento no contiene ninguna de las propiedades de las que depende el algoritmo.
• Olvidar reiniciar el conjunto de visitados entre pasadas. Las dos búsquedas son independientes. Arrastrar las marcas de visitado de la primera pasada a la segunda hace que no se explore nada y todas las componentes salgan vacías.
• Transponer en el sitio. La segunda pasada necesita el grafo invertido mientras que el orden de finalización procede del original. Mutar las listas de adyacencia originales en lugar de construir una transpuesta aparte corrompe ambas cosas.
• Suponer que funciona en grafos no dirigidos. La conectividad fuerte es una noción dirigida. En un grafo no dirigido toda componente conexa es trivialmente fuertemente conexa, y un solo DFS o Union-Find responde a la pregunta mucho más barato.

Preguntas frecuentes

¿Cómo funciona el algoritmo de Kosaraju?

Ejecuta una búsqueda en profundidad sobre el grafo original y registra el orden en que terminan los vértices. Después invierte todas las aristas y ejecuta una segunda búsqueda en profundidad procesando los vértices en orden decreciente de finalización. Cada árbol que crece en la segunda pasada es exactamente una componente fuertemente conexa.

¿Por qué funciona invertir las aristas?

Invertir aristas preserva la conectividad fuerte, ya que un viaje de ida y vuelta entre dos vértices sigue existiendo cuando todas las aristas se dan la vuelta. Lo que sí cambia es la dirección entre componentes. Empezar por el vértice que terminó el último te sitúa en una componente fuente de la condensación, y tras la inversión sus enlaces salientes pasan a ser entrantes, de modo que la búsqueda queda atrapada dentro de la componente y no puede escaparse.

¿Cuál es la diferencia entre Kosaraju y Tarjan?

Ambos son O(V + E). Kosaraju usa dos pasadas de DFS más una copia transpuesta del grafo, así que necesita O(V + E) de espacio extra; Tarjan usa una pasada y O(V) de espacio extra. Kosaraju es más fácil de explicar e implementar, Tarjan es más rápido y ligero en la práctica. Además emiten las componentes en órdenes opuestos: Kosaraju en orden topológico directo de la condensación, Tarjan en inverso.

¿Cuál es la complejidad temporal del algoritmo de Kosaraju?

O(V + E) en tiempo, procedente de dos recorridos lineales más una pasada lineal para construir la transpuesta. El espacio es O(V + E) porque hay que almacenar el grafo transpuesto, que es la principal diferencia práctica con Tarjan.

¿Puede Kosaraju hallar componentes en un grafo no dirigido?

Funcionaría, pero no tiene sentido. En un grafo no dirigido toda componente conexa ya es fuertemente conexa, así que un solo DFS o una estructura Union-Find las encuentra en una sola pasada sin necesidad de construir una transpuesta.