O algoritmo da busca em largura

Busca em largura atribui dois valores para cada vértice $v$‍:

Se não existir nenhum caminho do vértice origem para o vértice $v$‍, então a distância $v$‍ é infinita e o antecessor tem o mesmo valor especial que a origem antecessora.

Por exemplo, aqui tem um gráfico indireto com oito vértices, numerados de 0 a 7, com os números de vértices aparecendo acima ou abaixo dos vértices. Dentro de cada vértice tem dois números: a distância da origem, que é o vértice 3, seguido do predecessor no caminho mais curto do vértice 3. Um traço indica nulo:

Em BFS, nós inicialmente definimos a distância e o antecessor de cada vértice para valor especial (vazio). Nós começamos a pesquisa pela fonte e colocamos o valor da distância como 0. Então nós visitamos todos os vizinhos da fonte e damos o valor da distância de 1 e definimos seu antecessor como fonte. Em seguida, visitamos todos os vizinhos dos vértices cuja distância é 1 e que não tenham sido visitados antes e então damos a cada um desses vértices o valor da distância de 2 e colocamos o seu antecessor como o vértice que acabou de ser visitado. Continuamos até que todos os vértices alcançaveis pela fonte tenham sido alcançados, sempre visitando todos os vértices pela distância $k$‍ da fonte antes de visitar outro vértice pela distância $k+1$‍.

Dado o exemplo acima, aqui estão as etapas e um vídeo para ser reproduzido a cada etapa:

Note que não há um caminho do vértice 3 para o vértice 7, a busca não visita o vértice 7. A distância e o predecessor continuam inalterados dos seus valores iniciais de vazio.

Algumas perguntas surgem. Uma é como determinar se um vértice já foi visitado. Isso é fácil: a distância de um vértice é nula até que ele seja visitada, nesse o momento um valor numérico para a distância é atribuido. Portanto, quando examinamos os vizinhos de um vértice, visitamos apenas os vizinhos cuja distância está atualmente nula.

A outra questão é como manter o controle de quais vértices já foram visitados, mas ainda não foram visitados de todas as origens possíveis. Nós usamos uma sequência, que é uma estrutura de dados que nos permite inserir e remover itens, onde o item removido é sempre aquele que ficou há mais tempo na sequência. Chamamos esse comportamento primeiro dentro, primeiro fora. Uma sequência tem três operações:

Sempre que visitamos um vértice pela primeira vez, nós sequenciamos ele. No começo, nós sequenciamos o vértice de origem pois ele é o primeiro vértice que visitamos. Para decidir qual vértice visitar depois, nós escolhemos o vértice que está a mais tempo na sequência e removemos ele da sequência—em outras palavras, nós usamos o vértice que retorna de dequeue(). Dado o nosso gráfico de exemplo, aqui está como uma sequência se parece em cada passo, mais a visualização prévia mostraada com o estado da sequência:

Note que a qualquer momento, a sequência ou contêm vértices com as mesmas distâncias, ou contém vértices com a distância $k$‍ seguida por vértices com distância $k+1$‍. Assim é que nós asseguramos que nós visitamos todos os vértices na distância $k$‍ antes de visitar outro vértice pela distância $k+1$‍.

Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.