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 colasalió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
Paso
Sale
Contadores que bajan
Cola 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.