Arcos de arborescência

Examine o código a seguir que implementa a busca em profundidade.

#define MAXV 100 //número máximo de vértices
int G[MAXV][MAXV]; //grafo representado por matriz de adjacência
int ordemvisit[MAXV]; //marca a ordem de visitação dos vértices
int pai[MAXV]; //vetor de pai, pai de X é pai[X]
int n; //número de vértices neste grafo
int count; //contador

//Busca em profundidade em um digrafo
//vértices estão númerados de 0 até n-1
void dfsDigrafo(){
   int v;
   count = 0;
   
   for(v = 0; v < n; ++v) //ninguém foi visitado
      ordemvisit[v] = -1;
   
   for(v = 0; v < n; ++v){ //roda todos os vértices

      if( ordemvisit[v] == -1 ){ //se ainda não foi visitado

         pai[v] = v; //é pai dele mesmo, pois é a raiz da arborescência

         dfs(v); //faz a busca para esse vértice

      }
   }
}


//Busca em profundidade a partir de um vértice origem
void dfs(int v){ 
   int i;

   ordemvisit[v] = count++; //atual está visitado

   for(int i = 0; i < n; ++i){ //rodar todas as possíveis adjacências de v

      if (G[v][i] == 1 && ordemvisit[i] == -1){ //existe aresta e ainda não visitou
  
         pai[i] = v; //v é pai de i

         dfs(i); //visita esse vértice
      }
   }
}

O arco v-i que dfs percorre para visitar um vértice i pela primeira vez é conhecido como arco de arborescência (= tree arc).

Suponha, por um momento, que todo vértice de nosso digrafo G pode ser atingido a partir do vértice 0, ou seja, que todo vértice é término de um caminho que começa em 0. (Esse é o caso, por exemplo, se G é um grafo conexo.) Então, ao fim da execução de dfsDigrafo, o conjunto dos arcos de arborescência define uma arborescência com raiz 0. Dizemos que essa é a arborescência de busca em profundidade (= DFS tree) gerada por dfsDigrafo.

Se algum vértice de nosso digrafo G não pode ser alcançado a partir do vértice 0, o conjunto dos arcos de arborescência define várias arborescências, disjuntas uma da outra. Dizemos que esse conjunto de arborescências é a floresta de busca em profundidade (= DFS forest) gerada por dfsDigrafo. É claro que a floresta de busca em profundidade contém todos os vértices de G.

Nota: A expressão "arborescência de busca" não é usual. É mais comum dizer "árvore de busca". Mas no presente texto a palavra "árvore" é reservada para um conceito ligeiramente diferente. A expressão "floresta de busca" é duplamente infeliz: ela entra em choque com "arborescência de busca" e com o conceito usual de "floresta".

A função acima registra a floresta de busca em profundidade no vetor de pais pai.

Arcos de retorno, descendentes e cruzados

A relação entre a floresta de busca em profundidade e os arcos do digrafo que não estão na floresta pode ser em parte descrita pelo vetor ordemvisit:

- Se v-w é um arco descendente então ordemvisit[v] < ordemvisit[w]. - Se v-w é um arco de retorno (em particular, um arco-pai) então ordemvisit[v] > ordemvisit[w].
- Se v-w é um arco cruzado então ordemvisit[v] > ordemvisit[w].

No caso de digrafos simétricos, a classificação dos arcos é bem mais simples, pois não há arcos cruzados:

Propriedade da DFS em Grafos Simétricos: Depois de uma busca em profundidade num digrafo simétrico, todo arco que não pertence à floresta de busca é um arco de retorno ou um arco descendente.
Essa propriedade garante que depois de uma busca em profundidade num digrafo simétrico, todo arco v-w tal que pai[w] é diferente de v e pai[v] é diferente de w pode ser assim classificado:

- se ordemvisit[v] > ordemvisit[w] então v-w é um arco de retorno;
- se ordemvisit[v] < ordemvisit[w] então v-w é um arco descendente.

Exercícios para Fixação

1. Escreva a função dfs para grafos representados por lista de adjacências.
2. Esta frase: " que todo vértice é término de um caminho que começa em 0. (Esse é o caso, por exemplo, se G é um grafo conexo.)", está correta?. Porque?
3. Para que serve essa linha: "pai[v] = v;" na função dfsDigrafo()?

Referência: IME