A primeira aplicação da busca em profundidade que veremos é para encontrar uma ordenação topológica num grafo dirigido acíclico (DAG ou Directed Acyclic Graph)

Para tanto, primeiro precisamos entender o que é um DAG e o que é uma ordenação topológica

 - Uma ordenação topológica é uma ordem/rotulação f dos vértices de um grafo de modo que:
 
    - União_{v \in V} {f(v)} = {1, ..., n}
 
    - Para qualquer arco (u, v) temos f(u) < f(v)

 - A motivação para este problema é encontrar uma ordem possível para realizar um sequência de tarefas de modo a respeitar as restrições de precedência entre estas tarefas.



 - Um DAG é um grafo orientado que não possui ciclos



Uma relação interessante (e importante para nossa aplicação) é que:

 - um grafo orientado é acíclico se e somente se possui uma ordenação topológica
 
(<--) primeiro vamos mostrar a volta através da contrapositiva
 
 - a contrapositiva de: a --> b é

    - ~b --> ~a
 
 - portanto, a contra-positiva de: o grafo orientado possuir uma ordenação topológica --> o grafo ser acíclico é 
 
    - o grafo orientado ter um ciclo --> o grafo não possui uma ordenação topológica

 - no caso em que o grafo orientado possui um ciclo, vamos supor por contradição que temos uma ordenação topológica f válida. Nesta ordenação algum vértice v do ciclo tem o menor rótulo, mas como trata-se de um ciclo, existe um outro vértice w do ciclo que tem uma aresta (w, v) incidindo em v. Pela escolha de v, sabemos que o rótulo de v é menor que o rótulo de w, ou seja, f(v) < f(w). Mas, para ser uma ordenação topológica válida, como existe a aresta (w, v), deveríamos ter f(w) < f(v). Chegamos a um absurdo.
 
(-->) para provar a ida vamos fazer uma prova construtiva

 - já que o grafo é acíclico, vamos seguir um caminho neste grafo. Eventualmente (depois de no máximo n-1 arcos) esse caminho tem que acabar, caso contrário teríamos que repetir algum vértice o que resultaria em um ciclo. Note que o último vértice deste caminho não pode ter arcos saindo dele, caso contrário o caminho não teria acabado (se os arcos fossem para novos vértices) ou teríamos um ciclo (se os arcos fossem para vértices já visitados). Chamamos vértices sem arcos de saída de vértices sorvedouros (ou do inglês, sinks). Notem ainda que é seguro colocar este vértice como o último vértice da nossa ordenação topológica, ou seja, colocar o rótulo n nele. Feito isso, podemos removê-lo do grafo e recomeçar o processo. Já que ao remover um vértice sorvedouro (e os arcos que incidiam nele) nós não criamos ciclos, o grafo resultante continua acíclico. Repetindo o mesmo raciocínio para encontrar um sorvedouro no vértice restante (ou mais formalmente usando indução matemática) temos a demonstração do resultado. Além disso, temos uma ideia para um algoritmo para este problema.



Uma maneira bastante eficiente de implementar essa ideia de "remover" um sorvedouro por vez é usando busca em profundidade com um laço externo sobre os vértices e um contador decrescente, como mostra o seguinte algoritmo

LoopBuscaProf(grafo G=(V,E)) {
	maque todos os vértices em V como não encontrados // esta marcação é preservada ao longo de todas as invocações da função buscaProfRec
	
	rotulo-atual = n // para simplificar o pseudo-código essa variável é global. Numa implementação ela seria passada por referência (apontador) ao longo das chamadas de função
	
	para cada v \in V
		se v não foi encontrado
			buscaProfRec(G, v)
}



buscaProfRec(grafo G=(V,E), vértice v) {
	
	marque v como encontrado
	
	para cada aresta (v, w)
		se w não foi encontrado
			buscaProfRec(grafo G=(V,E), vértice w)
	
	defina f(v) = rotulo-atual // os rótulos f() também são globais por simplicidade
	rotulo-atual--
}



A eficiência desse algoritmo é O(n + m)

Para verificar que ele obtem uma ordenação topológica correta, vamos considerar um arco (u, v). Nesta caso, queremos f(u) < f(v). Temos dois casos:

 - (i) se u for encontrado antes de v. Como a busca em profundidade não volta até encontrar tudo que for possível, ela vai encontrar e rotular v antes de voltar e rotular u. Como os rótulos só decrescem, teremos f(u) < f(v).
 
 - (ii) se v for encontrado antes de u. Sabemos que não existe caminho de v para u, caso contrário junto da aresta (u, v) teríamos um ciclo. Portanto, v será rotulado antes de u ser encontrado. Eventualmente, em outra chamada do laço externo o vértice u será encontrado e rotulado. Novamente, como os rótulos só decrescem, teremos f(u) < f(v).