2 - Busca em Profundidade

No algoritmo DFS, percorre-se o grafo em termos de profundidade. Essa noção relaciona-se ao quão longe do vértice de origem o caminho vai parar dentro do grafo: a quantas arestas do vértice original o vértice atual do caminho se encontra? Se o caminho passa por uma aresta, a profundidade é de um. Se passa por três arestas, a profundidade é de três. O nome busca em profundidade advém de o algoritmo estar sempre tentando ir o mais “profundo” (distante) possível do vértice origem na sua busca pelo vértice destino. Também ocorre uma grande variação da profundidade ao longo da execução, uma vez que, ao não encontrar mais caminho para seguir em frente, o algoritmo retorna para o vértice anterior e tenta achar uma nova rota a partir dele, explorando vizinhos que ainda não foram visitados.

Calma, vou explicar um pouco melhor. No grafo do estado do RN, imagine que você quer fazer um caminho entre Santa Cruz e Pau dos Ferros. O vértice inicial da viagem é Santa Cruz, mas quem são os vizinhos dele?

Ora, os vizinhos são todos os vértices que têm uma aresta conectando com Santa Cruz, nesse caso, Natal, Mossoró e Caicó. Ao procurar um caminho para Pau dos Ferros, você poderia começar por qualquer um desses vizinhos. Então escolha Caicó, pra poder comer uma bolachinha na manteiga!

Em uma busca em profundidade, os outros vizinhos de Santa Cruz não serão explorados nesse momento: primeiramente serão explorados os vizinhos de Caicó, que estão em uma profundidade maior no caminho (em Santa Cruz você deu zero passos, em Caicó, já deu um passo). Faça isso sucessivamente (explore o vértice em dois, três, mil passos!) até chegar no destino. Depois que terminar de explorar, pode voltar para os vértices em níveis anteriores e continuar explorando outros caminhos e vizinhos que ainda não foram verificados. Captou a mensagem?

Observe o pseudocódigo do algoritmo abaixo (Código 01), talvez facilite um pouco a sua percepção de como isso ocorre:

Ainda não, né? Então veja as ilustrações abaixo! Os vértices verdes representam o ponto atual do caminho, os vértices em vermelho os pontos já visitados e os vértices amarelos são os próximos vizinhos não visitados que podem ser escolhidos. Os vértices em azul são pontos não visitados e que não são vizinhos do ponto atual.

Uma observação a fazer é que a escolha do próximo vértice a ser explorada foi aleatória, você poderia ter feito um percurso distinto seguindo as regras e estaria correto da mesma forma! Nesse ponto, foi traçado um caminho em que você parte de Santa Cruz e passa por Caicó e Mossoró antes de chegar em Pau dos Ferros. Se você quiser interromper o algoritmo porque encontrou um caminho, sem problemas! Ou você pode continuar “rodando” para ver se encontra outros caminhos até o vértice final (vai que tem um melhor!). Nesse caso, o algoritmo vai retornar ao vértice anterior (Mossoró) e colocar algum dos vizinhos ainda não explorados para tentar chegar a Pau dos Ferros novamente. Se no grafo não existirem mais caminhos, o algoritmo simplesmente termina.

Veja a sequência abaixo que mostra a execução do algoritmo no grafo voltando um nível (Mossoró).

Nesse ponto, foi encontrado um caminho que passa por todos os vértices:

Santa Cruz -> Caicó -> Mossoró -> Natal -> Pau dos Ferros

E o que acontece se você quiser voltar dois níveis de profundidade, quando Caicó era a bola da vez? Você não poderá ir novamente para Mossoró, porque é um caminho que já foi explorado. Confira nas figuras abaixo.

Dessa forma, o caminho encontrado foi Santa Cruz, Caicó e Pau dos Ferros, uma rota mais direta! Esse algoritmo é uma recursão simples, mas é muito útil para várias situações na área de jogos. Imagine que você quer fazer um jogo que gera mapas procedurais: fazer um algoritmo que gera os mapas de qualquer jeito não é difícil (pode ser tudo aleatório), mas garantir que o mapa é válido, e que todas as casas são navegáveis, aí a conversa é mais séria… Uma estratégia válida é gerar um mapa e usar uma DFS para varrer e verificar se todas as casas podem ser alcançadas pelo jogador, adaptando o caminho quando ele encontrar falhas. O uso de algoritmos recursivos para explorar todas as possibilidades é uma técnica denominada Backtracking.

Para não ficar apenas nos exemplos abstratos e visuais, veja um exemplo usando o grafo do RN, implementado em C# (Código 02).

A busca em profundidade é um recurso muito utilizado, e que se vale de uma implementação recursiva para manter o código simples e elegante. Mas ela não é o único tipo de busca que pode explorar os vértices do grafo! Existe uma segunda abordagem chamada de busca em largura!