Pré-ordem e pós-ordem intercaladas

[Enunciado]  É interessante intercalar as permutações em pré- e pós-ordem.  Para isso, basta trocar a variável cntt por cnt, ou seja, usar o mesmo contador para registrar as descobertas e as mortes dos vértices. 

static int cnt, pre[1000], post[1000];

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

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

Os vetores pre[] e post[] contam a história da busca:  cada vértice v é descoberto no instante pre[v] e morre no instante post[v].  É claro que  pre[v] < post[v]  e v está vivo durante o intervalo de tempo (pre[v],post[v]).

Se colocarmos os vértices na ordem indicada por pre[] e post[], teremos uma permutação dupla em que cada vértice aparece exatamente duas vezes:  a primeira aparição corresponde à descoberta do vértice e a segunda à sua morte.  Num grafo com vértices 0 .. 5, por exemplo, podemos ter a seguinte permutação dupla:

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

Se olharmos as primeiras aparições dos vértices, veremos os vértices em pré-ordem;  se olharmos as segundas aparições, veremos os vértices em pós-ordem.

É claro que os intervalos de vida (pre,post) de dois quaisquer vértices x e y não se cruzam, ou seja, que o padrão

x .. y .. x .. y

na permutação dupla é impossível.  Assim, dados dois quaisquer vértices x e y, temos apenas duas possibilidades: ou os intervalos (pre,post) dos dois vértices são disjuntos ou encaixados.  A primeira possibilidade corresponde ao padrão

x .. x .. y .. y

e é descrita pela relação post[x] < pre[y].  A segunda possibilidade corresponde ao padrão

x .. y .. y .. x

e é descrita pelas relações pre[x] < pre[y] e post[y] < post[x].   (Esses padrões são os mesmos da ordem de entrada e saída em uma pilha.)

Exemplo.  Aplique a versão com um só contador de GRAPHdfs() ao grafo da figura. Suponha que o grafo está representado por sua matriz de adjacências.   No fim da execução da função teremos a floresta DFS da figura abaixo e os vetores pre[] e post[] estarão no seguinte estado:

     v    0  1  2  3  4  5
 pre[v]   0  1  8  9  3  4
post[v]   7  2 11 10  6  5

Isso corresponde à seguinte permutação dupla dos vértices:

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

Para tornar essa permutação mais legível, podemos marcar a primeira aparição de cada vértice com um parêntese esquerdo e a segunda com um parêntese direito:

(  (     (  (           (  (     
0  1  1  4  5  5  4  0  2  3  3  2
      )        )  )  )        )  )

Classificação DFS dos arcos

Uma busca em profundidade em um grafo G define uma floresta DFS.  Em relação a essa floresta, os arcos de G são de quatro tipos, como já dissemos em outro capítulo: arcos de floresta, arcos de avanço, arcos de retorno, e arcos cruzados.

Um arco v-w é de floresta se e somente se pa[w] = v.  Se v-w não é de floresta, seu tipo pode ser determinado a partir das numerações intercaladas pre[] e post[]:

• v-w é de avanço se e somente se  pre[v] < pre[w]  e  post[v] > post[w]  (isso corresponde ao padrão v w w v);
• v-w é de retorno se e somente se  pre[v] > pre[w]  e  post[v] < post[w]  (isso corresponde ao padrão w v v w);
• v-w é cruzado se e somente se  pre[v] > post[w]  (isso corresponde ao padrão w w v v).

Portanto, um arco v-w é de avanço se w foi descoberto e morreu durante a vida de v.  Um arco v-w é de retorno se v foi descoberto e morreu enquanto w estava vivo.  Um arco v-w é cruzado se w foi descoberto e morreu antes que v fosse descoberto.