Conteúdo principal
O algoritmo da busca em largura
Busca em largura atribui dois valores para cada vértice :
- A distância, dado um número mínimo de arestas em qualquer caminho do vértice origem a vértice
. - O vértice antecessor de
ao longo de um caminho mais curto do vértice origem. Antecessor do vértice origem é um valor especial, comonulo
, indicando que não tem nenhum antecessor.
Se não existir nenhum caminho do vértice origem para o vértice , então a distância é 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 ( da fonte antes de visitar outro vértice pela distância .
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 Dado o exemplo acima, aqui estão as etapas e um vídeo para ser reproduzido a cada etapa:
- Comece visitando o vértice 3, a fonte, definir distância como 0.
- Então visite os vértices 2 e 6, definindo a distância entre eles como 1 e seus predecessores como sendo o vértice 3.
- Comece visitando os vértices de uma distância de 1 da fonte, começando pelo vértice 2. Do vértice 2, visite os vértices 4 e 5, definindo a distância entre eles como 2 e seus predecessores como sendo o vértice 2. Não visite o vértice 3, porque ele já foi visitado.
- Do vértice 6, não visite o vértice 5, porque ele já foi visitado pelo vértice 2, e também não visite o vértice 3.
- Agora comece visitando os vértices a partir da distância de 2 da fonte. Comece visitando a partir do vértice 4. Vértice 2 já foi visitado. Visite o vértice 1, definindo sua distância para 3 e o antecessor como vértice 4.
- A partir do vértice 5, não visite nenhum de seus vizinhos, porque eles todos já foram visitados.
- Agora comece visitando a partir do vértice com distância 3 da fonte. O único vértice que atende a esse requisito é o vértice 1. Seus vizinhos, vértices 4 e 5, já foram visitados. Mas o vértice 0 não foi visitado. Visite o vértice 0, definindo sua distância da fonte como 4 e seu predecessor como o vértice 1.
- Agora comece visitando os vértices com distância a partir de 4 da fonte. Esse será apenas o vértice 0, e seu vizinho, vértice 1, já foi visitado. Terminamos!
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:
enqueue(obj)
insere um objeto na sequência.dequeue()
remove da sequência o objetivo que estiver a mais tempo, retornando o mesmo objeto.isEmpty()
retornaverdadeiro
se a atual sequência não contém objetos, efalso
se a sequência contém pelo menos um objeto.
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:- Inicialmente, a sequência contém apenas 3 vértices com distância 0.
- Tire da sequência o vértice 3 e coloque os vértices 2 e 6, ambos com distância 1. A sequência agora contém o vértice 2 com a distância 1 e o vértice 6 com a distância 1.
- Tire da sequência o vértice 2 e coloque os vértices 4 e 5, ambos com distância 2. A sequência agora contém o vértice 6 com distância 1, o vértice 4 com distância 2 e o vértice 5 com distância 2.
- Tire da sequência o vértice 6,e não coloque nenhum outro vértice. A sequência agora contém o vértice 4 com distância 2 e o vértice 5 com distância 2.
- Tire da sequência o vértice 4 e coloque o vértice 1 com distância 3. A sequência agora contém o vértice 5 com distância 2 e o vértice 1 com distância 3.
- Tire da sequência o vértice 5 e não coloque nenhum outro vértice. A sequencia agora contém somente o vértice 1 com distância 3.
- Tire da sequência o vértice 1 e coloque o vértice 0 com distância 4. A sequência agora contém somente o vértice 0 com distância 4.
- Tire da sequência vértice 0 e não coloque nenhum outro vértice. A sequência agora está vazia. Como a sequência está vazia, a busca em profundidade é finalizada.
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 seguida por vértices com distância . Assim é que nós asseguramos que nós visitamos todos os vértices na distância antes de visitar outro vértice pela distância .
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.
Quer participar da conversa?
Nenhuma postagem por enquanto.