← Volver a los ejercicios

La cola de fuentes

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 cola saliendo ya 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

PasoSaleContadores que bajanCola 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.