Algoritmos para Grafos  |  Índice

Busca em largura

Um algoritmo de busca é um algoritmo que percorre um grafo andando pelos arcos de um vértice a outro.  Depois de visitar a ponta inicial de um arco, o algoritmo percorre o arco e visita sua ponta final.  Cada arco é percorrido no máximo uma vez.

Há muitas maneiras de organizar uma busca.  Cada estratégia de busca é caracterizada pela ordem em que os vértices são visitados.   Este capítulo introduz a busca em largura (= breadth-first search), ou busca BFS.  Essa estratégia está intimamente relacionada com os conceitos de distância e caminho mínimo.

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 vizinhos de s, depois todos os vizinhos dos vizinhos, e assim por diante.

O algoritmo numera os vértices, em sequência, na ordem em que eles são descobertos (ou seja, visitados pela primeira vez).  Para fazer isso, o algoritmo usa uma fila (= queue) de vértices.  No começo de cada iteração, a fila contém vértices que já foram numerados mas têm vizinhos ainda não numerados.  O processo iterativo consiste no seguinte:

No começo da primeira iteração, a fila contém o vértice s, com número 0, e nada mais.

Implementação do algoritmo

A fila de vértices é manipulada pelas funções auxiliares QUEUEinit(), QUEUEput(), QUEUEget(), QUEUEempty() e QUEUEfree().  A primeira cria uma fila vazia, a segunda coloca um vértice na fila, a terceira tira um vértice da fila, a quarta verifica se a fila está vazia, e a última libera o espaço ocupado pela fila.

A numeração dos vértices é registrada num vetor  num[]  indexado pelos vértices.  Se v é o k-ésimo vértice descoberto então num[v] recebe o valor k.

static int num[1000];

/* A função GRAPHbfs() implementa o algoritmo de busca em largura.
   Ela visita todos os vértices do grafo G 
   que estão ao alcance do 
   vértice s e 
   registra num vetor num[]
   a ordem em que os vértices são descobertos.
   Esta versão da função supõe que o grafo G 
   é representado por listas de adjacência. 
   (Código inspirado no programa 18.9 de Sedgewick.) */

void GRAPHbfs( Graph G, vertex s) 
{ 
   int cnt = 0;
   for (vertex v = 0; v < G->V; ++v)
      num[v] = -1;
   QUEUEinit( G->V);
   num[s] = cnt++; 
   QUEUEput( s); 

   while (!QUEUEempty( )) {
      vertex v = QUEUEget( ); 
      for (link a = G->adj[v]; a != NULL; a = a->next)
         if (num[a->w] == -1) {
            num[a->w] = cnt++; 
            QUEUEput( a->w); 
         }
   }
   QUEUEfree( ); 
}

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

1. todo vértice que está na fila já foi numerado;
2. se um vértice v já foi numerado mas algum de seus vizinhos ainda não foi numerado, então v está na fila.

Observe que a fila foi dimensionada corretamente na linha QUEUEinit( G->V): cada vértice de G entra na fila no máximo uma vez e portanto a fila não precisa de mais do que G->V posições.

