Em geral

Uma ordem topológica (classificação topológica, ordenação topológica, topsort ou toposort em inglês) de um grafo acíclico direcionado G é uma ordenação linear de todos os nós de G que satisfaz que se G contém a aresta direcionada uv então o nó u aparece antes do nó v. A condição de que o grafo não contenha ciclos é importante, pois a ordenação topológica não pode ser obtida a partir de grafos que contenham ciclos.

Normalmente, para esclarecer o conceito, os nós são normalmente identificados com tarefas "Tarefa (computação)") a serem executadas nas quais há precedência na execução das referidas tarefas "Tarefa (computação)"). A ordenação topológica, portanto, é uma lista em ordem linear na qual as tarefas devem ser executadas.

Para encontrar a ordenação topológica do grafo G devemos aplicar uma modificação do algoritmo de busca em profundidade (DFS).

Os algoritmos usuais para ordenação topológica possuem um tempo de execução do número de nós mais o número de arestas (O(|V|+|E|)).

Um dos algoritmos, descrito pela primeira vez por Kahn (1962), funciona escolhendo vértices da mesma ordem como uma eventual ordem topológica. Primeiro, ele encontra a lista de “nós iniciais” que não possuem arcos de entrada e os insere em um conjunto S; onde pelo menos um desses nós existe se o gráfico for acíclico. Então:.

Se você respeitar a definição de TAG, esta é uma solução possível, listada em L (não a única solução). Caso contrário, o gráfico contém pelo menos um ciclo e, portanto, uma ordenação topológica é impossível.

Deve-se notar que, devido à falta de unicidade da ordem resultante, a estrutura S pode ser simplesmente um conjunto, uma fila ou uma pilha.

Dependendo da ordem em que os nós “n” são extraídos do conjunto S, existe uma solução diferente possível.

Uma alternativa ao algoritmo visto para ordenação topológica é baseada em DFS (pesquisa em profundidade). Para este algoritmo, as arestas estão na direção oposta ao algoritmo anterior (e na direção oposta ao que mostra o diagrama de exemplo). Existe um arco de x para y se a tarefa x depende da tarefa y (em outras palavras, se a tarefa y deve ser concluída antes do início da tarefa x). O algoritmo se repete em cada nó do grafo, em ordem arbitrária, iniciando uma busca em profundidade que termina quando atinge um nó que já foi visitado desde o início da ordem topológica.