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
}