Visitados
Na fila
Arestas verificadas

  • Atual
  • Na fila
  • Visitado
  • Caminho
Um clique num nó define

Mais sobre a pesquisa em largura

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

  1. Clique num nó para o tornar a origem. Para procurar um caminho, mude o clique para Destino e clique noutro nó.
  2. 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.
  3. 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