Busca em Largura
Explora o grafo camada por camada — encontra o caminho mais curto em grafos não ponderados.
O(V+E)O(V+E)Como Funciona
Passo a passo do algoritmo
Inicialize a fila com o nó de partida
Adicione o nó inicial a uma fila (FIFO) e marque-o como descoberto. A fila controla a ordem em que os nós serão explorados.
fila = [início]; marcado = {início}Retire o primeiro nó da fila
Em cada iteração, retire o nó da frente da fila. Esse é o nó que será processado — todos os seus vizinhos ainda não visitados serão descobertos.
atual = fila.dequeue()Explore todos os vizinhos
Para cada vizinho do nó atual que ainda não foi descoberto, marque-o como descoberto e adicione-o ao final da fila.
para cada vizinho de atual: se não marcado → marcar e enfileirarRepita até a fila esvaziar
Continue retirando nós da fila e explorando seus vizinhos até que a fila esteja vazia. Nesse ponto, todos os nós alcançáveis foram visitados.
enquanto fila não vazia: repetirResultado: ordem por nível
A BFS garante que todos os nós a distância k do ponto de partida são visitados antes dos nós a distância k+1 — isso é o que garante "caminho mais curto".
nós visitados em ordem crescente de distânciaImplementação
Código comentado em JavaScript e Python
function buscaEmLargura(grafo, inicio) {
const visitados = new Set();
const fila = [inicio];
const ordem = [];
visitados.add(inicio);
while (fila.length > 0) {
const atual = fila.shift(); // FIFO — retira do início
ordem.push(atual);
for (const vizinho of grafo[atual]) {
if (!visitados.has(vizinho)) {
visitados.add(vizinho);
fila.push(vizinho); // adiciona ao final
}
}
}
return ordem;
}
// Exemplo de uso
const grafo = {
1: [2, 3],
2: [1, 4, 5],
3: [1, 6, 7],
4: [2],
5: [2, 6],
6: [3, 5, 7],
7: [3, 6]
};
console.log(buscaEmLargura(grafo, 1));
// [1, 2, 3, 4, 5, 6, 7]Playground
Visualize a busca em largura camada por camada
Quando Usar
Cenários ideais para este algoritmo
Caminho mais curto
A BFS encontra o caminho com menos arestas entre dois nós em grafos não ponderados — base de algoritmos de roteamento de rede.
Graus de separação
Redes sociais usam BFS para encontrar o menor número de conexões entre duas pessoas (o famoso "6 graus de separação").
Rastreamento web
Crawlers de motores de busca usam BFS para descobrir páginas web seguindo links camada por camada a partir de uma URL inicial.
GPS e mapas
Encontrar o menor número de ruas entre dois pontos, identificar cidades a N horas de distância, ou encontrar restaurantes próximos.
Complexidade
Análise de desempenho por cenário
| Cenário | Tempo |
|---|---|
| Melhor caso | O(V+E) |
| Caso médio | O(V+E) |
| Pior caso | O(V+E) |