Busca Em Largura E Busca Em Profundidade

Busca em largura (bfs)

Um algoritmo de busca é um algoritmo que examina, sistematicamente, os vértices e os arcos de um digrafo. Cada arco é examinado no máximo uma vez. Depois de examinar a ponta inicial de um arco, o algoritmo percorre o arco e examina sua ponta final.

Há muitas maneiras de organizar a busca. Cada estratégia de busca é caracterizada pela ordem em que os vértices são examinados. Essa estratégia, também conhecida como busca bfs, está intimamente relacionada com os conceitos de distância e caminho mínimo. Quando aplicada a uma arborescência, por exemplo, a busca bfs faz uma varredura "por níveis".

Algoritmo de 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 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 todos visitados. A fila é manipulada pelas funções QUEUEinit, QUEUEput, QUEUEget, QUEUEempty e QUEUEfree. A primeira cria uma fila vazia, a segunda insere um vértice na fila, a terceira retira um vértice da fila, a quarta verifica se a fila está vazia e a última libera o espaço ocupado pela fila.

A ordem em que os vértices são visitados é registrada num vetor lbl indexado pelos vértices. Se v é o k-ésimo vértice visitado então lbl[v] vale k-1.

#define maxV 1000

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 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 && lbl[w] == -1) {

lbl[w] = conta++;

QUEUEput( w);

}

}

QUEUEfree( );

}

No início de cada iteração valem as seguinte propriedades:

todo vértice que está na fila já foi visitado;

se um vértice v já foi visitado mas algum de seus vizinhos ainda não foi visitado, então v está na fila.

(Dizemos que 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.

Exemplo A. Seja G o digrafo com 6 vértices definido pelos arcos listados a seguir.

0-2 0-3 0-4 1-2 1-4 2-4 3-4 3-5 4-5 5-1

Represente G por sua matriz de adjacência e submeta o digrafo à função DIGRAPHbfs com segundo argumento 0. Eis o estado da fila (coluna esquerda) e o estado do vetorlbl (coluna direita) no início de cada iteração:

queue 0 1 2 3 4 5

0 0 - - - - -

2 3 4 0 - 1 2 3 -

3 4 0 - 1 2 3 -

4 5 0 - 1 2 3 4

5 0 - 1 2 3 4

1 0 5 1 2 3 4

Portanto, os vértices são visitados na ordem 0 2 3 4 5 1.

Exemplo B. Neste exemplo, G é um grafo, ou seja, um digrafo simétrico. Segue a lista de arestas de G (cada aresta é um par de arcos).

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 G à função DIGRAPHbfs com segundo argumento 0. Eis o estado da fila (coluna esquerda) e o estado do vetor lbl (coluna direita) no início de cada iteração:

queue 0 1 2 3 4 5 6 7

0 0 - - - - - - -

2 5 7 0 - 1 - - 2 - 3

5 7 6 0 - 1 - - 2 4 3

7 6 3 4 0 - 1 5 6 2 4 3

6 3 4 1 0 7 1 5 6 2 4 3

3 4 1 0 7 1 5 6 2 4 3

4 1 0 7 1 5 6 2 4 3

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

Bfs versus dfs

A diferença mais marcante entre a busca em largura e a busca em profundidade está nas estruturas de dados auxiliares empregadas pelas duas estratégias. A bfs usa umafila (de vértices), enquanto a dfs usa uma pilha. (Na versão recursiva da dfs, a pilha não aparece explicitamente porque é administrada pelo mecanismo de recursão.) Mas há várias outras diferenças, mais superficiais, entre os dois algoritmos:

na dfs,