El algoritmo de Kahn sobre grafos que no están en las
diapositivas. Cada vértice lleva su contador de entrada dibujado encima; se
ve bajar cuando sale un predecesor y ponerse en verde cuando llega a cero,
que es el instante en que el vértice entra a la cola. El primer grafo es el
más sencillo, con una sola fuente y sin nada que escoger; los otros dos
agregan una fuente de más y un vértice suelto.
1. El grafo y la predicción
Entrada: un grafo dirigido sin ciclos en
lista de adyacencia. Salida: un orden topológico: cada
vértice después de todos los que le apuntan.
Grafo:
en la colasaliendoya en el orden
¿Cuántos vértices entran a la cola antes de que salga el primero?
2. Ejecute y mire los contadores
Cola: vacía
Orden: [ ]
Paso 0 de 0
Compare el contador de la línea 16 con el de la línea 14: no todas las restas meten a alguien en la cola.
3. Una fila por vértice que sale
Paso
Sale
Contadores que bajan
Cola después
4. Cuándo se entra a la cola
Un vértice con dos flechas llegando, ¿en qué momento entra a la cola?
5. Por qué el orden que sale sirve
¿Qué garantiza que ningún vértice salga antes que uno que le apunta?
6. Para llevarse
Sin solución aquí. En el primer grafo, invierta la
numeración de los vértices (el 0 pasa a ser el 7, el 1 el 6, y así) sin
tocar las flechas. Ejecute el algoritmo a mano y diga qué cambió en el
orden de salida y qué no cambió. Después diga, sin ejecutar, cuántos
vértices entrarían a la cola al arrancar.