BFS — Algoritmo de Busca em Largura Explicado

A busca em largura, ou BFS, é um algoritmo de grafos que visita os nós na ordem da distância em relação a um nó inicial. Ele verifica todos os nós que estão a uma aresta de distância antes de passar para os nós que estão a duas arestas, depois três arestas, e assim por diante.

Essa ordem por camadas é a ideia principal. Se o grafo for não ponderado, ou se toda aresta tiver o mesmo custo, o BFS também fornece o comprimento do caminho mínimo do nó inicial até cada nó alcançável.

O Que a Busca em Largura Faz

O BFS usa uma fila, que é uma lista do tipo primeiro a entrar, primeiro a sair. É a fila que preserva a ordem por camadas: nós descobertos antes são processados antes.

O padrão usual é:

• marcar o nó inicial como visitado
• colocá-lo na fila
• remover o nó da frente
• adicionar cada vizinho não visitado ao fim da fila
• repetir até que a fila esteja vazia

Se você também armazenar o pai de cada nó, poderá reconstruir um dos caminhos mínimos depois que a busca terminar.

Por Que a Fila Cria Camadas

Suponha que o nó $A$ seja o inicial. Seus vizinhos diretos estão a distância $1$ de $A$, então entram primeiro na fila. Só depois que esses nós são processados é que seus vizinhos ainda não visitados entram, o que significa que a próxima onda está a distância $2$.

É por isso que o BFS naturalmente agrupa os nós pela distância em relação ao início. Ele não está estimando qual caminho é curto. A fila força a busca a terminar todos os caminhos com menos arestas antes de considerar os mais longos.

Exemplo de BFS: Encontrando o Caminho Mínimo pelo Número de Arestas

Use este grafo:

$$A \to \{B, C\}, \qquad B \to \{D\}, \qquad C \to \{E\}, \qquad D \to \{F\}, \qquad E \to \{F\}$$

Comece em $A$. A fila muda assim:

$$[A] \to [B, C] \to [C, D] \to [D, E] \to [E, F] \to [F]$$

Veja o que isso significa:

Primeiro, processe $A$ e depois adicione $B$ e $C$. Em seguida, processe $B$ e depois $C$, o que adiciona $D$ e $E$. Depois disso, processe $D$ e $E$, o que alcança $F$.

Então, a ordem de visita do BFS é:

$$A,\ B,\ C,\ D,\ E,\ F$$

As distâncias a partir de $A$ são:

$$\operatorname{dist}(A)=0,\quad \operatorname{dist}(B)=1,\quad \operatorname{dist}(C)=1,\quad \operatorname{dist}(D)=2,\quad \operatorname{dist}(E)=2,\quad \operatorname{dist}(F)=3$$

Isso mostra o principal benefício. O BFS alcança $F$ com distância $3$, então o caminho mínimo de $A$ até $F$ usa $3$ arestas. Um caminho mínimo é $A \to B \to D \to F$. Outro é $A \to C \to E \to F$.

Erros Comuns em BFS

Supor Que o BFS Sempre Encontra o Caminho Mais Barato

Isso só é verdade quando toda aresta tem o mesmo custo, ou quando o grafo é tratado como não ponderado. Se as arestas tiverem pesos diferentes, o BFS pode encontrar um caminho com menos arestas, mas com custo total maior.

Marcar um Nó Tarde Demais

No BFS padrão, um nó normalmente é marcado como visitado quando ele entra na fila, e não quando é removido depois. Isso evita que o mesmo nó seja adicionado à fila muitas vezes.

Confundir BFS com DFS

O BFS explora por camadas. A busca em profundidade, ou DFS, continua seguindo um ramo antes de voltar. Eles respondem bem a tipos diferentes de perguntas.

Esquecer Que a Ordem Pode Depender da Ordem dos Vizinhos

A ordem exata de visita dentro da mesma camada pode mudar dependendo de como os vizinhos são listados. As garantias de distância continuam valendo, mas a ordem de percurso pode ser diferente.

Quando a Busca em Largura É Usada

O BFS é útil quando você se importa com alcançabilidade, percurso em nível em árvores ou comprimentos de caminhos mínimos medidos pelo número de arestas.

Ele também aparece em problemas de espaço de estados em que cada movimento tem o mesmo custo. Nessa condição, o BFS costuma ser a forma mais clara de encontrar o número mínimo de movimentos.

Uma Forma Simples de Lembrar do BFS

Pense no BFS como uma ondulação se espalhando para fora a partir do nó inicial. Cada passo da ondulação acrescenta mais uma aresta de distância.

Para testar sua própria versão, desenhe um grafo pequeno, escolha um nó inicial e escreva a fila após cada passo. Se quiser ir além, resolva um problema semelhante de percurso em grafos e verifique se a afirmação sobre caminho mínimo ainda vale quando o grafo é ponderado.