Busca em largura: explorar por camadas

Explorar o grafo em ondas

Imagine que você joga uma pedra num lago parado. As ondas se afastam do ponto de queda em círculos: primeiro o anel mais perto, depois o seguinte, depois um mais distante. A busca em largura explora um grafo exatamente assim. Ela parte de um vértice e, antes de ir para longe, visita todos os vizinhos que estão a um passo de distância. Só quando esse anel inteiro foi visto é que ela avança para os vértices a dois passos, depois a três, sempre completando uma camada antes de começar a próxima. Nada de mergulhar num caminho e esquecer o resto; a BFS é metódica e uniforme.

Para conseguir essa ordem tão certinha, a busca precisa de memória. A peça central é uma fila, aquela estrutura FIFO que você viu antes: o primeiro a entrar é o primeiro a sair. Quando a busca descobre novos vizinhos, ela os coloca no fim da fila; quando vai escolher o próximo a visitar, tira o da frente. Como os vizinhos mais próximos entram primeiro, também saem primeiro, e é isso que garante a exploração por camadas. Ao lado da fila, um conjunto de visitados anota quem já apareceu, para que nenhum vértice seja processado duas vezes.

A fila e os visitados em ação

Vale acompanhar o algoritmo passo a passo. No começo, você coloca o vértice inicial na fila e o marca como visitado. Depois entra num laço que repete enquanto a fila não estiver vazia: tira o vértice da frente, olha para cada vizinho dele e, para cada vizinho ainda não visitado, marca como visitado e coloca no fim da fila. Marcar no momento de enfileirar, e não no momento de visitar, é um detalhe que evita colocar o mesmo vértice duas vezes na fila. Quando a fila esvazia, todos os vértices alcançáveis foram vistos, cada um uma única vez.

fila <- [inicio]
visitados <- {inicio}   // conjunto
enquanto fila não está vazia faça
  atual <- tira da frente da fila
  escreva("visitando ", atual)
  para cada vizinho de atual faça
    se vizinho não está em visitados então
      adiciona vizinho em visitados
      coloca vizinho no fim da fila
    fim
  fim
fim

O esqueleto da BFS: fila para a ordem, conjunto para não repetir. Marca ao enfileirar, visita ao desenfileirar.

Por que a ordem por camadas importa

A grande vantagem de visitar camada por camada aparece quando você quer o caminho mais curto contado em passos. Como a BFS só chega à camada 2 depois de esgotar a camada 1, a primeira vez que ela toca um vértice é sempre pelo caminho com o menor número de arestas. Se você procura em quantos passos vai de uma pessoa a outra numa rede de amizades, ou o menor número de movimentos num labirinto, a BFS entrega isso de graça: a camada em que o vértice foi encontrado é a distância dele até o início. A busca em profundidade, que você verá na próxima aula, não dá essa garantia, porque ela mergulha fundo antes de olhar os vizinhos mais próximos.