La búsqueda en profundidad anota dos instantes por vértice:
cuándo lo descubre y cuándo termina con él. El dibujo los muestra encima de
cada círculo mientras corre, y el vértice cambia de blanco a gris al entrar
y de gris a negro al salir. Al final, leer los f de mayor a
menor da la lista con la que arranca Kosaraju.
Entrada: un grafo dirigido en lista de
adyacencia. Salida: dos números por vértice, d[u]
y f[u], tomados de un reloj que avanza en uno cada vez que un
vértice se descubre y cada vez que uno termina.
| Vértice | d | f | Color |
|---|
f aparece
como un punto en el dibujo: todavía no se ha escrito.Sin solución aquí. En el primer grafo, escriba la
expresión de paréntesis del recorrido: un paréntesis que abre en cada
d y uno que cierra en cada f, con el nombre del
vértice al abrir. Verifique que queda bien formada y diga qué vértices son
descendientes del 0 en el bosque. Después agregue la flecha 6 → 0 y diga,
sin ejecutar, cuántos árboles quedan.