Busca em largura (BFS)
Explora um grafo camada por camada. Uma fila decide qual vértice vem depois, então os vértices mais próximos são sempre visitados primeiro.
- O(V + E)
- memória O(V)
- fila
V e E: o número de vértices e de arestas. O(V + E) significa que cada vértice e cada aresta são tratados um número fixo de vezes.
Fila: o primeiro a entrar é o primeiro a sair. A BFS sempre pega o vértice que está esperando há mais tempo.
Outros termos desta página
- Vértice: um ponto do grafo, desenhado aqui como um círculo com uma letra.
- Aresta: uma linha que liga dois vértices. Aqui dá para percorrê-la nos dois sentidos.
- Vizinhos: os vértices ligados a um vértice por uma aresta. São examinados em ordem alfabética.
Experimente: Escolha o grafo com duas partes. Os vértices que não estão ligados ao início nunca são alcançados.
Como funciona
A BFS coloca o vértice inicial em uma fila. Depois, repetidas vezes, pega o vértice da frente da fila e adiciona os vizinhos novos no fim. Uma fila atende por ordem de chegada, então todo vértice a uma aresta de distância fica pronto antes de qualquer vértice a duas arestas. O número ao lado de um vértice é sua distância até o início: o menor número de arestas para chegar a ele.
Quando é uma boa escolha
Use a BFS quando precisar do caminho mais curto em passos: o menor número de jogadas em um quebra-cabeça, de saltos em uma rede, as pessoas a dois contatos de você. Em um grafo grande, a fila pode ficar longa, porque guarda uma camada inteira de uma vez.