Laboratorio: Ordenamiento Topológico en DAGs
Simula el Algoritmo de Kahn (Iterativo Mejorado en $O(n+m)$) sobre la gráfica hexagonal canónica (Diapositiva 45 y clase de Ordenamiento Topológico).
Gráfica Dirigida (DAG de 7 nodos)
Orden Topológico Lineal (Lista L): Aristas apuntan de izquierda a derecha (i < j)
Grado > 0
En cola S (Grado = 0)
Procesado en L
Iniciando simulación...
Cola de Fuentes S (in-degree == 0):
Lista de Salida L (Orden Topológico construido):
|L| = 0 / 7
Vector dinámico de Grados de Entrada (in-degree):
Comparativa de Complejidad (Diapositivas 4, 5, 7, 8):
| Versión | Tiempo $T(n,m)$ | Espacio $S(n,m)$ | Estrategia |
|---|---|---|---|
| Iterativa ingenua | $O(n^2 + nm)$ | $O(n)$ | Escanea toda $G$ cada ronda |
| Iterativa mejorada (Kahn) | $O(n + m)$ | $O(n)$ | Cola $S$ + vector dinámico |