← Volver a los ejercicios

El algoritmo de Tarjan

Una sola búsqueda en profundidad numera los vértices con d, los apila al descubrirlos y calcula low, el menor d que alcanza cada uno. Cuando al terminar un vértice low[u] == d[u], u es la raíz de un componente y todo lo que quedó apilado encima de él, hasta u, sale junto con él. Se ejecutan las dos formas del código: la recursiva, que usa la pila de llamadas, y la que lleva su propia lista llamadas de pares [u, i].

1. El grafo y la predicción

Entrada: un grafo dirigido en lista de adyacencia, con 7 vértices.  Salida: los componentes fuertemente conexos, en el orden en que se cierran.

Grafo:
Versión:

Sobre cada vértice, d/low. Azul claro: en la pila. Amarillo: ya desapilado, componente por cerrar. Cada componente cerrado estrena color. Flecha ámbar: la que se mira; verde: baja a un vértice nuevo; azul: del árbol; morada: la que actualiza low.
¿Cuántos componentes fuertemente conexos tiene?

2. Ejecute el algoritmo

Pila de llamadas: vacía
pila de vértices (la cima es el último): [ ]
en_pila[v] es True para: ninguno
Paso 0 de 0
El reloj solo avanza al descubrir: d va de 1 a |V|. Las primeras líneas de en_blanco se ejecutan una vez por vértice; el algoritmo propiamente dicho empieza en la línea 22.

3. Los tres arreglos, vértice por vértice

Vérticedlowen_pilaComponente

4. Los componentes, en el orden en que se cierran

CierreLo cierraVértices, en el orden en que salen de la pilaTamaño

5. Para llevarse

Sin solución aquí. En el grafo de las páginas web, ejecute las dos versiones y compare las dos tablas de componentes. Después cambie la línea 32 de la recursiva para que use low[v] en vez de d[v] y compare los valores de low y los componentes que salen en los tres grafos. Por último, agregue la flecha ayuda → inicio y diga cuántos componentes quedan.