3 - Busca em Largura

Retome o exemplo da viagem de Santa Cruz para Pau dos Ferros, agora para entender o outro tipo de busca.

Na busca em largura, ou BFS, a ideia é que você explore todos os vizinhos do vértice em uma mesma profundidade antes de verificar os próximos vértices. No fim das contas você vai realizar os mesmos processamentos, só que em uma ordem diferente! Essa busca é mais sistemática e explora primeiro os vértices que estão mais próximos da origem, dirigindo-se gradativamente aos vértices mais distantes. É a ideia oposta da busca em profundidade: ao invés de tentar achar logo um caminho, ele vai verificando todos os caminhos do grafo até encontrar um que seja o destino desejado.

Para implementar essa ideia, parta para uma abordagem iterativa, utilizando uma Fila (lembra da Aula 03? A mesminha! ). Você vai pegar seu vértice de origem, Santa Cruz, e vai sair adicionando todos os vizinhos dele: Mossoró, Natal e Caicó. Todos esses vértices serão colocados em uma fila para serem processados. Após isso, o primeiro que foi colocado na fila torna-se o atual, e os seus vizinhos que ainda não estão na fila serão então inseridos no final. Perceba que esses novos vizinhos só serão processados quando todos os três vizinhos de Santa Cruz forem avaliados.

Dessa forma, você vai fazendo uma varredura do grafo pelos níveis de vértices que estão mais próximos do ponto de origem, e os nós mais distantes serão atingidos no final do algoritmo. Essa abordagem é boa para momentos em que você quer encontrar o primeiro caminho possível com o menor número de percursos no grafo (isso faz mais sentido quando o grafo não tem peso, em que o número de arestas do caminho seria equivalente ao seu custo!). O pseudocódigo desse algoritmo é ilustrado pelas linhas do Código 03 abaixo:

Hum… ainda está confuso, hein? Já sei, já sei, você quer as imagens... No caso da busca em largura, os vértices em amarelo vão representar os vértices inseridos na fila de avaliação pelo algoritmo, enquanto os outros mantêm o mesmo significado do que foi anteriormente visto no algoritmo DFS.

Como você pôde observar na Figura 16, o caminho final dessa iteração foi chegar a Pau dos Ferros através de Caicó, vértice a partir do qual Pau dos Ferros foi inserido na fila. Da mesma forma que o algoritmo anterior, vou colocar um exemplo de implementação utilizando a linguagem C# (Código 04). Esse exemplo busca o primeiro caminho possível de um ponto inicial até um ponto final.

E com isso você já fica com duas ferramentas poderosas para trabalhar. Apesar de suas aplicações na área de jogos, esses algoritmos não se limitam apenas a esse campo, podendo ser encontrados na resolução de diversos problemas na área de redes, circuitos, otimização de algoritmos, engenharia de software e vários outros campos da computação! Então é muito importante entender a ideia de funcionamento e brincar com a implementação desses algoritmos para aumentar o seu arsenal como programador.

Perceba uma coisa: com esses algoritmos você consegue verificar se existe um caminho de A até B, e até achar todos os caminhos que existem entre os dois! Mas eles não são direcionados para achar o menor caminho: aquele que te leva com o menor custo possível de um ponto a outro - a principal problemática que foi discutida no início das aulas de “Descoberta de caminhos”!

Não se desespere! Mature um pouco o conteúdo dessa aula, que na próxima você terá o gran finale! Conhecerá dois algoritmos voltados para essas tarefas: o algoritmo de Djikstra e o algoritmo A*!

Não consegue conter a emoção, hein? Clique aqui para ver o próximo episódio.

Até lá!