Pular para o conteúdo
</> Entendendo Algoritmos

Busca em largura

Em um grafo, a busca em largura usa uma fila para verificar primeiro os vizinhos diretos, depois os vizinhos dos vizinhos, e assim por diante. Assim encontra o caminho com menos arestas. Custo: O(V + E).

Explicação do algoritmo: escolha um nível para ler.

{ }Ver o código
function buscaEmLargura(grafo, inicio, alvo) {
  const fila = [inicio];
  const verificados = [];
  const pai = { [inicio]: null };   // quem descobriu cada nó

  while (fila.length > 0) {
    const atual = fila.shift();                   // primeiro a entrar, primeiro a sair
    if (verificados.includes(atual)) continue;    // já verificado: ignora
    verificados.push(atual);

    if (atual === alvo) {
      const caminho = [];
      for (let no = atual; no !== null; no = pai[no]) caminho.unshift(no);
      return caminho;                             // caminho com menos arestas
    }

    for (const vizinho of grafo[atual] ?? []) {
      fila.push(vizinho);
      if (!(vizinho in pai)) pai[vizinho] = atual;
    }
  }

  return null;   // não existe caminho
}