← Volver a los ejercicios

Cuando la cola se vacía antes

El mismo algoritmo, sobre grafos que sí tienen ciclos. La cola se queda sin fuentes con vértices todavía adentro, y esos vértices son la respuesta a dos preguntas: si hay ciclo, y quién no puede salir nunca.

1. El grafo y la predicción

Entrada: un grafo dirigido en lista de adyacencia, que puede tener ciclos.  Salida: los vértices que el algoritmo alcanza a emitir, y con ellos la respuesta a si el grafo tiene un ciclo.

Grafo:
en la cola salió se quedó
¿Cuántos vértices alcanzan a salir antes de que la cola se vacíe?

2. Ejecute y mire qué contadores no bajan

Cola: vacía
Orden: [ ]
Paso 0 de 0
La línea 18 compara el largo del orden con n: esa comparación es toda la detección.

3. Una fila por vértice que sale

PasoSaleContadores que bajanCola después

4. Quién se queda por fuera

Cuando la cola se vacía antes de tiempo, ¿qué vértices quedaron sin salir?

5. La señal

¿Por qué len(orden) < n equivale a que el grafo tiene ciclos, en las dos direcciones?

6. Para llevarse

Sin solución aquí. Modifique kahn para que, además del orden, devuelva la lista de los vértices que quedaron por fuera, y con ella escriba una función que diga cuáles de esos vértices están en un ciclo y cuáles solo dependen de uno. Pruébela sobre el primer grafo: debe separar 1, 2, 3 de 4.