Lo mismo de los ejercicios anteriores, sobre un grafo del tamaño de un problema real: catorce módulos de un proyecto con diecinueve dependencias, y la pregunta de en qué orden compilarlos. El algoritmo es el de la clase, sin cambiar una línea; lo que cambia es que ya no se puede seguir la traza de memoria.
Entrada: los catorce módulos y sus dependencias. Salida: un orden en que compilarlos donde cada módulo vaya después de todos los que necesita, o el aviso de que no existe.
Diecinueve dependencias. Una flecha de a a b quiere decir que a se compila antes que b.
| Paso | Sale | Contadores que bajan | Cola después |
|---|
Sobre las diecinueve dependencias, marque las parejas cuyo orden relativo no está fijado: las que un orden topológico puede poner en cualquiera de las dos formas.
app sale de último. ¿Por qué?Sin solución aquí. Con estas diecinueve
dependencias, ¿cuántos módulos se podrían compilar al mismo tiempo en
cada ronda, si en cada una se compilan todos los que ya tienen sus
dependencias listas? Cuente las rondas y diga cuál es la ronda más
cargada. Después: ¿qué le tendría que cambiar a kahn para
que, en vez de una lista, devuelva esas rondas?