Algoritmos para Grafos  |  Índice

Busca em profundidade

Um algoritmo de busca (ou de varredura) é qualquer algoritmo que visita todos os vértices de um grafo andando pelos arcos de um vértice a outro.  Há muitas maneiras de fazer uma tal busca.  Cada algoritmo de busca é caracterizado pela ordem em que visita os vértices.

Este capítulo introduz o poderoso algoritmo de busca em profundidade (= depth-first search), ou busca DFS.  Trata-se de uma generalização do algoritmo que estudamos no capítulo Acessibilidade.  Lá o objetivo era decidir se um vértice está ao alcance de outro.  Aqui, é objetivo é visitar todos os vértices e numerá-los na ordem em que são descobertos.

A busca em profundidade não resolve um problema específico. Ela é apenas um arcabouço, ou pré-processamento, para a resolução eficiente de vários problemas concretos.  A busca DFS nos ajuda a compreender o grafo com que estamos lidando, revelando sua forma e reunindo informações (representadas pela numeração dos vértices) que ajudam a responder perguntas sobre o grafo.

A busca em profundidade está relacionada com expressões como pré-ordem, exploração de labirintos, exploração Trémaux, fio de Ariadne (no mito de Teseu e o Minotauro), etc.

Busca DFS

O algoritmo de busca DFS visita todos os vértices e todos os arcos do grafo numa determinada ordem e atribui um número a cada vértice: o k-ésimo vértice descoberto recebe o número k .

A função GRAPHdfs() abaixo é uma implementação do algoritmo.  A busca poderia começar por qualquer vértice, mas é natural começá-la pelo vértice 0.  A numeração dos vértices é registrada em um vetor  pre[]  indexado pelos vértices.

Para simplificar o código, trataremos o vetor pre[] como variável global e suporemos que o número de vértices não passa de 1000.  (Veja abaixo o exercício Alocação dinâmica.) Também trataremos como variável global o contador cnt usada para a numeração:

static int cnt;
int pre[1000];

/* A função GRAPHdfs() faz uma busca em profundidade 
   no grafo G.

   Ela atribui um número de ordem pre[x] a 
   cada vértice x 
   de modo que 
   o k-ésimo vértice descoberto receba o número de ordem k. 
   (Código inspirado no programa 18.3
   de Sedgewick.) */

void GRAPHdfs( Graph G) 
{ 
   cnt = 0;
   for (vertex v = 0; v < G->V; ++v) 
      pre[v] = -1;
   for (vertex v = 0; v < G->V; ++v)
      if (pre[v] == -1) 
         dfsR( G, v); // começa nova etapa
}

A função GRAPHdfs() é apenas um invólucro; a busca propriamente dita é realizada pela função recursiva dfsR().  Em geral, nem todos os vértices estão ao alcance do primeiro vértice visitado em GRAPHdfs(), e portanto a função dfsR() precisa ser invocada várias vezes por GRAPHdfs().  Cada uma dessas invocações define uma etapa da busca.

/* A função dfsR() visita 
   todos os vértices de G 
   que podem ser alcançados a partir do vértice v
   sem passar por vértices já descobertos.

   A função atribui cnt+k a pre[x]
   se x é o k-ésimo vértice descoberto.
   (O código supõe que G 
   é representado por listas de adjacência.) */

static void dfsR( Graph G, vertex v) 
{ 
   pre[v] = cnt++; 
   for (link a = G->adj[v]; a != NULL; a = a->next) {
      vertex w = a->w;
      if (pre[w] == -1)
         dfsR( G, w); 
   }
}

Convém esclarecer os termos visitar e descobrir que usamos até aqui de maneira informal.  Dizemos que um vértice x é visitado toda vez que pre[x] é consultado, isto é, comparado com -1. Um vértice x é descoberto quando visitado pela primeira vez, ocasião em que pre[x], que valia -1, recebe o valor corrente de cnt. Um vértice x já foi visitado se e somente se pre[x] é diferente de -1. 

