|
|
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 search = BFS). [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.
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 F ← Cria-Fila(r) |
| 15 o enquanto F não está vazia faça |
| 16 oooo u ← Sai-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.
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 (u ← Sai-da-Fila( )) é implementada por
| oooo u ← F[i] |
| oooo i ← i+1 |
a linha 10 (Entra-na-Fila(v)) é implementada por
| oooooooooo então F[f] ← v |
| oooooooooo então f ← f+1 |
Essa implementação da fila jamais sofre overflow, pois cada vértice do digrafo entra na fila no máximo uma vez.
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).
|
|
|
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 |
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.
