Busca em Largura (BFS)

Nesta lição, discutiremos um algoritmo de busca em grafos conhecido como Busca em largura (BFS).

O Algoritmo de busca em largura é uma busca que visitará os nossos vértices em camadas. Inicialmente, temos que definir um vértice como a fonte. O algoritmo visitará primeiro o vértice , depois visitará os vizinhos de , depois visitará os vizinhos dos vizinhos de , e assim por diante. Dizemos que está na camada , os vizinhos de estão na camada , os vizinhos dos vizinhos de estão na camada , e assim por diante.

Para implementar este algoritmo, utilizaremos uma fila (esta estrutura foi explicada em Estruturas de Dados Básicas) que nos ajudará a encontrar a ordem que precisamos processar os vértices. Para não processarmos um vértice mais do que uma vez, manteremos um vetor onde será igual a se e somente se nós já visitámos o -ésimo vértice. Inicialmente, colocaremos a nossa fonte na fila e faremos os seguintes passos enquanto a nossa fila não estiver vazia:

1. Pegue o primeiro vértice da fila
2. Retire da fila
3. Itere sobre os vizinhos de
4. Se ainda não tiver sido visitado, vamos defini-lo como visitado e adicioná-lo à nossa fila

O nosso algoritmo visitará todos os vértices que estão na mesma componente da nossa fonte e, supondo que esta componente tem vértices e arestas, ele rodará em porque visitaremos cada vértice exatamente uma vez e cada aresta duas vezes (uma para cada ponta).

Como qualquer algoritmo de busca em grafos, podemos contar o número dos componentes desse grafo. Veja o código abaixo para uma melhor compreensão de como fazer isto utilizando a BFS.

Para o implementar estaremos reutilizarando a classe Graph da aula de representação. A nossa classe Graph terá os seguintes métodos:

• add_edge: adiciona uma aresta ligando dois vértices;
• bfs: a função BFS executará o algoritmo BFS com uma dada fonte
• count_components: onde montamos o vetor visited e qtd_components. Depois passamos por todos os vértices, se um vértice não for visitado, visitamos todos os vértices que podemos alcançar a partir deste vértice e aumentamos o número de componentes em .