Algoritmos para Grafos  |  Índice

Florestas DFS

A busca em profundidade deixa uma espécie de rastro ao percorrer um grafo.  Esse rastro é uma floresta radicada.  Pode-se dizer que a floresta é um esqueleto do grafo.  Para registrar a floresta radicada, basta acrescentar duas linhas de código ao par de funções GRAPHdfs() e dfsR() que discutimos no capítulo Busca em profundidade.

Floresta da busca

Examine as funções GRAPHdfs() e dfsR() que implementam uma busca em profundidade.  O arco  v-w  que dfsR() percorre para descobrir o vértice  w  é conhecido como arco de floresta.   No fim da execução de GRAPHdfs(), o conjunto dos arcos de floresta define uma floresta radicada.  Essa é a floresta de busca em profundidade, ou floresta DFS, construída pela função.

Uma floresta DFS contém todos os vértices do grafo e portanto é um sub­grafo gerador.  A floresta DFS se diferencia de outras sub­florestas geradoras do grafo por estar associada a uma numeração do grafo em pré-ordem, que é também uma numeração topológica da floresta.

Uma floresta DFS pode ser confortavelmente representada por um vetor de pais, digamos  pa[0..V-1]:  para cada vértice w,  pa[w] é o pai de w na floresta.  (O vetor de pais é como a trilha de migalhas de pão na conto infantil João e Maria.)  A seguinte função calcula o vetor de pais à medida que numera o grafo em pré-ordem:

static int cnt;
int pre[1000];
vertex pa[1000];

