Busca em Profundidade

O conteúdo desta seção é baseado no capítulo referente a busca em profundidade do livro “Introduction to Algorithms - A Creative Approach”, escrito por Udi Manber.

MOTIVACAO E INTRODUCAO

Os algoritmos explicados nesta e nas próximas seções assumirão que o grafo de entrada é conectado e foi implementado usando listas de adjacência. Tomaremos como base a seguinte implementação, discutida nas seções anteriores:

IMPLEMENTACAO

Agora, tentaremos explicar de forma mais técnica o funcionamento da busca em profundidade. Ela começa a partir de um vértice arbitrário , que é chamado de raiz da busca (esse vértice é também algumas vezes chamado de vértice fonte). O vértice é marcado como visitado. A seguir, seleciona-se um vértice qualquer , dentre os vizinhos de que ainda não tenham sido marcados visitados, e uma nova DFS é iniciada recursivamente a partir dele. A recursão termina ao encontrar um vértice cujos vizinhos estejam todos marcados como visitados. Se após a DFS em terminar todos os outros vértices adjacentes a já tiverem sido marcados como visitados, a DFS em também termina. Caso contrário, seleciona-se um outro vértice arbitrário adjacente a e ainda não marcado como visitado. Uma nova DFS é iniciada em . Esse procedimento é repetido até que todos os vértices do grafo tenham sido marcados como visitados.

Vejamos como implementar esse algoritmo que acabamos de descrever. A princípio, assumiremos que o grafo é não-direcionado. Posteriormente, mostraremos uma implementação para grafos direcionados. As duas implementações são muito parecidas, mas tratar grafos direcionados e não-direcionados separadamente nos permitirá estudar algumas propriedades interessantes da busca em profundidade.

IMPLEMENTACAO DFS

Ordenação Topológica

Exemplos: O professor Donald Knuth apresenta um exemplo interessante de ordenação topológica. Nesse exemplo, imagine um grande glossário contendo definições de termos técnicos. O problema de ordenação topológica neste caso é encontrar uma forma de organizar as palavras no glossário de modo que nenhum termo seja usado antes de ser definido.

Exemplo Super-Homem.