A busca em largura, também conhecida como busca BFS (= breadth-first search), 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".
BFS versus DFS
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:
- na busca em profundidade, o próprio algoritmo escolhe o vértice inicial, enquanto a busca em largura começa tipicamente num vértice especificado pelo usuário;
- a busca em profundidade visita, tipicamente, todos os vértices do digrafo, enquanto a busca em largura visita apenas os vértices que podem ser atingidos a partir do vértice inicial;
- a busca em profundidade é descrita, usualmente, em estilo recursivo, enquanto a busca em largura é descrita em estilo iterativo.
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.
Busca em largura
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.
Para implementar essa idéia, 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 ordem em que os vértices são visitados é registrada num vetor ordemvisit indexado pelos vértices, à semelhança do que fizemos ao estudar busca em profundidade.
No início de cada iteração valem as seguinte propriedades: 1. todo vértice que está na fila já foi visitado; 2. se um vértice v já foi visitado mas algum de seus vizinhos ainda não foi visitado, então v está na fila. (Um vértice x já foi visitado se e somente se ordemvisit[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.
Arborescência de busca em largura
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 pai.
[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.]
No início de cada iteração, cada vértice que está na fila é uma folha da arborescência representada por pai.
Desempenho
A função bfsDigrafo é linear: ela consome tempo proporcional a V^2 no pior caso. A variante dessa função para listas de adjacência consome tempo proporcional a V+E.
Exercícios para Fixação
1. O código bfsDigrafo utiliza matriz ou lista de adjacências para representar o grafo?
2. Como ficaria esse código com o cálculo do vetor de pais?
3. O que a bfs faz que a dfs não pode fazer?
4. Faça um algoritmo que determine o caminho mínimo entre dois vértices usando bfs, o peso de todas as arestas é o mesmo.
Fonte: IME
BFS versus DFS
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:
- na busca em profundidade, o próprio algoritmo escolhe o vértice inicial, enquanto a busca em largura começa tipicamente num vértice especificado pelo usuário;
- a busca em profundidade visita, tipicamente, todos os vértices do digrafo, enquanto a busca em largura visita apenas os vértices que podem ser atingidos a partir do vértice inicial;
- a busca em profundidade é descrita, usualmente, em estilo recursivo, enquanto a busca em largura é descrita em estilo iterativo.
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.
Busca em largura
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.
Para implementar essa idéia, 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 ordem em que os vértices são visitados é registrada num vetor ordemvisit indexado pelos vértices, à semelhança do que fizemos ao estudar busca em profundidade.
#define MAXV 10000
int cnt, ordemvisit[MAXV];
int fila[MAXV];
int ini,fim;
/* A função bfsDigrafo 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 ordemvisit. */
void bfsDigrafo (int s) {
int v, w;
cnt = 0;
for (v = 0; v < n; v++) ordemvisit[v] = -1;
ordemvisit[s] = cnt++;
ini = fim = 0;
fila[ini++] = s;
while (ini > fim) {
v = fila[fim++];
for (w = 0; w < n; w++)
if (g[v][w] == 1)
if (ordemvisit[w] == -1) {
ordemvisit[w] = cnt++;
fila[ini++] = w;
}
}
}
No início de cada iteração valem as seguinte propriedades: 1. todo vértice que está na fila já foi visitado; 2. se um vértice v já foi visitado mas algum de seus vizinhos ainda não foi visitado, então v está na fila. (Um vértice x já foi visitado se e somente se ordemvisit[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.
Arborescência de busca em largura
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 pai.
[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.]
No início de cada iteração, cada vértice que está na fila é uma folha da arborescência representada por pai.
Desempenho
A função bfsDigrafo é linear: ela consome tempo proporcional a V^2 no pior caso. A variante dessa função para listas de adjacência consome tempo proporcional a V+E.
Exercícios para Fixação
1. O código bfsDigrafo utiliza matriz ou lista de adjacências para representar o grafo?
2. Como ficaria esse código com o cálculo do vetor de pais?
3. O que a bfs faz que a dfs não pode fazer?
4. Faça um algoritmo que determine o caminho mínimo entre dois vértices usando bfs, o peso de todas as arestas é o mesmo.
Fonte: IME
