ORDEN TOPOLÓGICO
Se puede dibujar un grafo de modo que todas las aristas apuntaran en general de izquierda a derecha, pero sólo para grafos dirigidos acíclicos, porque si el grafo tiene un ciclo, obviamente sería imposible hacerlo. Encontrar tal acomodo de los vértices, es el problema del ordenamiento topoiógico.

Sea G = (V, E) un grafo dirigido con n vértices. Un orden topoiógico para G es una asignación de enteros distintos 1,..., n a los vértices de V (sus números topológicos) tal que, cada arista vw pertenece a E, el número topoiógico de v; es menor que el número topoiógico de w. Un orden topológico inverso es similar, sólo que, para cada arista vw de E, el número topoiógico de v es mayor que el número topoiógico de w.

Un orden topológico equivale a una permutación de los vértices y es el problema fundamental de los grafos dirigidos acíclicos. Una vez encontrado el orden topológico para los vértices, muchos otros problemas se vuelven sencillos.

Los algoritmos de orden topológico y orden topológico inverso son simples modificaciones al algoritmo del recorrido primero en profundidad.

Orden topológico inverso.

Entrada: Las mismas que para el algoritmo de búsqueda primero en profundidad más un arreglo global ArrTop y un contador global numT.

Salida: El algoritmo llena el arreglo global con un conjunto de números topológicos inversos. Los tipos devueltos por este algoritmo se pueden cambiar a void.

Comentario: Para calcular el orden topológico "hacia adelante", se asigna a numT el valor inicial n+1 y se cuenta hacia atrás.

Estrategia: Se modifica el algoritmo de búsqueda primero en profundidad.

Nota: Recuerda que en una búsqueda en profundidad, no necesariamente se recorren todos los nodos a partir del vértice con el que se inició, si se desea recorrer todo el grafo, hará falta agregar un método que se encargue de esto, conocido comúnmente como "barrido de la búsqueda primero en profundidad" que consta de un ciclo sencillo que llame a la búsqueda primero en profundidad para todos los nodos.

Dentro de este método, para poder implementar el orden topológico, haría falta incluir la variable global numT inicializada en cero, la cual se incrementaría (numT++) dentro del método de la búsqueda en profundidad, de igual manera, ahí se asignaría dicho valor al vector en la posición del nodo (ArrTop[v] = numT), sólo hay que saber la parte adecuada del método en que dichas operaciones deben llevarse a cabo, por eso, debes implementarlo.

Al comparar el algoritmo de la búsqueda primero en profundidad con el algoritmo de orden topológico inverso, se puede ver que sus tiempos de terminacion en la búsqueda primero en profundidad produce el mismo ordenamiento que el algoritmo del orden topológico, y el último vértice que termina tiene el número más grande. Por lo tanto, por su conexión con el algoritmo de búsqueda primero en profundidad, decimos que el algoritmo del orden topológico inverso se ejecuta en tiempo Θ(n+m) con un grafo de n vértices y m aristas.