Exemplo A.  Considere o grafo G definido pelos arcos  0-2 0-3 0-4 1-2 1-4 2-4 3-4 3-5 4-5 5-1.  Suponha que os vértices estão em ordem crescente de nomes em cada lista de adjacência.  Submeta G à função GRAPHbfs() com segundo argumento 0.  Eis o estado da fila (coluna esquerda) e o estado do vetor num[] (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
                 0 5 1 2 3 4

Basta examinar o vetor num[] para deduzir que os vértices foram descobertos (e portanto numerados) na ordem  0 2 3 4 5 1.

Exemplo B.  Neste exemplo, G é o grafo não-dirigido definido pelas arestas  0-1 0-2 0-5 2-1 2-3 2-4 3-4 3-5.  Suponha que os vértices estão em ordem crescente de nomes em todas as listas de adjacência e submeta o grafo à função GRAPHbfs() com segundo argumento 0.  Eis o estado da fila e o estado do vetor num[] no início de cada iteração:

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

Os vértices foram descobertos (e portanto numerados) na ordem  0 1 2 5 3 4.

Árvore de busca em largura

A busca em largura a partir de um vértice s constrói uma árvore radicada com raiz s:  cada arco v-w percorrido até um vértice w não numerado é acrescentado à árvore.  Essa árvore radicada é conhecida como árvore de busca em largura, ou árvore BFS (= BFS tree).  Podemos representar essa árvore explicitamente por um vetor de pais pa[]. Basta acrescentar algumas linhas ao código de GRAPHbfs():

static int num[1000];
static vertex pa[1000];

void GRAPHbfs( Graph G, vertex s) 
{ 
   int cnt = 0;
   for (vertex v = 0; v < G->V; ++v)
      num[v] = pa[v] = -1;
   QUEUEinit( G->V);
   num[s] = cnt++; 
   pa[s] = s;
   QUEUEput( s); 

   while (!QUEUEempty( )) {
      vertex v = QUEUEget( ); 
      for (link a = G->adj[v]; a != NULL; a = a->next)
         if (num[a->w] == -1) {
            num[a->w] = cnt++; 
            pa[a->w] = v;
            QUEUEput( a->w); 
         }
   }
   QUEUEfree( ); 
}

O sub­grafo de G representado pelo vetor pa[] é, de fato, uma árvore radicada pois (1) o vetor num[] é uma numeração topológica do sub­grafo e (2) no máximo um arco do sub­grafo entra em cada vértice. (Veja abaixo o exercício Numeração topológica da árvore BFS.)

No início de cada iteração, cada vértice na fila é uma folha da árvore radicada representada por pa[].

Exemplo C.  Aplique a função GRAPHbfs() ao grafo do exemplo A.  No fim da execução da função, o vetor pa[] estará no seguinte estado:

   v    0 1 2 3 4 5
pa[v]   0 5 0 0 0 3

Exemplo D.  Aplique a função GRAPHbfs() ao grafo não-dirigido do exemplo B.  No fim da execução da função, o vetor pa[] estará no seguinte estado:

   v    0 1 2 3 4 5
pa[v]   0 0 0 2 2 0

Desempenho

Quanto tempo a função GRAPHbfs() consome para processar um grafo com V vértices e A arcos?  Cada iteração em while (!QUEUEempty()) tira um vértice v da fila e percorre os arcos do leque de saída de v. Como cada vértice entra na fila e sai da fila no máximo uma vez, cada arco do grafo é percorrido no máximo uma vez durante a execução do while. Assim, a execução de todas as iteração consome tempo proporcional a A no pior caso.  O resto do código consome tempo proporcional a V.  Portanto, o consumo total de tempo é proporcional a

V + A

no pior caso, supondo que o grafo é representado por um listas de adjacência.  (Se A ≥ V, como acontece em muitas aplicações, podemos dizer que o consumo de tempo é proporcional a A.)  Esse tempo é proporcional ao tamanho do grafo e portanto podemos dizer que GRAPHbfs() é linear.

Se o grafo for representado por matriz de adjacências, uma análise semelhante mostra que o consumo de tempo é proporcional a

V²

no pior caso.  Se nos restrigirmos a grafos densos, esse consumo é linear.

BFS versus DFS

Apesar da semelhança entre a siglas, a busca BFS e a busca DFS são muito diferentes e têm aplicações muito diferentes.

A diferença mais marcante entre as duas buscas está nas estruturas de dados auxiliares empregadas pelas duas estratégias.  A BFS usa uma fila (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.)

Outras diferenças entre os dois algoritmos são mais superficiais:

• na BFS, o usuário escolhe o vértice inicial; na DFS o próprio algoritmo escolhe o vértice inicial de cada etapa;
• a DFS visita todos os vértices do grafo, enquanto a BFS visita apenas os vértices que estão ao alcance do vértice inicial;
• em geral, a DFS é descrita em estilo recursivo enquanto a BFS é descrita em estilo iterativo.