- Atual
- Na fila
- Visitado
- Caminho
Pesquisa em largura (BFS)
A pesquisa em largura explora um grafo em anéis: primeiro cada nó junto à origem, depois cada nó a duas arestas, e assim por diante. Fá-lo com uma fila: o primeiro a entrar é o primeiro a sair. Clique num nó para começar a partir dele, escolha um destino se quiser, e avance passo a passo para ver a fila crescer e diminuir, cada nó receber a sua distância e surgir um caminho mais curto. Prima Reproduzir para ver a pesquisa, ou Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto. Clique num nó para o tornar a origem; mude o clique para Destino e clique noutro nó para procurar um caminho mais curto até ele. O número em cada nó é a sua distância à origem, e a linha por baixo do grafo é a fila. Novo grafo cria outro grafo; escolha quantos nós e arestas tem. Com o tabuleiro selecionado, as setas avançam e recuam um passo, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.
Como funciona
- Clique num nó para o tornar a origem. Para procurar um caminho, mude o clique para Destino e clique noutro nó.
- Prima Reproduzir, ou use Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto da pesquisa.
- Observe a fila por baixo do grafo e a distância em cada nó. Novo grafo cria outro grafo para experimentar.
Como funciona a pesquisa em largura
Coloque o nó de origem numa fila com distância 0. Depois repita: retire o nó da frente da fila e examine cada um dos seus vizinhos. Um vizinho que ainda não foi visto recebe uma distância uma unidade maior do que a do nó retirado, guarda esse nó como aquele por onde foi alcançado e entra no fim da fila. Os vizinhos já vistos são ignorados. Quando a fila fica vazia, cada nó alcançável tem a sua distância.
Porque encontra caminhos mais curtos
A fila entrega os nós pela ordem em que foram encontrados, e os nós são encontrados anel a anel: todos os nós à distância 1 entram na fila antes de qualquer nó à distância 2, e assim por diante. Por isso, a primeira vez que um nó é alcançado, é-o por um caminho com o menor número possível de arestas. Seguir os nós guardados do destino até à origem dá esse caminho. Isto só conta arestas; quando as arestas têm comprimentos diferentes, é preciso o algoritmo de Dijkstra.
Perguntas frequentes
O que é a pesquisa em largura?
Uma forma de explorar um grafo a partir de um nó de origem, visitando primeiro todos os seus vizinhos, depois os vizinhos destes, e assim por diante, anel a anel. Usa uma fila para manter os nós pela ordem em que foram encontrados.
A pesquisa em largura encontra o caminho mais curto?
Sim, quando todas as arestas contam o mesmo: a primeira vez que a BFS alcança um nó, usou o menor número possível de arestas. Para arestas com comprimentos diferentes, use antes o algoritmo de Dijkstra.
Qual é a diferença entre BFS e DFS?
A pesquisa em largura usa uma fila e espalha-se de forma uniforme, anel a anel. A pesquisa em profundidade usa uma pilha (ou recursão) e segue um caminho até ao fundo antes de voltar atrás. A BFS encontra caminhos mais curtos em arestas; a DFS não, mas é útil para encontrar ciclos e para a ordenação topológica.
Quão rápida é a pesquisa em largura?
Retira cada nó da fila uma vez e examina cada aresta a partir das duas pontas, por isso o trabalho cresce com o número de nós mais o número de arestas.
O meu grafo é enviado para algum lado?
Não. O grafo é criado e percorrido no seu navegador, e as suas últimas definições ficam no armazenamento local deste navegador.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Ir para o editor