Busca em largura

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

Diferentemente do algoritmo Território, o algoritmo de busca em largura visita os vértices do grafo numa ordem específica, que chamaremos ordem de busca em largura. Essa ordem é essencial para calcular a distância entre dois vértices, como veremos em outra página.

Esta página é inspirada na seção 2 do capítulo 22 do CLRS.

Algoritmo de busca em largura

A ordem em que os vértices saem da lista administrada pelo algoritmo Território é irrelevante. Já no algoritmo de busca em largura, a lista de vértices é administrada pela política FIFO: o vértice a sair da lista é aquele que está lá há mais tempo. A lista se comporta, portanto, como uma fila.

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

Busca-em-Largura (n, Adj, r)
11 . para u ← 1 até n faça
12 .ooo cor[u] ← branco
13 . cor[r] ← cinza
14 . Nova-Fila (r)
15 . enquanto a fila não estiver vazia faça
16 .ooo uSai-da-Fila ( )
17 .ooo para cada v em Adj[u] faça
18 .oooooo se cor[v] = branco
19 .ooooooooo então cor[v] ← cinza
10 .ooooooooo então Entra-na-Fila (v)
11 .ooo cor[u] ← preto
12 . devolva cor[1 .. n]

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

Exemplo A.  Aplique o algoritmo Busca-em-Largura ao grafo 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

  1. Reescreva o código de Busca-em-Largura com a fila implementada num vetor F[1 .. n].
  2. ★ 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.

Desempenho

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 grafo.

Apêndice: BFS versus DFS

Apesar da semelhança entre a siglas, a busca DFS é muito diferente da busca BFS e tem aplicações muito diferentes. Eis algumas diferenças entre as duas estratégias de busca: