Algoritmos para Grafos, via Sedgewick  |  Índice remissivo

Busca em profundidade

Um algoritmo de busca (ou varredura) é um algoritmo que visita, sistematicamente, todos os vértices e todos os arcos de um digrafo.  Cada arco é visitado uma e uma só vez.  Depois de visitar a ponta inicial de um arco, o algoritmo percorre o arco e visita sua ponta final.

Há muitas maneiras de fazer uma tal busca.  Cada estratégia de busca é caracterizada pela ordem em que os vértices são visitados.  Diremos que o k-ésimo vértice visitado durante a busca tem número de ordem k−1 . 

Esta página introduz uma poderosa estratégia de busca conhecida como busca em profundidade (= depth-first searchDFS).  A busca em profundidade, ou busca DFS, está relacionada com conceitos como backtracking, varredura em pré-ordem, exploração de labirintos, exploração Tremaux, fio de Ariadne (no mito de Teseu e o Minotauro), etc.  A página Procurando caminhos já fez uma introdução à busca DFS.

[Esta página corresponde aproximadamente às seções 18.1 (Exploring a Maze) e 18.2 (Depth-First Search) do capítulo 18 (Graph Search) do livro de Sedgewick.]

Busca DFS

A função DIGRAPHdfs abaixo executa uma busca em profundidade em um digrafo G.  Dizemos que a função visita os vértices do digrafo "em ordem DFS" ou, mais precisamente, em pré-ordem (= preorder).  Cada vértice v recebe um rótulo que dá o número de ordem do vértice.  Os rótulos são armazenados num vetor  pre  indexado pelos vértices.

/* Vamos supor que nossos digrafos têm no máximo maxV vértices. */

static int conta, pre[maxV];

/* A função DIGRAPHdfs visita todos os vértices e todos os arcos do digrafo G. A função atribui um número de ordem pre[x] a cada vértice x:  o k-ésimo vértice visitado recebe número de ordem k-1.  (Código inspirado no programa 18.3, p.87, de Sedgewick.) */

void DIGRAPHdfs( Digraph G) { 
   Vertex v;
   conta = 0;
   for (v = 0; v < G->V; v++) 
      pre[v] = -1;
   for (v = 0; v < G->V; v++)
      if (pre[v] == -1) 
         dfsR( G, v);
}

/* A função dfsR supõe que o digrafo G é representado por uma matriz de adjacência.  (Inspirado no programas 18.1, p.82, de Sedgewick.) */

void dfsR( Digraph G, Vertex v) { 
   Vertex w;
   pre[v] = conta++; 
   for (w = 0; w < G->V; w++)
      if (G->adj[v][w] != 0 && pre[w] == -1)
         dfsR( G, w); 
}

A função DIGRAPHdfs é apenas uma interface.  A busca em profundidade propriamente dita é realizada pela função recursiva dfsR.  A versão acima supõe que o digrafo está representado por sua matriz de adjacência, enquanto a versão abaixo supõe representação por listas de adjacência.

/* A função dfsR supõe que o digrafo G é representado por listas de adjacência.  (Inspirado no programas 18.2, p.85, de Sedgewick.) */

void dfsR( Digraph G, Vertex v) { 
   link p; 
   pre[v] = conta++; 
   for (p = G->adj[v]; p != NULL; p = p->next)
      if (pre[p->w] == -1) 
         dfsR( G, p->w); 
}

A ordem em que os vértices são visitados (e portanto o conteúdo do vetor de rótulos pre) depende não só do digrafo mas também da ordem em que os vizinhos de cada vértice aparecem nas listas de adjacência.

Se pre[v] vale -1, dizemos que o vértice v ainda não foi visitado.  Dizemos que um arco v-w foi visitado quando a função dfsR se depara com w ao examinar os vizinhos de v.

Qual a diferença entre a função DIGRAPHdfs de busca em profundidade e a função DIGRAPHpath de busca de caminhos?  Há apenas duas pequenas diferenças:  (1) DIGRAPHdfs visita todos os vértices do digrafo, enquando DIGRAPHpath visita apenas os que são acessíveis a partir de um vértice s   e  (2) DIGRAPHdfs numera os vértices na ordem em que eles são visitados, enquanto DIGRAPHpath marca todos os vértices que visita com um mesmo rótulo 1.

Exemplo A

Considere o digrafo G definido pelos arcos  2-0 2-3 2-4 0-1 0-4 3-4 3-5 4-1 4-5 5-1 .   Eis a matriz de adjacência do digrafo (com "-" no lugar de "0"):

     - 1 - - 1 -
     - - - - - -
     1 - - 1 1 -
     - - - - 1 1
     - 1 - - - 1
     - 1 - - - -

