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.
Entrada: un grafo dirigido en lista de
adyacencia. Salida: la lista orden y el valor de
ciclo[0].
ciclo[0].| Vértice | d | f | Color |
|---|
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.