Ordenación topológica
De Wikipedia, la enciclopedia libre
Una ordenación topológica de un grafo acíclico G dirigido es una ordenación lineal de todos los nodos de G que conserva la unión entre vértices del grafo G original. La condición que el grafo no contenga ciclos es importante, ya que no se puede obtener ordenación topológica de grafos que contengan ciclos.
Usualmente, para clarificar el concepto se suelen identificar los nodos con tareas a realizar en la que hay una precedencia a la hora de ejecutar dichas tareas. La ordenación topológica por tanto es una lista en orden lineal en que deben realizarse las tareas.
Para poder encontrar la ordenación topológica del grafo G deberemos aplicar una modificación del algoritmo de búsqueda en profundidad (DFS).
[editar] Pseudocódigo
- La ordenación topológica no es única. Depende en qué orden recorras los nodos del grafo en el bucle for de la función ORDENACIÓN_TOPOLÓGICA.
- La nomenclatura adicional utilizada es: lista = Estructura de datos lista enlazada
ORDENACIÓN_TOPOLÓGICA(grafo G)
for each vertice u ∈ V[G]do
estado[u] = NO_VISITADO
padre[u] = NULL
tiempo =0
for each vertice u ∈ V[G]do
if estado[u] = NO_VISITADO then
TOPOLÓGICO-Visitar(u)
TOPOLÓGICO-Visitar(nodo u)
estado[u]=VISITADO
tiempo = tiempo+1
distancia[u] = tiempo
for each v ∈ Adyacencia[u] do
if estado[v]=NO_VISITADO then
padre[v]=u
TOPOLÓGICO-Visitar(v)
estado[u] = TERMINADO
tiempo = tiempo+1
finalización[u] = tiempo
insertar (lista, u)
Al final de la ejecución del algoritmo se devuelve la lista enlazada de nodos, que corresponde con la ordenación topológica del grafo .
[editar] Ejemplo gráfico
- En rojo se muestran los siguientes tiempos: distancia[u] / finalización[u]
- Ejecutamos el algoritmo ORDENACIÓN_TOPOLÓGICA (grafo G) sobre el siguiente grafo.
2. El algoritmo nos devuelve una lista enlazada con los nodos del grafo en orden decreciente en tiempo de finalización.
Grafo ordenado topológicamente. En él se pueden ver claramente las precedencias de las tareas:
- Ponerse la camisa antes que el cinturón y el jersey
- Ponerse el pantalón antes que los zapatos y el cinturón
- Ponerse los calcetines antes que los zapatos
[editar] Referencias
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 22.3: Depth-first search, pp.540–549.
