Buscador SCC de Tarjan

Pseudocódigo

Un solo DFS, una pila y dos números por vértice. La idea clave es que toda componente fuertemente conexa tiene una raíz única: el vértice de la componente que se descubre primero.

conectarFuerte(u):
    desc[u] = low[u] = ++tiempo
    pila.meter(u); enPila[u] = verdadero

    para cada arista (u, v):
        si v no visitado:
            conectarFuerte(v)
            low[u] = min(low[u], low[v])
        si no, si enPila[v]:
            low[u] = min(low[u], desc[v])
        // si no: v está en una SCC ya cerrada, se ignora

    si low[u] == desc[u]:          // u es raíz de una SCC
        sacar de la pila hasta u incluido
        ese conjunto extraído es una SCC

La comprobación enPila es lo que separa a Tarjan de un esquema ingenuo de low-link. Una arista hacia un vértice visitado que ya pertenece a una componente cerrada no dice nada sobre tu propia componente y debe omitirse; incluirla fusionaría dos SCC genuinamente distintas. Fíjate además en la asimetría: una arista de árbol incorpora low[v], una arista de retroceso incorpora desc[v], y confundirlas es el otro fallo clásico.

Ejemplo resuelto, paso a paso

Ejecuta Tarjan sobre un grafo dirigido que contiene un ciclo de tres vértices, un ciclo de dos y un vértice que no pertenece a ninguno.

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. Descender por A, B, C. desc y low arrancan iguales: A recibe 1, B recibe 2, C recibe 3. Los tres están en la pila.
2. C a A es una arista de retroceso. A está visitado y sigue en la pila, así que low[C] = min(3, desc[A] = 1) = 1. Fíjate en que usa desc[A], no low[A].
3. C a F, y F sale solo. F recibe desc 4 y no tiene aristas salientes, así que low[F] se queda en 4. Como low[F] es igual a desc[F], F es raíz de una SCC y sale de la pila por sí solo como la componente {F}. Un vértice que no está en ningún ciclo siempre forma su propia SCC unitaria.
4. B a D a E, y E vuelve atrás. D recibe desc 5 y E recibe desc 6. La arista E a D encuentra a D en la pila, así que low[E] = min(6, desc[D] = 5) = 5. E no es raíz, ya que low[E] de 5 no es igual a desc[E] de 6, de modo que todavía no sale nada.
5. D es raíz. De vuelta en D, low[D] = min(5, low[E] = 5) = 5, que coincide con desc[D]. D es raíz de una SCC, así que la pila expulsa E y luego D, dando la componente {D, E}.
6. A es raíz. Al deshacer la recursión, low[B] = min(2, low[C] = 1, low[D] = 5) = 1 y low[A] = min(1, low[B] = 1) = 1, que coincide con desc[A]. La pila expulsa C, B y A, dando {A, B, C}.

Los low-link finales son A 1, B 1, C 1, F 4, D 5, E 5, y las componentes salen en el orden {F}, luego {D, E}, luego {A, B, C}. Hay dos cosas que merece la pena notar. Las componentes se emiten en orden topológico inverso de la condensación, y por eso Tarjan es el primer paso habitual para 2-SAT. Y F, alcanzable desde el ciclo pero sin camino de vuelta, forma correctamente su propia componente en lugar de quedar absorbido por {A, B, C}.

Complejidad y de dónde sale

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

Una única búsqueda en profundidad visita cada vértice una vez y examina cada arista dirigida exactamente una vez, lo que da O(V + E). Cada vértice se mete y se saca de la pila una sola vez, así que las operaciones de pila suman O(V) en toda la ejecución. El estado adicional es el tiempo de descubrimiento, el low-link y la marca de en pila por vértice, más la pila de recursión, todo O(V). Tarjan hace esto en una sola pasada, mientras que Kosaraju necesita dos recorridos completos más la construcción del grafo transpuesto, razón por la cual Tarjan suele preferirse en la práctica aunque ambos sean lineales.

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

Los tres algoritmos lineales de SCC tienen el mismo coste asintótico, así que la elección va de constantes, memoria y facilidad de implementar sin errores.

Errores frecuentes

• Usar low[v] en lugar de desc[v] en una arista de retroceso. Para una arista de árbol incorporas low[v]; para una arista de retroceso hacia un vértice que está en la pila incorporas desc[v]. Usar low[v] en las aristas de retroceso puede arrastrar un valor de otra componente y fusionar SCC que deberían quedar separadas. Los dos casos son genuinamente distintos.
• Omitir la comprobación de enPila. Una arista hacia un vértice visitado que ya se ha extraído a una SCC cerrada debe ignorarse por completo. Sin esa comprobación, los low-link se filtran entre componentes y la salida es incorrecta en cualquier grafo con aristas cruzadas.
• Olvidar limpiar enPila al extraer. Todo vértice extraído hacia una componente debe tener su marca borrada. Dejarla puesta hace que las comprobaciones posteriores de aristas de retroceso se disparen contra vértices que ya no están en la pila, corrompiendo en silencio las componentes siguientes.
• Recursar sobre grafos muy grandes. Tarjan es naturalmente recursivo y la profundidad es la longitud del camino más largo. En grafos con cientos de miles de vértices encadenados la pila de llamadas se desborda, y hace falta una reescritura con pila explícita. Es más delicada que para un DFS simple porque la actualización del low-link debe ocurrir después de que cada hijo retorne.
• Suponer un orden de componentes que no está ahí. Tarjan emite las componentes en orden topológico inverso de la condensación, no en ningún orden relacionado con las etiquetas de los vértices. Si necesitas el orden topológico directo, invierte la salida.

Preguntas frecuentes

¿Qué es una componente fuertemente conexa?

Una componente fuertemente conexa de un grafo dirigido es un conjunto máximo de vértices en el que cada vértice puede alcanzar a todos los demás siguiendo aristas dirigidas. Lo de máximo importa: no puedes añadir otro vértice y conservar la propiedad. Un vértice que no está en ningún ciclo dirigido forma una componente por sí solo.

¿Cómo funciona el algoritmo de Tarjan?

Ejecuta una única búsqueda en profundidad asignando a cada vértice un índice de descubrimiento y un valor low-link, el menor índice alcanzable desde su subárbol usando a lo sumo una arista de retroceso hacia un vértice que siga en la pila. Los vértices se apilan al visitarlos. Cuando un vértice termina con su low-link igual a su propio índice, es la raíz de una componente, y todo lo que hay por encima de él en la pila se extrae como esa componente.

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

Ambos hallan componentes fuertemente conexas en O(V + E). Tarjan usa un único DFS con contabilidad de low-link y una pila. Kosaraju usa dos pasadas de DFS, una sobre el grafo original para obtener tiempos de finalización y otra sobre el grafo transpuesto en orden decreciente de finalización. Kosaraju es más fácil de explicar; Tarjan es más rápido en la práctica porque evita construir la transpuesta y recorre el grafo una sola vez.

¿Cuál es la complejidad temporal de Tarjan SCC?

O(V + E) en tiempo y O(V) en espacio. Cada vértice se visita una vez, cada arista se examina una vez, y cada vértice entra y sale de la pila exactamente una vez. Es óptimo, ya que cualquier algoritmo debe leer el grafo entero.

¿Para qué sirven las componentes fuertemente conexas?

Para condensar un grafo dirigido en un DAG, que es el primer paso para resolver 2-SAT. También para el análisis de grafos de llamadas y la eliminación de código muerto en compiladores, la detección de interbloqueos, la búsqueda de dependencias mutuas en gestores de paquetes y hojas de cálculo, y la estructura de comunidades en redes sociales dirigidas.