Busca em largura

 

Esta página volta a tratar do problema de encontrar o território de um vértice em um digrafo. Ela introduz uma versão especializada do algoritmo Território, conhecida como busca em largura (= breadth-first searchBFS).   [Para justificar a palavra busca, devemos imaginar que o algoritmo percorre o digrafo buscando vértices que pertencem ao território em questão.]

Nossa versão do algoritmo de busca em largura nada mais faz que pintar de preto todos os vértices do território de um vértice.  Mas, diferentemente do algoritmo Território, ela visita os vértices numa certa ordem específica, que chamaremos ordem de busca em largura.

Se queremos apenas encontrar o território de um vértice, a ordem em que os vértices são visitados é irrelevante. Mas a ordem de visita torna-se essencial se desejamos determinar outras propriedades além da mera pertinência de vértices ao território. Por exemplo, a ordem de visita é importante se desejamos calcular a distância entre dois vértices, como veremos em outra página.  Assim, o algoritmo de busca em largura a ser discutido abaixo é apenas um protótipo:  ele será usado como modelo para algoritmos dedicados a vários outros problemas.

Esta página é inspirada na seção 2 do capítulo 22 do CLRS.   Veja também o verbete Breadth-first search na Wikipedia.

Algoritmo de busca em largura

O algoritmo Território tem um caráter genérico:  a ordem em que os vértices saem da lista manipulada pelo algoritmo é irrelevante.  Já no algoritmo de busca em largura, a lista de vértices obedece a política FIFO: o vértice que sai da lista é sempre o que está lá há mais tempo. A lista se comporta, portanto, como uma fila FIFO.

O algoritmo pinta de preto todos os vértices do território de um vértice r.  O código abaixo supõe que os vértices do digrafo são  1, 2, … , n  e que os arcos são representados pelo vetor Adj[1..n] de listas de adjacência.

  Busca-em-Largura (n, Adj, r)
11 o para u ← 1 até n faça
12 oooo cor[u] ← branco
13 o cor[r] ← cinza
14 o FCria-Fila(r)
15 o enquanto  F  não está vazia faça
16 oooo uSai-da-Fila(F)
17 oooo para cada v em Adj[u] faça
18 ooooooo se cor[v] = branco
19 oooooooooo então  cor[v] ← cinza
10 oooooooooo então  Entra-na-Fila(v, F)
11 oooo cor[u] ← preto
12 o devolva  cor[1..n]

O comando Cria-Fila(r) cria uma fila com um só elemento igual a r.  O comando Sai-da-Fila(F) retira o primeiro elemento (ou seja, o elemento mais antigo) da fila F. O comando Entra-na-Fila(v,F) insere v no fim da fila F.

Detalhes de implementação

A fila pode ser implementada, muito simplesmente, em um vetor F[1..n].  O primeiro elemento da fila será F[i] e o último será F[f−1].

1 i f n
r                      

A linha 4 do algoritmo (Cria-Fila(r)) consiste simplesmente em

  o i ← 1
  o f ← 2
  o F[1] ← r

a linha 5 do algoritmo (enquanto F não estiver vazia faça) é traduzida por

  o enquanto i < f faça

a linha 6 (uSai-da-Fila( )) é implementada por

  oooo uF[i]
  oooo ii+1

a linha 10 (Entra-na-Fila(v)) é implementada por

  oooooooooo então  F[f] ← v
  oooooooooo então  ff+1

Essa implementação da fila jamais sofre overflow, pois cada vértice do digrafo entra na fila no máximo uma vez.

Exemplo

Aplique o algoritmo Busca-em-Largura ao digrafo definido pela figura com r = 2. Registre o estado do vetor cor e o estado da fila no início de cada iteração (ou seja, imediatamente antes de cada execução da linha 6).

Copiado de http://webmathematics.net/
u   Adj[u]
1 (6)
2 (3, 6)
3 (2, 4, 6)
4 (1, 5)
5 (4, 6)
6 (1, 4)

As linhas da tabela abaixo dão o estado da fila F[1..6] no início de sucessivas iterações:  as casas pretas contêm os vértices que já saíram da fila; as casas cinza representam a fila propriamente dita.

2          
2 3 6      
2 3 6 4    
2 3 6 4 1  
2 3 6 4 1 5
2 3 6 4 1 5
2 3 6 4 1 5

Exercícios

  1. [Importante]  Escreva uma variante do algoritmo Busca-em-Largura que atribui um número de ordem (1, 2, … ) a cada vértice no momento em que o vértice fica cinza.  (Isso permite acompanhar a ordem em que o algoritmo visita os vértices.)  Escreva outra variante que registre a ordem em que os vértices ficam pretos.

Consumo de tempo do algoritmo

Tal como Território, o algoritmo Busca-em-Largura é linear:  o consumo de tempo do algoritmo é

Ο(n+m) .

Como de hábito, m é número de arcos do digrafo.

 


Valid HTML 4.01 Strict Valid CSS!