Cada etapa da busca pode ser resumida assim:  (a) escolha um vértice não descoberto v e (b) visite todos os vértices que estão ao alcance de v mas ainda não foram visitados.  No passo (a), qualquer vértice não descoberto pode ser escolhido para fazer o papel de v. A função GRAPHdfs() escolhe os vértices seguindo a ordem 0, 1, 2, etc., mas poderia ter usado qualquer outra ordem.  Da mesma forma, a ordem em que os vizinhos de v são visitados na função dfsR() não é importante.

Qual a diferença entre a função GRAPHdfs() e a função GRAPHreach() que estudamos no capítulo Acessibilidade?  Há apenas duas pequenas diferenças:  (1) GRAPHdfs() visita todos os vértices do grafo, enquando GRAPHreach() visita apenas os que estão ao alcance de um dado vértice s  e  (2) GRAPHdfs() atribui um rótulo numérico diferente a cada vértice, enquanto GRAPHreach() usa apenas os rótulos 0 e 1.

Exemplo A.  Considere o grafo G definido pelos arcos  0-1 1-2 1-3 2-4 2-5 .   Veja a matriz de adjacências (com - no lugar de 0) e as listas de adjacência do grafo:

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

Segue o rastreamento (= trace) de uma execução de GRAPHdfs(G).  As linhas da tabela que começam com v-w registram o momento em que a função dfsR() percorre o arco v-w, ou seja, o momento em que a função se depara com w ao examinar os vizinhos de v. Cada expressão da forma dfsR(G,w) registra uma invocação de dfsR().  Cada nova invocação de dfsR() é indicada por uma indentação apropriada da linha.

v-w dfsR(G,w)

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

As linhas em que aparece apenas um vértice v representam o fim da execução de dfsR(G,v), ou seja, a morte da encarnação dfs(G,v) de dfsR().  Para determinar o estado finaldo vetor pre[], basta examinar a sequência de expressões da forma dfsR(G,w) no rastreamento acima:

    w   0 1 2 4 5 3 
pre[w]  0 1 2 3 4 5

Podemos reescrever esse vetor colocando em ordem crescente a primeira linha da tabela:

    w   0 1 2 3 4 5
pre[w]  0 1 2 5 3 4

Nesse exemplo, a busca tem apenas uma etapa.

Exemplo B.  Seja G o grafo definido pelos arcos  1-0 0-4 0-5 4-2 4-3 .   Veja as listas de adjacências do grafo:

0:  4 5
1:  0
2:  
3:  
4:  2 3
5:  

Segue o rastreamento de uma execução de GRAPHdfs(G).  As linhas da tabela que começam com v-w registram o momento em que a função dfsR() percorre o arco v-w. Se a ponta final do arco ainda não foi visitada, a linha da tabela também registra a invocação de dfsR(G,w). Um vértice v isolado numa linha da tabela representa o fim da encarnação dfsR(G,v) de dfsR().

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

1 dfsR(G,1)    
1-0            
  0            
1              

O bloco de linhas que começa com dfsR(G,0) corresponde à primeira etapa da busca. O bloco que começa com dfsR(G,1) corresponde à segunda etapa.  É fácil deduzir pre[] do rastreamento pois a função numera em sequência os vértices w que aparecem nas expressões da forma dfsR(G,w). Assim, o estado final do vetor pre[] é

    w   0 4 2 3 5 1
pre[w]  0 1 2 3 4 5

Se preferir, a primeira linha da tabela pode ser colocada em ordem crescente:

    w   0 1 2 3 4 5
pre[w]  0 5 2 3 1 4

Exemplo C.  Seja G o grafo definido pelos arcos  2-0 2-3 2-4 0-1 0-4 3-4 3-5 4-1 4-5 5-1 .  Veja as listas de adjacência do grafo:

