Una componente fuertemente conexa reúne vértices de un grafo dirigido que pueden alcanzarse mutuamente. Dentro de ella siempre existe un camino de ida y otro de regreso.
En un grafo no dirigido, pertenecer a la misma componente conexa significa estar unidos por algún camino. En un grafo dirigido la situación es más exigente: llegar desde A hasta B no garantiza que podamos regresar desde B hasta A.
Las componentes fuertemente conexas permiten dividir un grafo dirigido en regiones de alcanzabilidad mutua. También se las conoce como SCC, por Strongly Connected Components.
Una componente fuertemente conexa es un conjunto maximal de vértices C en el que cada par u, v cumple:
La palabra maximal significa que no es posible agregar otro vértice al conjunto sin perder la propiedad. Aunque un solo vértice siempre se alcanza a sí mismo mediante un camino de longitud cero, si puede agruparse con otros debe pertenecer a la componente mayor.
Si tenemos A → B, B → C y C → A, los tres vértices forman una componente fuerte: podemos movernos entre cualquier par siguiendo la orientación de las aristas.
Si además existe C → D pero no hay ningún camino desde D de regreso a A, D no pertenece a esa componente.
Dos conceptos distintos pueden aplicarse a grafos dirigidos:
| Conectividad | Condición |
|---|---|
| Fuerte | Hay caminos dirigidos de ida y vuelta entre todos los vértices |
| Débil | El conjunto queda conectado si ignoramos la orientación de las aristas |
Toda componente fuerte está contenida en una componente débil, pero una componente débil puede contener varias componentes fuertes.
El grafo comienza con tres componentes fuertes conectadas en una sola dirección. Agrega la arista de retorno G → A y observa cómo todas se fusionan, porque aparece un camino de regreso a través de la cadena completa.
Componentes detectadas
Grafo condensado
Interpretación
Los colores representan las componentes calculadas por Tarjan. Las aristas blancas están dentro de una componente; las amarillas conectan componentes diferentes.
Una solución directa consiste en iniciar una búsqueda desde cada vértice y construir una matriz de alcanzabilidad. Dos vértices pertenecen a la misma SCC si cada uno alcanza al otro.
Este enfoque es correcto, pero repetir DFS o BFS desde todos los vértices puede costar O(V(V + E)). Kosaraju y Tarjan encuentran todas las componentes en tiempo lineal.
El grafo transpuesto Gᵀ se obtiene invirtiendo la dirección de todas las aristas.
Invertir todas las aristas no modifica las componentes fuertemente conexas: si dentro de un conjunto existían caminos de ida y vuelta, después de invertirlos continúan existiendo en sentidos intercambiados.
Kosaraju utiliza dos recorridos DFS:
El primer recorrido identifica por dónde conviene comenzar; el segundo evita atravesar prematuramente hacia otra componente.
function kosaraju(grafo) {
const vertices = Object.keys(grafo);
const visitados = new Set();
const orden = [];
function dfs1(v) {
visitados.add(v);
for (const w of grafo[v]) if (!visitados.has(w)) dfs1(w);
orden.push(v);
}
for (const v of vertices) if (!visitados.has(v)) dfs1(v);
const transpuesto = Object.fromEntries(vertices.map(v => [v, []]));
for (const v of vertices) {
for (const w of grafo[v]) transpuesto[w].push(v);
}
visitados.clear();
const componentes = [];
function dfs2(v, componente) {
visitados.add(v);
componente.push(v);
for (const w of transpuesto[v]) {
if (!visitados.has(w)) dfs2(w, componente);
}
}
while (orden.length) {
const v = orden.pop();
if (!visitados.has(v)) {
const componente = [];
dfs2(v, componente);
componentes.push(componente);
}
}
return componentes;
}Tarjan encuentra las SCC en un único recorrido DFS. A cada vértice le asigna:
Si al terminar un vértice se cumple low[v] === indice[v], v es la raíz de una componente. Se retiran elementos de la pila hasta incluirlo.
function tarjan(grafo) {
let siguienteIndice = 0;
const indice = {}, low = {}, pila = [], enPila = new Set();
const componentes = [];
function visitar(v) {
indice[v] = low[v] = siguienteIndice++;
pila.push(v);
enPila.add(v);
for (const w of grafo[v]) {
if (indice[w] === undefined) {
visitar(w);
low[v] = Math.min(low[v], low[w]);
} else if (enPila.has(w)) {
low[v] = Math.min(low[v], indice[w]);
}
}
if (low[v] === indice[v]) {
const componente = [];
let w;
do {
w = pila.pop();
enPila.delete(w);
componente.push(w);
} while (w !== v);
componentes.push(componente);
}
}
for (const v of Object.keys(grafo)) {
if (indice[v] === undefined) visitar(v);
}
return componentes;
}El índice nunca cambia después del descubrimiento. El valor low-link, en cambio, puede disminuir cuando DFS encuentra una ruta hacia un vértice anterior que todavía permanece en la pila.
Es importante actualizar con low[w] después de visitar un hijo, pero con indice[w] al encontrar una arista hacia un vértice que ya estaba en la pila.
El grafo condensado reemplaza cada componente fuerte por un único vértice. Se agrega una arista entre dos componentes si en el grafo original existe alguna arista que las conecte.
El resultado siempre es un DAG. Si tuviera un ciclo, las componentes de ese ciclo serían mutuamente alcanzables y deberían haberse agrupado en una sola.
| Característica | Kosaraju | Tarjan |
|---|---|---|
| Recorridos DFS | Dos | Uno |
| Grafo transpuesto | Necesario | No necesario |
| Estructuras clave | Orden de finalización | Índices, low-link y pila |
| Implementación | Suele ser más intuitiva | Más delicada, pero compacta |
| Complejidad | O(V + E) | O(V + E) |
Las componentes fuertemente conexas revelan la estructura interna de un grafo dirigido: separan las regiones con circulación completa de las conexiones que solo avanzan en una dirección. Kosaraju y Tarjan permiten encontrarlas eficientemente incluso en redes grandes.
En el próximo tema estudiaremos la clausura transitiva, que determina qué pares de vértices son alcanzables.