El algoritmo de Kahn guarda las fuentes disponibles en una cola. Cambiar la cola por una pila, o por una cola de prioridad que entrega siempre la fuente de número más bajo, produce otro orden. Aquí las tres versiones corren sobre el mismo grafo, que no está en las diapositivas, y antes de correrlas hay que decir cuál orden devuelve cada una.
Siete vértices y ocho flechas. Al arrancar hay dos fuentes, 2 y 6, y entran a la estructura en ese orden.
Entrada: este grafo. Salida: un orden topológico; cuál de todos depende de qué fuente se saca primero, y eso lo decide la estructura donde esperan las fuentes disponibles.
| Paso | Fuentes disponibles | Sale |
|---|
Sin solución aquí. La versión de la fuente menor usa una cola de prioridad y cuesta Θ((n + m) lg n). Diga qué costaría si en vez de la cola de prioridad se buscara la fuente menor recorriendo la lista de disponibles cada vez, y sobre qué grafos esa búsqueda sería tan cara como la versión ingenua de la clase.