← Volver a los ejercicios

Cola, pila y la fuente menor

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.

1. El grafo

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.

2. ¿Cuál orden devuelve la versión con pila?

3. ¿Y la versión que saca siempre la fuente de número más bajo?

4. Ejecute las tres

Estructura:
Cola: vacía
Orden: [ ]
Paso 0 de 0
Las líneas 3, 7, 11 y 16 son las únicas que cambian entre versiones.
PasoFuentes disponiblesSale

5. ¿Cuáles de los tres órdenes son topológicos?

6. Para llevarse

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.