← Volver a los ejercicios

El orden topológico con la profundidad

Una búsqueda en profundidad pinta cada vértice de gris al entrar y de negro al salir, y cada vértice que se pinta de negro se agrega a orden. La lista sale por tiempo de finalización creciente; al invertirla queda el orden topológico. Si la búsqueda mira una flecha hacia un vértice gris, encontró un ciclo. Aquí se ejecutan las dos formas del código: la recursiva, donde lo pendiente vive en la pila de llamadas, y la de pila explícita, donde vive en una lista de pares.

1. El grafo y la predicción

Entrada: un grafo dirigido en lista de adyacencia.  Salida: la lista orden y el valor de ciclo[0].

Grafo:
Versión:

Sobre cada vértice, d/f: el punto es una f que todavía no se escribe. Blanco, gris y negro son los tres colores del código.

2. Ejecute la búsqueda

Pila de llamadas: vacía
orden (se llena por f creciente): [ ]
Paso 0 de 0
La flecha azul es la que se está mirando y se pone verde cuando el otro extremo está blanco y la búsqueda baja por ella. Una flecha roja llega a un vértice gris: es la que activa ciclo[0].

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

VérticedfColor
El reloj avanza al pintar de gris y al pintar de negro, así que los tiempos van de 1 a 2|V|. En la versión con pila los d y f pueden salir distintos de los de la recursiva: la pila visita los vecinos en el orden contrario al de la lista, y el resultado sigue siendo un orden válido.

4. Para llevarse

Sin solución aquí. En el grafo de los paquetes, ejecute las dos versiones y compare las tablas de d y f: diga qué vértice cambia de tiempos y por qué, y compruebe flecha por flecha que el orden de las dos sigue siendo válido. Después, en el de la receta, agregue la flecha servir → cebolla y diga, sin ejecutar, en qué momento la búsqueda llega a un vértice gris y cuál de las flechas del ciclo es la que la delata.