Segue o rastramento de DIGRAPHdfs(G).  Cada linha da figura registra o momento em que um arco é visitado; registra também cada invocação de dfsR. A execução de cada nova instância de dfsR é indicada por uma indentação apropriada das linhas.

                                  0 1 2 3 4 5
                                             
     dfsR(G,0)                    0 - - - - -
       0-1 dfsR(G,1)              0 1 - - - -
       0-4 dfsR(G,4)              0 1 - - 2 -
         4-1                                 
         4-5 dfsR(G,5)            0 1 - - 2 3
           5-1                               
                                             
     dfsR(G,2)                    0 1 4 - 2 3
       2-0                                   
       2-3 dfsR(G,3)              0 1 4 5 2 3
         3-4                                 
         3-5                                 
       2-4                                   

Em cada linha da coluna direita da figura aparece o estado do vetor pre (com "-" no lugar de "-1") imediatamente depois da execução de "pre[v] = conta++" na correspondente invocação de dfsR.   O estado final de pre informa que os vértice são visitados na ordem  0 1 4 5 2 3.  Esta é, portanto, enumeração dos vértices em pré-ordem.

Exemplo B

O exemplo abaixo ilustra uma busca em profundidade num grafo, ou seja, num digrafo simétrico.  O grafo é definido pelo conjunto de arestas a seguir.

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

[Esse exemplo foi copiado da figura 18.5, p.82, de Sedgewick.]

undirected graph with 8 vertices

Suponha que o grafo é representado por sua matriz de adjacência. A figura abaixo registra cada arco no momento em que ele é visitado e registra cada invocação de dfsR.

                                    0 1 2 3 4 5 6 7
                                                   
     dfsR(G,0)                      0 - - - - - - -
       0-2 dfsR(G,2)                0 - 1 - - - - -
         2-0                                       
         2-6 dfsR(G,6)              0 - 1 - - - 2 -
           6-2                                     
           6-4 dfsR(G,4)            0 - 1 - 3 - 2 -
             4-3 dfsR(G,3)          0 - 1 4 3 - 2 -
               3-4                                 
               3-5 dfsR(G,5)        0 - 1 4 3 5 2 -
                 5-0                               
                 5-3                               
                 5-4                               
             4-5                                   
             4-6                                   
             4-7 dfsR(G,7)          0 - 1 4 3 5 2 6
               7-0                                 
               7-1 dfsR(G,1)        0 7 1 4 3 5 2 6
                 1-7                               
               7-4                                 
       0-5                                         
       0-7                                         

Os sucessivos estados do vetor de rótulos pre aparecem do lado direito da figura (com "-" no lugar de "-1").   O estado final de pre informa que os vértice são visitados na ordem  0 2 6 4 3 5 7 1.

Exercícios 1

  1. Considere o digrafo definido pelos arcos  0-1 1-2 1-3 3-4 3-5 1-6 0-7 7-8 7-9 8-6 .  Faça uma busca DFS.  Em que ordem os vértices são visitados?
  2. [Sedgewick 18.4, p.86]  Aplique a função DIGRAPHdfs, versão para matriz de adjacência, ao grafo definido pelas arestas
         0-2 0-5 1-2 3-4 4-5 3-5
    

    e exiba o rastreamento da execução da função no formato do exemplo acima.

  3. [Sedgewick 18.5, p.86]  Refaça o exemplo acima depois de alterar o código de dfsR, versão para matriz de adjacência, de modo que cada linha da matriz seja percorrida "ao contrário", isto é, de V-1 para 0.
  4. [Sedgewick 18.7, p.90]  Aplique a função DIGRAPHdfs, versão para matriz de adjacência, ao grafo definido pelas arestas
         3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4
    

    e faça o rastreamento da execução da função. Use o formato do exemplo acima.

  5. Refaça o exemplo acima supondo que o grafo é representado por suas listas de adjacência. Suponha que as listas são construídas pela inserção das arestas, na ordem dada acima, num grafo inicialmente vazio.
  6. [Sedgewick 18.8, p.90]  Aplique a função DIGRAPHdfs, versão para listas de adjacência, ao grafo definido pelas arestas
         3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4
    

    e faça o rastreamento da execução da função. Suponha que as listas de adjacência são construídas inserindo os arcos acima, na ordem dada, num grafo inicialmente vazio. Use o formato do exemplo acima.

  7. Execute uma busca em profundidade a partir do vértice 0 no digrafo G dado pelas listas de adjacência a seguir.  Exiba o rastreamento da busca.
          0: 1 4   
          1: 2 5   
          2: 3     
          3: 7     
          4: 8     
          5: 4     
          6: 5 10 2
          7: 11 6  
          8: 9     
          9: 5 8   
         10: 9     
         11: 10    
    
  8. A função DIGRAPHdfs funciona corretamente quando s é igual a t?  E quando G->A vale 0?  E quando G->V vale 1?
  9. [Sedgewick 17.85, p.62]  Modifique as funções DIGRAPHdfs e dfsR de modo que elas imprimam um rastreamento como o da coluna esquerda do exemplo acima. [Veja também a figura 17.17, p.51, do livro de Sedgewick.]   (Sugestão: Para fazer a indentação, use uma variável global que é incrementada quando a execução entra em dfsR e decrementada quando a execução sai de dfsR.)  Compile e teste as funções modificadas. Use um subgrafo aleatório da grade quadrada para os testes.
  10. Qual a principal diferença entre a busca em profundidade, executada pela função DIGRAPHdfs, e a busca por um caminho a partir de um certo vértice, executada pela função DIGRAPHpath?
  11. Escreva a documentação da função recursiva dfsR  (ou seja, diga o que a função faz).  [Solução]

