Achar o menor caminho com busca em largura

Explorar por camadas

Imagine jogar uma pedra na origem e ver as ondas se espalharem. A primeira onda toca os vizinhos diretos, a onda seguinte toca os vizinhos deles, e cada onda está sempre a um passo além da anterior. A busca em largura é essa onda. Ela visita a origem, depois todos que estão a um passo, depois todos que estão a dois passos, sem pular ninguém. Por avançar de forma tão organizada, quando a onda finalmente toca o destino, ela chegou pelo caminho mais curto em passos. É por isso que a busca em largura é a ferramenta certa para o Mapa de Rotas: queremos a rota com menos trechos, e a busca em largura entrega exatamente isso.

Duas estruturas fazem a onda funcionar. A fila controla a ordem de visita: quem é descoberto primeiro é visitado primeiro, o que mantém a exploração camada por camada. O conjunto de visitados guarda quem a busca já alcançou, para não voltar a lugares já vistos. Sem ele, num grafo com ciclos (e o metrô tem vários), a busca daria voltas eternas, visitando Centro, Norte, Centro, Norte, para sempre. Juntas, a fila e o conjunto de visitados são o coração da busca em largura.

A lógica, passo a passo

O algoritmo é um laço curto que repete quatro ideias. Começa colocando a origem na fila e marcando a origem como visitada. Enquanto a fila tiver alguém, tira o próximo da frente da fila (esse é o vértice atual), olha cada vizinho dele e, para todo vizinho ainda não visitado, marca como visitado e coloca na fila. A busca termina quando a fila esvazia (visitou tudo que dava para alcançar) ou quando o atual é o destino (achou). Repare que marcar o vizinho como visitado acontece no momento em que ele entra na fila, não quando sai. Marcar cedo é o que impede o mesmo ponto de entrar na fila várias vezes.

funcao busca_largura(grafo, origem, destino)
  fila <- [origem]
  visitados <- {origem}
  enquanto fila nao vazia faca
    atual <- desenfileirar(fila)   // tira da frente
    se atual = destino entao
      retorne "achou o destino"
    para cada vizinho de grafo[atual] faca
      se vizinho nao esta em visitados entao
        adicionar(visitados, vizinho)
        enfileirar(fila, vizinho)   // poe no fim
      fim
    fim
  fim
  retorne "sem caminho"
fim

A fila dá a ordem de visita; o conjunto de visitados garante que cada vértice entra uma vez só.

Por que ela dá o menor caminho

A garantia do menor caminho vem da disciplina da fila. Como a busca sempre tira da fila quem entrou primeiro, ela esgota toda a camada de distância um antes de tocar em qualquer ponto de distância dois, e assim por diante. Logo, a primeira vez que um vértice é alcançado é sempre pela rota mais curta em passos, porque uma rota mais longa chegaria numa camada posterior, quando o ponto já estaria marcado como visitado e seria ignorado. Vale lembrar o limite: a busca em largura conta passos, não distância física nem tempo. Se cada trecho tivesse um peso diferente (uns longos, outros curtos), o menor caminho em quilômetros exigiria outro algoritmo. Para contar trechos, baldeações ou apertos de mão, a busca em largura é exata.