/* A função GRAPHdfs() faz uma busca DFS no grafo G. 
   Ela atribui um número de ordem pre[x] a 
   cada vértice x 
   (o k-ésimo vértice descoberto recebe o número de ordem k) e
   registra a correspondente floresta DFS no vetor de pais pa[]. 
   (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) {
         pa[v] = v; // v é uma raiz da floresta
         dfsR( G, v);
      }
}

/* A função dfsR() visita 
   todos os vértices de G 
   que podem ser alcançados a partir de v
   sem passar por vértices já descobertos.
   Todos esses vértices, e só esses,
   tornam-se   descendentes de v
   na floresta radicada definida por pa[].
   Se x é o k-ésimo vértice descoberto,
   a função atribui cnt+k a pre[x]. 
   (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) {
         pa[w] = v; // v-w é arco da floresta 
         dfsR( G, w); 
      }
   }
}

(O código acima supõe que G é representado por listas de adjacência. Não é difícil adaptar o código para grafos representados por matriz de adjacências.)

O sub­grafo de G representado pelo vetor pa[] é, de fato, uma floresta radicada pois 

1. o vetor pre[] é uma numeração topológica do sub­grafo e
2. no máximo um arco do sub­grafo entra em cada vértice.

Para deduzir essas duas propriedades basta examinar o código com atenção.

A floresta DFS consiste em uma ou mais árvores radicadas.  Cada etapa da busca constrói uma das árvores. A etapa que começa com a linha dfsR( G, v) de GRAPHdfs() constrói uma árvore com raiz v.

Exemplo A. Aplique a função GRAPHdfs() ao grafo G representado pelas seguintes listas de adjacência:

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

Cada lista de adjacência está em ordem crescente, o que torna fácil conferir o rastreamento da execução da função:

v-w dfsR(G,w)

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

Um vértice v isolado numa linha da tabela representa o fim do processamento de v, ou seja, o fim da execução de dfsR(G,v).  As linhas do rastreamento que têm a forma  v-w dfsR(G,w)  mostram que o vetor pa[] estará no seguinte estado no fim da execução da função:

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

Aqui os vértices estão listados na ordem em que foram descobertos, mas a tabela pode ser reescrita colocando a primeira linha em ordem crescente:

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

A floresta DFS consiste em duas árvores: uma tem raiz 0 e a outra tem raiz 2.

Exemplo B. Aplique a função GRAPHdfs() ao grafo G representado pelas seguintes listas de adjacência:

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

Para tornar o exemplo mais interessante, começamos a busca pelo vértice 2 e não pelo vértice 0, como manda o código de GRAPHdfs().  Veja o rastreamento da execução da função:

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

É fácil deduzir do rastreamento o estado final do vetor pa[]. Para cada linha da forma v-w dfsR(G,w) na tabela temos pa[w] = v:

   w   2 7 5 4 1 3 6 0
pa[w]  2 2 7 5 5 1 3 6

Exemplo C. Seja G o grafo não-dirigido representado pelas seguintes listas de adjacência:

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

Veja o rastreamento da execução de GRAPHdfs( G):

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

(Os pontos foram acrescentados apenas para deixar o alinhamento vertical mais visível.)  Basta observar as linhas da forma v-w dfsR(G,w) para deduzir o estado final do vetor de pais:

   0     
   |     
   2     
  / \    
 1   3   
    / \  
   5   4 

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

Essa floresta DFS consiste em uma só árvore, que tem raiz 0.  Às vezes é útil fazer uma figura do grafo que coloque a floresta DFS em destaque. Veja a figura à direita, oriente todos os arcos de cima para baixo, e acrescente os demais arcos do grafo.

Acima, abaixo, à esquerda e à direita

Digamos que x e y são dois vértices da floresta DFS de um grafo.  Como em qualquer floresta radicada, x pode ser ancestral, descendente, ou primo de y. (Um vértice é primo de outro se não for ancestral nem descendente do outro.)  Além disso, em consequência da ordem em que os vizinhos de cada vértice são visitados durante a busca DFS, podemos distinguir um vértice mais velho de um vértice mais novo. Assim, se x e y são primos e pre[] é a numeração em pré-ordem associada à floresta então

• x é primo mais velho, ou esquerdo, de y  se  pre[x] < pre[y]  e
• x é primo mais novo, ou direito, de y  se  pre[x] > pre[y].

É claro que essas relações são mutuamente inversas: x é primo mais velho de y se e somente se y é primo mais novo de x.

Essas relações genealógicas entre os vértices de uma floresta DFS poderiam também ser descritas por uma metáfora espacial: acima corresponde a ancestral, abaixo corresponde a descendente, à esquerda corresponde a primo mais velho e à direita corresponde a primo mais novo.

Como saber, algoritmicamente, se um dado vértice é ancestral, descendente, primo mais velho ou primo mais novo de outro?  A aplicação simplória das definições não leva a um algorimo rápido pois exige que a floresta seja percorrida a partir de um dos vértices à procura do outro, e isso pode consumir muito tempo. O capítulo seguinte dará uma resposta eficiente depois de introduzir a numeração em pós-ordem.

Arcos de retorno, de avanço, e cruzados

Dada uma floresta DFS de um grafo, cada arco v-w do grafo pertence a um de três tipos, conforme a posição relativa de v e w na floresta:

• se w é um descendente de v então v-w é de avanço (= forward arc = down arc);
• se w é um ancestral de v então v-w é de retorno (= back arc);
• se w é um primo de v então v-w é cruzado (= cross arc).

Cabem duas observações:  1. Usualmente, quando se diz arco de avanço fica subentendido que o arco não é de floresta, embora todos os arcos da floresta sejam também de avanço.  2. As pontas de um arco cruzado podem estar em diferentes árvores da floresta.

É fácil deduzir do código de dfsR() que os arcos cruzados são todos esquerdos, ou seja, que não existe arco v-w tal que w é primo direito de v.  Em outras palavras, se v-w é um arco e w é primo de v então w é primo esquerdo de v.

Essa propriedade tem a seguinte consequência imediata:  grafos não-dirigidos não têm arcos cruzados,

Exemplo D. Na figura abaixo, os arcos de floresta são vermelhos, os de retorno são verdes, os de avanço são roxos, e os cruzados são azuis.  (O exemplo foi copiado dos slides de 2011 de José Coelho de Pina.) 

Exemplo E. Em relação à floresta DFS calculada no exemplo B, os arcos do grafo que não pertencem à floresta têm a seguinte classificação:

0-2  retorno
0-4  cruzado
4-5  retorno
4-7  retorno
5-7  retorno
6-2  retorno
6-4  cruzado
7-3  avanço

Exemplo F. Em relação à floresta DFS calculada no grafo não-dirigido do exemplo C, os arcos que não pertencem à floresta têm os seguintes tipos:

0-1  avanço
0-5  avanço
1-0  retorno
1-2  retorno
2-0  retorno
2-4  avanço
3-2  retorno
4-2  retorno
4-3  retorno

Como acontece com todos os grafo não-dirigidos, não há arcos cruzados.