Algoritmos em Grafos  |  Livros  |  WWW  |  Índice de Termos

 

Busca em largura

(Veja Breadth-first search na Wikipedia.)

Este capítulo discute uma implementação clássica do algoritmo genérico de busca.  Nessa implementação, o conjunto de vértices ativos é administrado como uma fila (= queue):  cada iteração escolhe o vértice ativo que foi marcado há mais tempo.  O resultado dessa política é conhecido como busca em largura (= breadth-first search = BFS).

Quando o conjunto de vértices ativos é tratado como uma fila, o algoritmo genérico pode ser simplificado pois podemos lidar, de uma só vez, com todos os arcos que saem de v e assim dispensar o conjunto A(v). O algoritmo pode ser reformulado assim:

1 2 3 4 5 6 7

enquanto a fila não está vazia faça seja  v  o primeiro vértice da fila para cada vértice  w  adjacente a v faça se  w  não está marcado então marque  w então insira  w  no final da fila retire  v  da fila

Implementação

Eis a implementação em C, usando as estruturas de dados do SGB:

#define marca x.I
#define próximo y.V

void 
busca_em_largura (Graph *g, Vertex *r) {
   Vertex *v, *w, *ativo, *último;  Arc *a;

   for (v = g–>vertices; v < g–>vertices+g–>n; v++)
      v–>marca = 0;
   r–>marca = 1;
   ativo = último = r;  último–>próximo = NULL;

   while (ativo != NULL) {
      v = ativo;
      for (a = v–>arcs; a != NULL; a = a–>next) {
         w = a–>tip;
         if (w–>marca == 0) {
            w–>marca = 1;
            w–>próximo = NULL;
            último–>próximo = w;
            último = w; 
         }
      }  
      ativo = ativo–>próximo; 
   }
}

A função recebe um grafo g e um vértice r e marca o território de r;  um vértice v é considerado marcado se v–>marca vale 1.   A fila de vértices ativos é

ativo,  ativo–>próximo,  ativo–>próximo–>próximo,  . . . , último,  NULL.

Versão com predecessores

É fácil escrever uma versão com predecessores no lugar das marcas:

#define pred x.V
#define próximo y.V

void 
busca_em_largura (Graph* g, Vertex* r) {
   Vertex* v, * w, * ativo, * último;  Arc* a;

   for (v = g–>vertices; v < g–>vertices+g–>n; v++)
      v–>pred = NULL;
   r–>pred = r;
   ativo = último = r;  último–>próximo = NULL;
   while (ativo != NULL) {
      v = ativo;
      for (a = v–>arcs; a != NULL; a = a–>next) {
         w = a–>tip;
         if (w–>pred == NULL) {
            w–>pred = v;
            w–>próximo = NULL;
            último–>próximo = w;
            último = w; 
         }
      }  
      ativo = ativo–>próximo; 
   }
}

Exercícios

1. Que acontece se inserirmos  "ativo = ativo–>próximo"  logo depois da linha "v = ativo"  no código da função busca_em_largura?

2. O que há de errado com o seguinte código de busca? Ele marca corretamente o território de r? Dê um pequeno grafo que "derrube" o código.

      for (v = g–>vertices; v < g–>vertices+g–>n; v++)
         v–>marca = 0, v–>próximo = NULL;
      ativo = último = r;
      while (ativo != NULL) {
         v = ativo;
         v–>marca = 1;
         for (a = v–>arcs; a != NULL; a = a–>next) {
           w = a–>tip;
           if (w–>marca == 0) {
               último–>próximo = w;
               último = w; 
           }  
        }  
        ativo = ativo–>próximo; 
      }
   

3. Escreva uma variante da função busca_em_largura que receba um grafo e um vértice  r  e imprima, uma e uma só vez, o nome (campo name) de cada vértice do território de r.

4. Escreva uma variante da função busca_em_largura que marque os vértices do terrítório de r com 1, 2, 3, etc. à medida que os vértices forem sendo encontrados.

5. Escreva uma versão recursiva da função busca_em_largura.

6. Analise e discuta a seguinte função:

   #define marca x.I
   #define próximo y.V
   
   void busca (Graph* g, Vertex* r) {
      Vertex* v, * w, * ativo;  Arc* a;
   
      for (v = g–>vertices; v < g–>vertices+g–>n; v++)  
          v–>marca = 0;
      r–>marca = 1;
      ativo = r;  ativo–>próximo = NULL;
      while (ativo != NULL) {
         v = ativo;
         ativo = ativo–>próximo;                       /*09*/
         for (a = v–>arcs; a != NULL; a = a–>next) {   /*10*/
            w = a–>tip;                                /*11*/
            if (w–>marca == 0) {                       /*12*/
               w–>marca = 1;                           /*13*/
               w–>próximo = ativo;                     /*14*/
               ativo = w;                              /*15*/
            }                                          /*16*/
         }                                             /*17*/
      }                                                /*18*/
   }
   

   Ela marca corretamente o território de r? O conjunto de vértices ativos parece ser administrado como uma pilha; isso é de fato verdade?  Que acontece se a linha 09 for colocada entre as linhas 17 e 18?