Pesquisa em largura (BFS)
Explora um grafo camada a camada. Uma fila decide qual é o próximo vértice, por isso os vértices mais próximos são sempre visitados primeiro.
- tempo O(V + E)
- memória O(V)
- usa uma fila
O que significam estes termos?
- Vértice: um ponto do grafo, desenhado aqui como um círculo com uma letra.
- Aresta: uma linha que liga dois vértices. Aqui pode ser percorrida nos dois sentidos.
- Vizinhos: os vértices ligados a um vértice por uma aresta. São examinados por ordem alfabética.
- Fila: o primeiro a entrar é o primeiro a sair. A BFS tira sempre o vértice que está há mais tempo à espera.
- Pilha: o último a entrar é o primeiro a sair. A DFS continua sempre a partir do último vértice a que chegou.
- 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.
- na fila
- atual
- terminado
- aresta da árvore de pesquisa
- aresta ignorada
Começamos em A. Carregue em Reproduzir ou avance passo a passo.
Espaço: reproduzir ou pausar. Setas esquerda e direita: avançar passo a passo. Home e End: saltar.
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 põe o vértice inicial numa fila. Depois, uma e outra vez, tira o vértice da frente da fila e junta os vizinhos novos ao fim. Uma fila atende por ordem de chegada, por isso todos os vértices a uma aresta de distância ficam terminados antes de qualquer vértice a duas arestas. O número junto a um vértice é a distância ao início: o menor número de arestas para lá chegar.
Quando é uma boa escolha
Use a BFS quando precisar do caminho mais curto em passos: o menor número de jogadas num quebra-cabeças, de saltos numa rede, as pessoas a dois contactos de si. Num grafo grande, a fila pode ficar longa, porque guarda uma camada inteira de cada vez.