0:  1 4
1:  
2:  0 3 4
3:  4 5
4:  1 5
5:  1

Segue o rastreamento da execução de GRAPHdfs(G). (É fácil conferir o rastreamento pois os vizinhos de cada vértice aparecem em ordem crescente na lista de adjacência.)

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

O bloco de linhas que começa com dfsR(G,0) corresponde à primeira etapa da busca. O bloco que começa com dfsR(G,2) corresponde à segunda etapa.  Para deduzir o estado final do vetor pre[], basta observar a sequência de valores de w nas expressões da forma dfsR(G,w):

    w   0 1 4 5 2 3
pre[w]  0 1 2 3 4 5

Exemplo D.  Este exemplo ilustra uma busca em profundidade num grafo não-dirigido.  O grafo G tem conjunto de arestas  0-2 0-5 0-7 1-7 2-6 3-4 3-5 4-5 4-6 4-7 e portanto suas listas de adjacências são

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

Segue o rastreamento de uma execução de GRAPHdfs(G).  As linhas da tabela que começam com v-w registram o momento em que a função dfsR() percorre o arco v-w (esse arco é uma metade de uma aresta do grafo).

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

Nesse exemplo, a busca tem uma só etapa.  (Os pontos servem apenas para deixar o alinhamento vertical mais visível.)  Como vimos nos exemplos anteriores, é fácil deduzir do rastreamento o estado final do vetor pre[]:

    v   0 2 6 4 3 5 7 1
pre[v]  0 1 2 3 4 5 6 7

A tabela pode ser reescrita com a primeira linha em ordem crescente:

    v   0 1 2 3 4 5 6 7
pre[v]  0 7 1 4 3 5 2 6

Desempenho da busca DFS

A função GRAPHdfs() examina o leque de saída de cada vértice uma só vez. Portanto, cada arco é examinado uma só vez. Assim, se o grafo tem V vértices e A arcos, GRAPHdfs() consome tempo proporcional a

V + A .

(Esse consumo é proporcional ao tamanho do grafo e portanto também ao tempo necessário para ler todas as listas de adjacência.)  No caso de grafos representados por matriz de adjacências, a função GRAPHdfs(), combinada com a versão apropriada de dfsR(), consome tempo proporcional a

V²

quando aplicada a um grafo com V vértices.  (Esse consumo é proporcional ao tempo necessário para ler a matriz de adjacências.)  Se o grafo é esparso, esta segunda versão é mais lenta que a primeira.

Pré-ordem

A ordem em que a função GRAPHdfs() descobre os vértices do grafo é chamada pré-ordem (= preorder).  Para obter a permutação dos vértices em pré-ordem basta inverter o vetor pre[]:

  vertex vv[1000];
  for (vertex v = 0; v < G->V; ++v)
     vv[pre[v]] = v;
  for (int i = 0; i < G->V; ++i)
     printf( "%d ", vv[i]);

Para ilustrar, considere o exemplo D acima.  O estado final de pre[] informa que os vértice foram descobertos na ordem  0 2 6 4 3 5 7 1.  Esta é, então, a permutação dos vértices em pré-ordem.

É claro que a pré-ordem depende da sequência em que os vértices aparecem nas listas de adjacência. Se alterarmos essa sequência, a pré-ordem também se altera, mas continua merecendo o nome pré-ordem.  Essas variações da pré-ordem são especialmente evidentes quando o grafo é representado por sua matriz de adjacências, pois nesse caso dfsR() pode percorrer as linhas da matriz em diferentes ordens (como da direita para a esquerda, por exemplo).

Resumindo, dizemos que qualquer implementação do algoritmo de busca em profundidade descobre os vértices do grafo em pré-ordem.

Se o grafo for uma árvore radicada, a permutação dos vértices em pré-ordem pode ser descrita recursivamente:  visite a raiz; depois, para cada vizinho w da raiz, visite, em pré-ordem, a sub­árvore que tem raiz w.