Una ordenación topológica (topological sort, topological ordering, topsort o toposort en inglés) de un grafo acíclico dirigido G es una ordenación lineal de todos los nodos de G que satisface que si G contiene la arista dirigida uv entonces el nodo u aparece antes del nodo v. 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).
Los algoritmos usuales para el ordenamiento topológico tienen un tiempo de ejecución de la cantidad de nodos más la cantidad de aristas (O(|V|+|E|)).
Uno de los algoritmos, primero descrito por Kahn (1962), trabaja eligiendo los vértices del mismo orden como un eventual orden topológico. Primero, busca la lista de los "nodos iniciales" que no tienen arcos entrantes y los inserta en un conjunto S; donde al menos uno de esos nodos existe si el grafo es acíclico. Entonces:
L ← Lista vacía que contendrá luego los elementos ordenados.
S ← Conjunto de todos los nodos sin aristas entrantes.
MIENTRAS [S no es vacío]:
n ← nodo extraído de S
insertar n en L
PARA CADA [nodo m con arista e de n a m]:
Eliminar arista e del grafo
SI [m no tiene más aristas entrantes]:
insertar m en S
SI [el grafo tiene más aristas]:
error: el grafo tiene al menos un ciclo
SINO:
RETORNAR L
Si respeta la definición de GAD, ésta es una solución posible, listada en L (no es la única solución). De lo contrario el grafo contiene al menos un ciclo y por lo tanto un ordenamiento topológico es imposible.
Ha de tenerse en cuenta que, debido a la falta de unicidad del orden resultante, la estructura S puede ser simplemente un conjunto, una cola o una pila.
Dependiendo del orden que los nodos "n" son extraídos del conjunto S, hay una diferente posible solución.
Una alternativa al algoritmo visto para ordenamiento topológico está basado en DFS (del inglés búsqueda en profundidad). Para este algoritmo, las aristas están en dirección contraria al algoritmo anterior (y en dirección contraria a lo que muestra el diagrama del ejemplo). Hay un arco desde x a y si la tarea x depende de la tarea y (en otras palabras, si la tarea y debe completarse antes que la tarea x empiece). El algoritmo se repite a través de cada nodo del grafo, en un orden arbitrario, iniciando una búsqueda en profundidad que termina cuando llega a un nodo que ya ha sido visitado desde el comienzo del orden topológico.
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 vértice u ∈ V[G]do
estado[u] = NO_VISITADO
padre[u] = NULL
tiempo =0
for each vértice 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 .