7.17. Ordenamiento topológico¶
Para demostrar que los científicos de la computación pueden convertir casi cualquier cosa en un problema de grafos, consideremos el difícil problema de batir un montón de panqueques. La receta es realmente muy simple: 1 huevo, 1 taza de mezcla de panqueques, 1 cucharada de aceite y \(3 \over 4\) de una taza de leche. Para hacer panqueques usted debe calentar la plancha, mezclar todos los ingredientes y derramar la mezcla sobre una plancha caliente. Cuando los panqueques empiecen a burbujear, déles vuelta y deje que se cocinen hasta que estén dorados en la parte de abajo. Antes de comer sus panqueques, usted querrá calentar un poco de jarabe dulce. La Figura 27 ilustra este proceso como un grafo.
Lo difícil al preparar panqueques es saber qué hacer primero. Como se puede ver en la Figura 27, usted puede empezar calentando la plancha o añadiendo cualquiera de los ingredientes a la mezcla de panqueques. Para ayudarnos a decidir el orden preciso en el que debemos hacer cada uno de los pasos requeridos para hacer nuestros panqueques recurriremos a un algoritmo de grafos llamado el ordenamiento topológico.
Un ordenamiento topológico toma un grafo acíclico dirigido y produce un ordenamiento lineal de todos sus vértices de tal manera que si el grafo \(G\) contiene una arista \((v,w)\) entonces el vértice \(v\) está, en el orden, antes del vértice \(w\). Los grafos acíclicos dirigidos se usan en muchas aplicaciones para indicar la precedencia de los eventos. Hacer panqueques es sólo un ejemplo; otros ejemplos incluyen planificaciones de proyectos de software, grafos de precedencia para optimizar las consultas de bases de datos y la multiplicación de matrices.
El ordenamiento topológico es una adaptación simple pero útil de una búsqueda en profundidad. El algoritmo para el ordenamiento topológico es el siguiente:
Llamar a
bep(g)para algún grafog. La principal razón por la que queremos invocar a la búsqueda en profundidad es para calcular los tiempos de finalización para cada uno de los vértices.Almacenar los vértices en una lista en orden decreciente según el tiempo de finalización.
Devolver la lista ordenada como resultado del ordenamiento topológico.
La Figura 28 muestra el bosque de profundidad construido por bep para el grafo de preparación de panqueques mostrado en la Figura 27.
Figura 28: Resultado de la búsqueda en profundidad para el grafo de preparación de panqueques¶
Figura 28: Resultado de la búsqueda en profundidad para el grafo de preparación de panqueques
Por último, la Figura 29 muestra los resultados de aplicar el algoritmo de ordenamiento topológico a nuestro grafo. Ahora se ha eliminado toda ambigüedad y sabemos exactamente el orden de los pasos para hacer panqueques.
Figura 29: Resultado del ordenamiento topológico aplicado a un grafo acíclico dirigido¶
Figura 29: Resultado del ordenamiento topológico aplicado a un grafo acíclico dirigido