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].
Entrada: un grafo dirigido en lista de adyacencia, con 7 vértices. Salida: los componentes fuertemente conexos, en el orden en que se cierran.
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.| Vértice | d | low | en_pila | Componente |
|---|
| Cierre | Lo cierra | Vértices, en el orden en que salen de la pila | Tamaño |
|---|
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.