← Volver a los ejercicios

Los dos relojes y el orden por finalización

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.

1. El grafo y la predicción

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.

Grafo:
blanco, sin descubrir gris, en la pila de llamadas negro, terminado
¿Cuántos árboles tendrá el bosque de profundidad?
Es lo mismo que preguntar cuántas veces se ejecuta la línea 14.

2. Ejecute y mire el reloj

Raíces: ninguna todavía
Terminados, en orden: [ ]
Por f decreciente: (falta terminar)
Paso 0 de 0
La flecha azul es la que está mirando la línea 7; se pone verde cuando el vértice del otro extremo está blanco y la línea 8 baja por ella.

3. Los dos tiempos, vértice por vértice

VérticedfColor
Mientras un vértice esté gris su f aparece como un punto en el dibujo: todavía no se ha escrito.

4. Cuál termina de último

¿Qué vértice tiene el f más grande?

5. De dónde sale la lista que usa Kosaraju

El primer paso de Kosaraju pide los vértices ordenados. ¿Ordenados por qué?

6. Para llevarse

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.