Pesquisa em largura (BFS)

Atire uma pedra a um lago e as ondas espalham-se em anéis regulares. A pesquisa em largura explora um grafo da mesma forma: primeiro tudo o que está a um passo da origem, depois tudo o que está a dois passos, e assim por diante. É esta ordem simples que a faz encontrar caminhos mais curtos.

Um grafo de nós com letras, colorido em anéis segundo a distância ao nó de origem, com uma fila de nós desenhada por baixo
Um grafo de nós com letras, colorido em anéis segundo a distância ao nó de origem, com uma fila de nós desenhada por baixo

A ideia

Um grafo é um conjunto de nós ligados por arestas: locais e estradas, pessoas e amizades, casas de um labirinto e as passagens entre elas. A pesquisa em largura responde à pergunta: a partir daqui, o que consigo alcançar, e em quantos passos no mínimo? Mantém uma fila dos nós ainda por visitar. Como retira os nós da frente e junta os novos ao fim, os nós são tratados pela ordem em que foram descobertos.

Passo a passo

Coloque a origem na fila à distância 0. Retire o nó da frente. Para cada vizinho que ainda não foi visto, registe como distância a do nó atual mais um, guarde o nó atual como aquele por onde foi alcançado e junte-o ao fim da fila. Ignore os vizinhos já vistos. Repita até a fila ficar vazia ou até alcançar o destino.

Um exemplo

Considere um grafo com as arestas A–B, A–C, B–D, C–D, C–E e D–F, e comece em A. Ao retirar A da fila, encontram-se B e C à distância 1. Ao retirar B, encontra-se D à distância 2. Ao retirar C, vê-se que D já tinha sido visto, e encontra-se E à distância 2. Ao retirar D, encontra-se F à distância 3. E e F não trazem nada de novo, e a fila fica vazia. Seguir os nós guardados a partir de F dá F ← D ← B ← A, por isso um caminho mais curto de A a F é A → B → D → F, com três arestas.

Porque as distâncias estão certas

Cada nó à distância 1 entra na fila antes de qualquer nó à distância 2, cada nó à distância 2 antes de qualquer nó à distância 3, e assim por diante, porque os vizinhos de um nó só entram na fila quando o próprio nó sai dela. Por isso, o primeiro caminho que alcança um nó é um com o menor número de arestas, e a BFS nunca precisa de corrigir uma distância. Cada nó é retirado uma vez e cada aresta examinada a partir das duas pontas, por isso o trabalho cresce com o número de nós mais o número de arestas.

História e aplicações

Konrad Zuse descreveu a pesquisa em largura em 1945, num trabalho sobre a sua linguagem Plankalkül que só foi publicado em 1972. Edward F. Moore reinventou-a em 1959 para encontrar o caminho mais curto para sair de um labirinto, e C. Y. Lee usou-a em 1961 para traçar pistas em placas de circuito. Hoje encontra o menor número de jogadas em quebra-cabeças, os graus de separação nas redes sociais, as páginas que um rastreador web alcança primeiro e a casa livre mais próxima nos jogos. Quando as arestas têm comprimentos, o algoritmo de Dijkstra generaliza-a.

Konrad Zuse (ao centro, de óculos) e Heinz Billing (à esquerda) na feira SYSTEMS ’91 em Munique. Zuse descreveu a pesquisa em largura em 1945, em trabalhos sobre a sua linguagem Plankalkül só publicados em 1972.
Konrad Zuse (ao centro, de óculos) e Heinz Billing (à esquerda) na feira SYSTEMS ’91 em Munique. Zuse descreveu a pesquisa em largura em 1945, em trabalhos sobre a sua linguagem Plankalkül só publicados em 1972.

Explore-a

Abra a aplicação e prima Avançar. O nó a ser visitado fica destacado, os nós à espera na fila ficam azuis e os nós visitados ficam verdes, cada um com a sua distância. A fila é mostrada por baixo do grafo, com a frente primeiro. Mude o clique para Destino e escolha um nó para parar aí e ver o caminho mais curto, ou crie um novo grafo com mais nós e arestas.

Perguntas frequentes

Qual é a complexidade temporal da BFS?

O(V + E) para V nós (vértices) e E arestas: cada nó entra e sai da fila uma vez, e cada aresta é examinada a partir das duas pontas. Precisa de O(V) de memória extra para a fila e as distâncias.

Porque é que a BFS usa uma fila?

Porque «o primeiro a entrar é o primeiro a sair» mantém os nós pela ordem em que foram descobertos, que é a ordem da sua distância. Com uma pilha, a pesquisa mergulharia primeiro em profundidade: isso é a pesquisa em profundidade.

A BFS encontra caminhos mais curtos em grafos ponderados?

Em geral, não: conta arestas, não os seus comprimentos. Para grafos ponderados sem arestas negativas, use o algoritmo de Dijkstra. Se cada peso for 0 ou 1, funciona uma variante chamada BFS 0-1.

Onde se usa a BFS?

Para resolver quebra-cabeças e labirintos com o menor número de jogadas, encontrar amigos de amigos em redes sociais, percorrer a web nível a nível, difundir mensagens em redes e como peça de outros algoritmos, por exemplo para encontrar fluxos máximos.

Pronto para experimentar?

Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.

Experimente a pesquisa em largura