Desempenho

A função DIGRAPHdfs, combinada com a versão de dfsR para matriz de adjacência, consome tempo proporcional a

V2

quando aplicada a um digrafo com V vértices.  (Isso é proporcional ao tempo necessário para ler a matriz de adjacência; o algoritmo é, portanto, muito rápido quando aplicado a um digrafo denso.)

Combinada com a versão de dfsR para listas de adjacência, a função DIGRAPHdfs consome tempo proporcional a

V + A

quando aplicada a um digrafo com V vértices e A arcos.  (Isso é proporcional ao tempo necessário para ler todas as listas de adjacência.) Se o digrafo é esparso, esta segunda versão é mais rápida que a primeira.

Vértices em pré-ordem

Depois da execução da busca em profundidade, a sequência de números pre[0], pre[1], …, pre[V-1] é uma permutação de 01, …, V-1,  sendo V o número de vértices de G.  Assim, para imprimir os vértices em pré-ordem basta inverter o vetor pre:

     Vertex preordem[maxV];
     int i;
     
     for (v = 0; v < G->V; ++v)
        preordem[pre[v]] = v;
     for (i = 0; i < G->V; ++i)
        printf( "%d ", preordem[i]);

Exercícios 2

  1. Suponha que o grafo cujas arestas são dadas a seguir é representado por suas listas de adjacência.
         0-1 0-2 1-3 1-4 1-5 3-6 3-7 4-7 5-7
    

    Suponha que uma busca em profundidade visita os vértices na seguinte ordem:  0 1 5 7 4 3 6 2.  Em que os ordem aparecem os vizinhos de cada vértice nas listas de adjacência?

  2. Repita o exercício anterior supondo que os vértices são visitados na ordem  0 1 4 3 2 5 6 7
  3. [Sedgewick 18.11, p.91]  Existem 13! diferentes permutações dos vértices do grafo definido pelas arestas a seguir [veja figura 18.8, p.87, de Sedgewick)].
         0-1 0-9 1-4 1-9 2-7 2-10 2-12 3-12 5-12 6-10 6-12 7-10 8-11
    

    Quantas dessas permutações coincidem com a ordem em que os vértices do grafo poderiam ser visitados pela função DIGRAPHdfs se usarmos a versão da função dfsR para listas de adjacência?  (Sugestão: Considere todas as ordens em que os vértices podem aparecer nas listas de adjacência.)

  4. O seguinte algoritmo iterativo executa uma busca em profundidade?  As funções STACKinit, STACKpush, STACKpop e STACKempty manipulam uma pilha de vértices:  STACKinit cria uma pilha vazia, STACKpush coloca um vértice na pilha, STACKpop retira um vértice da pilha e STACKempty devolve 1 se a pilha está vazia.  (Compare o código com a implementação da busca em largura a ser estudada adiante.)
         #include "STACK.h"
         static int conta, pre[maxV];
         void DIGRAPHdfs?( Digraph G) { 
            Vertex v;
            conta = 0;
            for (v = 0; v < G->V; v++) pre[v] = -1;
            for (v = 0; v < G->V; v++)
               if (pre[v] == -1)
                  dfs?( G, v);
         }
         void dfs?( Digraph G, Vertex v) { 
            Vertex w;
            STACKinit( G->A);
            pre[s] = conta++; 
            STACKpush( s); 
            while (!STACKempty( )) {
               v = STACKpop( ); 
               for (w = 0; w < G->V; w++)
                  if (G->adj[v][w] == 1)
                     if (pre[w] == -1) { 
                        pre[w] = conta++; 
                        STACKpush( w); 
                     }
            }
         }
    
  5. [Versão Iterativa da Busca em Profundidade[Sedgewick 18.61, p.132]  Escreva uma versão iterativa da função dfsR para digrafos representados por listas de adjacência.  
  6. [Versão Iterativa, Matriz de Adjacência[Sedgewick p.126]  Escreva uma versão iterativa da função dfsR para digrafos representados por matriz de adjacência.   (Este exercício exige apenas uma adaptação simples do exercício anterior.) 

Perguntas e respostas

Valid HTML 4.01 Strict Valid CSS!