Algoritmos para Grafos, via Sedgewick | Índice remissivo
Como já dissemos ao discutir busca em profundidade, um algoritmo de busca é um algoritmo que examina, sistematicamente, os vértices e os arcos de um digrafo. Há muitas maneiras de organizar uma tal busca. Cada estratégia de busca é caracterizada pela ordem em que os vértices são visitados.
Esta página introduz a busca em largura (= breadth-first search = BFS). Essa estratégia, também conhecida como busca BFS, está intimamente relacionada com o conceito de distância entre vértices. Quando aplicada a uma arborescência, a busca BFS faz uma varredura "por níveis".
(Esta página corresponde aproximadamente à seção 18.7 (Breadth-First Search), p.114-124, do capítulo 18 do livro de Sedgewick.)
A diferença mais marcante entre a busca em largura e a busca em profundidade está na estrutura de dados auxiliar empregada por uma das estratégias e pela outra. A busca em largura usa uma fila (de vértices), enquanto a busca em profundidade usa uma pilha. (Na versão recursiva da busca em profundidade, a pilha não aparece explicitamente pois é administrada pelo mecanismo de recursão.) Mas há várias outras diferenças, mais superficiais, entre os dois algoritmos:
O fato é que, apesar da semelhança entre a siglas, a busca DFS e a busca BFS são muito diferentes e têm aplicações muito diferentes.
A busca em largura começa por um vértice, digamos s, especificado pelo usuário. O algoritmo visita s, depois visita todos os vértices que estão à distância 1 de s, depois todos os vértices que estão à distância 2 de s, e assim por diante. (O conceito de distância será definido precisamente na próxima página.)
Para implementar essa ideia, o algoritmo usa uma fila de vértices. Essa fila contém todos os vértices já visitados cujos vizinhos ainda não foram visitados. A fila é manipulada pelas funções QUEUEinit, QUEUEput, QUEUEget e QUEUEempty. (A primeira cria uma fila vazia, a segunda insere um vértice na fila, a terceira retira um vértice da fila, e a última verifica se a fila está vazia.)
A ordem em que os vértices são visitados é registrada num vetor lbl indexado pelos vértices, à semelhança do que fizemos ao estudar busca em profundidade. [O nome "lbl" não faz muito sentido no presente contexto, uma vez que a busca em largura não tem relação alguma com preorder traversal de árvores.] Se v é o k-ésimo vértices visitado então prev[v] vale k-1.
#define maxV 10000 static int conta, lbl[maxV];/* A função DIGRAPHbfs visita todos os vértices do digrafo G que podem ser alcançados a partir do vértice s. A ordem em que os vértices são visitados é registrada no vetor lbl. (Código inspirado no programa 18.9, p.119, de Sedgewick.) */
void DIGRAPHbfs (Digraph G, Vertex s) { Vertex v, w; conta = 0; for (v = 0; v < G->V; v++) lbl[v] = -1; QUEUEinit(G->V); lbl[s] = conta++; QUEUEput(s); while (!QUEUEempty()) { v = QUEUEget(); for (w = 0; w < G->V; w++) if (G->adj[v][w] == 1) if (lbl[w] == -1) { lbl[w] = conta++; QUEUEput(w); } } }
No início de cada iteração valem as seguinte propriedades:
(Um vértice x já foi visitado se e somente se lbl[x] é diferente de -1.) Cada vértice entra na fila no máximo uma vez. Portanto, basta que a fila tenha espaço suficiente para V vértices.
(Este exemplo é cópia da figura 18.21, p.116 de Sedgewick.) Seja G o digrafo simétrico definido pelo conjunto de arestas (cada aresta é um par de arcos) abaixo.
0-2 2-6 6-4 4-5 5-0 0-7 7-1 7-4 3-4 3-5
Represente G por sua matriz de adjacência e submeta o digrafo à função DIGRAPHbfs. Eis o estado da fila no início de sucessivas iterações:
0-2 0-5 0-7
0-5 0-7 2-6
0-7 2-6 5-3 5-4
2-6 5-3 5-4 7-1 7-4
5-3 5-4 7-1 7-4 6-4
5-4 7-1 7-4 6-4 3-4
7-1 7-4 6-4 3-4
7-4 6-4 3-4
6-4 3-4
3-4
Eis o vetor lbl no início de sucessivas iterações (com "*" no lugar de "-1"):
0 1 2 3 4 5 6 7
---------------
* * * * * * * *
0 * * * * * * *
0 * 1 * * * * *
0 * 1 * * 2 * *
0 * 1 * * 2 * 3
0 * 1 * * 2 4 3
0 * 1 5 * 2 4 3
0 * 1 5 6 2 4 3
0 7 1 5 6 2 4 3
Portanto, os vértices são visitados na ordem 0 2 5 7 6 3 4 1.
A busca em largura a partir de um vértice s descreve, implicitamente, uma arborescência com raiz s. Essa arborescência é conhecida como arborescência de busca em largura (= BFS tree). Podemos representar essa arborescência explicitamente por um vetor de pais parent.
[Muita gente diz "árvore de busca" no lugar do meu "arborescência de busca". Infelizmente, a palavra "árvore" também é usada para designar um outro conceito, o que pode causar confusão.]
#define maxV 10000 static int conta, lbl[maxV]; static Vertex parent[maxV];
void DIGRAPHbfs (Digraph G, Vertex s) { Vertex v, w; conta = 0; for (v = 0; v < G->V; v++) lbl[v] = -1; QUEUEinit(G->V); lbl[s] = conta++; parent[s] = s; QUEUEput(s); while (!QUEUEempty()) { v = QUEUEget(); for (w = 0; w < G->V; w++) if (G->adj[v][w] == 1) if (lbl[w] == -1) { lbl[w] = conta++; parent[w] = v; QUEUEput(w); } } }
No início de cada iteração, cada vértice que está na fila é uma folha da arborescência representada por parent.
Aplique a função DIGRAPHbfs ao grafo do exemplo acima. No fim da execução da função, o vetor parent estará no seguinte estado:
v 0 1 2 3 4 5 6 7
---------------
parent[v] 0 7 0 5 5 0 2 0
8-9 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4 .
Suponha que o grafo está representado por sua matriz de adjacência. Faça um desenho da arborescência de busca.
8-9 3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4
Faça uma busca em largura a partir do vértice 0. Faça um desenho da arborescência de busca.
static int conta, lbl[maxV];
void DIGRAPHsearch (Digraph G) {
Vertex v;
conta = 0;
for (v = 0; v < G->V; v++) lbl[v] = -1;
for (v = 0; v < G->V; v++)
if (lbl[v] == -1)
bfs(G, ARC(v, v));
}
void bfs (Digraph G, Arc e) {
Vertex v, w;
QUEUEput(e);
while (!QUEUEempty()) {
e = QUEUEget();
if (lbl[e.w] == -1) {
lbl[e.w] = conta++;
parent[e.w] = e.v;
for (v = 0; v < G->V; v++)
if (G->adj[e.w][v] == 1)
if (lbl[v] == -1)
QUEUEput(ARC(e.w, v));
}
}
}
static int conta, lbl[maxV];
void DIGRAPHsearch (Digraph G) {
Vertex v;
conta = 0;
for (v = 0; v < G->V; v++) lbl[v] = -1;
for (v = 0; v < G->V; v++)
if (lbl[v] == -1)
bfs(G, ARC(v, v));
}
void bfs (Digraph G, Arc e) {
Vertex v, w;
QUEUEput(e);
lbl[e.w] = conta++;
while (!QUEUEempty()) {
e = QUEUEget();
w = e.w;
parent[w] = e.v;
for (v = 0; v < G->V; v++)
if (G->adj[w][v] == 1) {
if (lbl[v] == -1) {
QUEUEput(ARC(w, v));
lbl[v] = conta++;
}
}
}
A função DIGRAPHbfs é linear: ela consome tempo proporcional a V2 no pior caso. A variante dessa função para listas de adjacência consome tempo proporcional a V+E.