Algoritmos para Grafos  |  Índice

Ciclos e dags

Este capítulo mostra que um grafo é topológico (ou seja, tem uma numeração topológica) se e somente se não tem ciclos. A prova desse fato decorre do algoritmo busca em profundidade: quando aplicado a qualquer grafo, o algoritmo produz um ciclo ou uma numeração topológica.

Detecção de ciclos

Um ciclo num grafo é um caminho fechado. Um par de arcos antiparalelos, por exemplo, induz um ciclo de comprimento 2. A motivação principal deste capítulo é o seguinte

Dizemos que um grafo é acíclico se não tem ciclo algum. É claro que o problema do ciclo não tem solução se o grafo em questão for acíclico. Faz parte do problema decidir se o grafo é acíclico.

Para resolver o problema, podemos tentar encontrar, para cada arco v-w, um caminho de w a v. (Veja a função GRAPHreach() no capítulo Acessibilidade.)  Mas essa solução é muito ineficiente pois a tentativa de encontrar um caminho de w a v refaz boa parte do trabalho já feito na tentativa de encontrar um caminho de vértices próximos a w até vértices próximos a v. Como veremos a seguir, a busca DFS oferece uma maneira bem mais rápida de encontrar um ciclo (ou provar que o grafo é acíclico).

Algoritmo

O seguinte algoritmo decide se uma instância do problema do ciclo tem solução, ou seja, se o grafo em questão tem ciclos. O algoritmo começa por fazer uma busca DFS no grafo. Depois, usa as numerações em pré- e pós-ordem produzidos pela busca para procurar um arco de retorno, pois todo arco de retorno faz parte de um ciclo.

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

/* Esta função decide se o grafo G tem um ciclo. */

bool GRAPHcycle0( Graph G) 
{
   GRAPHdfs( G); // calcula pre[] e post[]

   for (vertex v = 0; v < G->V; ++v) {
      for (link a = G->adj[v]; a != NULL; a = a->next) {
         vertex w = a->w;
         if (post[v] < post[w]) // v-w é de retorno
            return true;
      }
   } 
   // post[v] > post[w] para todo arco v-w
   return false;
}

A função está correta?  Suponha que  post[v] > post[w]  para todo arco v-w. Então post[] é uma numeração anti-topológica. Logo, -post[] é uma numeração topológica. Como grafos topológicos são acíclicos, o return false está correto.

pre  post
v w  v w
 <    >  floresta
 <    >  avanço
 >    <  retorno
 >    >  cruzado

Suponha agora que a função encontra um arco v-w tal que  post[v] < post[w]. Então devemos ter  pre[v] > pre[w],  pois caso contrário o arco v-w seria cruzado direito em relação à floresta DFS que está sendo implicitamente construída e sabemos bem que isso é impossível. Portanto, o arco v-w é de retorno. Em outras palavras, w é ancestral de v na floresta. Logo, existe um caminho de w a v na floresta. Esse caminho, junto com o arco v-w, forma um ciclo simples. (Veja o exercício Arco de retorno versus ciclo no capítulo Florestas DFS.)  Portanto, o return true está correto.

A função GRAPHcycle0() é semelhante à função GRAPHtopol(), que implementa o algoritmo de eliminação iterada de fontes, mas é mais completa que aquela. Se o grafo é topológico, ambas as funções calculam uma numeração topológica. Mas se o grafo não é topológico, apenas GRAPHcycle0() encontra um ciclo.

Exemplo A.  Seja G o grafo da figura. Veja as listas de adjacência do grafo (note que as listas não estão em ordem crescente de nomes):

 0: 1 5
 1:
 2: 3 0
 3: 5 2
 4: 2 3
 5: 4
 6: 0 4 9
 7: 6 8
 8: 7 9
 9: 10 11
10: 12
11: 4 12
12: 9

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

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

6 dfsR(G,6)
6-0
6-4
6-9 dfsR(G,9)
  9-10 dfsR(G,10)
    10-12 dfsR(G,12)
       12-9
       12
    10
  9-11 dfsR(G,11)
    11-4
    11-12
    11
  9
6

7 dfsR(G,7)
7-6
7-8 dfsR(G,8)
  8-7
  8-9
  8
7

No fim da execução de GRAPHdfs( G), temos os seguintes vetores pre[], post[] e pa[]

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

Observe que post[3] < post[5]. Observe também que pre[3] > pre[w] (o que é inevitável, como observamos na análise de GRAPHcycle0()). Logo o arco 3-5 é de retorno e fecha o ciclo  3-5-4-2-3  (verifique o ciclo examinando o vetor pa[]).

O arco 9-12 também é de retorno e fecha o ciclo 12-9-10-12. O arco 8-7 também é de retorno e fecha o ciclo 8-7-8.

Exemplo B.  Seja G o grafo dado pelas seguintes listas e adjacência:

 0: 1 5
 1:
 2: 0 3
 3: 5
 4:
 5: 4
 6: 4 9
 7: 6
 8: 7
 9: 10 11 12
10: 
11: 12
12:

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

0 dfsR(G,0)        
0-1 dfsR(G,1)      
  1                  
0-5 dfsR(G,5)      
  5-4 dfsR(G,4)
    4
  5    
0-6 dfsR(G,6)
  6-4
  6-9 dfsR(G,9)
    9-10 dfsR(G,10)
      10
    9-11 dfsR(G,11)
      11-12 dfsR(G,12)
         12
      11
    9-12
    9
  6
0

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

7 dfsR(G,7)
7-6
7

8 dfsR(G,8)
8-7
8

Portanto, os vetores pre[] e post[] terminam no seguinte estado:

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

O vetor post[] é uma numeração anti-topológica dos vértices. Para conferir essa afirmação, extraia de post[] a permutação

         1  4  5 10 12 11  9  6  0  3  2  7  8

dos vértices e constate que todos os arcos do grafo apontam da direita para a esquerda. Portanto, o grafo é acíclico.

Grafos topológicos versus dags

Não seria difícil acrescentar algumas linhas de código à função GRAPHcycle0() para imprimir um ciclo no caso de resposta true. Podemos dizer então que, ao receber qualquer grafo, a função GRAPHcycle0() produz (1) um ciclo ou (2) uma numeração topológica. Assim, a função GRAPHcycle0() prova o seguinte

Grafos acíclicos também são conhecidos como  dags  (= directed acyclic graphs). O teorema pode ser parafraseado assim: dags e grafos topológicos são a mesma coisa.

Vale a pena chamar a atenção para o caráter complementar das definições dos dois conceitos: a definição de grafo topológico tem um caráter positivo (existe um certo tipo de numeração) enquanto a definição de dag tem um caráter negativo (não existem ciclos).

Se um grafo tem um ciclo, é evidente que não tem numeração topológica. Da mesma forma, se um grafo tem uma numeração topológica, é evidente que não tem ciclos. Portanto, um ciclo é um certificado de inexistência de numeração topológica e uma numeração topológica é um certificado de inexistência de ciclo. Mas isso deixa em aberto a possibilidade de grafos que não têm ciclos nem numeração topológica. O teorema exclui essa possibilidade.

Segue imediatamente do teorema a seguinte caracterização de dois tipos especiais de grafos topológicos. Uma floresta radicada é um dag sem vértices de grau de entrada maior que 1. Uma árvore radicada é um dag em que exatamente um vértice tem grau de entrada 0 e todos os demais têm grau de entrada 1.

Implementação on-the-fly do algoritmo

Ao invocar GRAPHdfs(), a função GRAPHcycle0() examina o grafo todo duas vezes. Embora isso resulte em um algoritmo linear, é preferível obter o mesmo efeito examinando o grafo uma só vez. Para fazer isso, é preciso interromper a busca DFS assim que um ciclo for encontrado. Diremos que essa é a versão on-the-fly de GRAPHcycle0(). (Já fizemos algo semelhante na seção Implementação on-the-fly do algoritmo do capítulo Ciclos e dags.)

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

/* Esta função decide se o grafo G tem um ciclo. */

bool GRAPHcycle( Graph G) 
{ 
   cnt = cntt = 0;
   for (vertex v = 0; v < G->V; ++v)
      pre[v] = post[v] = -1;
   for (vertex v = 0; v < G->V; ++v)
      if (pre[v] == -1) 
         if (dfsRhcy( G, v)) return true;
   return false; 
}

/* A função dfsRhcy() devolve true
   se encontra um ciclo ao percorrer G
   a partir do vértice v
   e devolve false em caso contrário. */

static bool dfsRhcy( 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) {
         if (dfsRhcy( G, w)) 
            return true;
      } else {
         if (post[w] == -1) 
            return true; // base da recursão
      }
   }
   post[v] = cntt++;
   return false;
}

A função está correta?  Suponha inicialmente que a função devolve false. Nesse caso, G é topológico, como mostraremos a seguir. Seja v-w um arco qualquer. No fim da execução da função, todos os elementos do vetor pre[] são diferentes de -1, em particular, pre[v] ≠ -1. Logo, dfsRhcy() foi executado com argumentos (G, v) em algum momento. Essa encarnação de dfsRhcy() deve ter terminado com um return false. Portanto, todos os vizinhos de v foram examinados e todos morreram antes de v. Em particular, a atribuição post[w] = cntt++ foi executada antes da atribuição post[v] = cntt++. Concluímos assim que post[v] > post[w]. Isso vale para todo arco v-w. Portanto, post[] é uma numeração anti-topológica e G é um dag.

pre  post
v w  v w
 <    >  floresta
 <    >  avanço
 >    <  retorno
 >    >  cruzado

Suponha agora que GRAPHcycle() devolve true. Mostraremos que nesse caso o grafo tem um ciclo. Comece por observar que alguma encarnação dfsRhcy(G,v) de dfsRhcy() devolveu true, donde algum vizinho w de v tinha pre[w] ≠ -1 e post[w] ≡ -1, ou seja, w já foi descoberto mas ainda não morreu (a encarnação dfsRhcy(G,w) de dfsRhcy() ainda está viva). Portanto, o intervalo de vida de dfsRhcy(G,w) contém o intervalo de vida de dfsRhcy(G,v). Logo, se a busca DFS não tivesse sido interrompida pelo return true, a atribuição post[v] = cntt++ seria executada antes de post[w] = cntt++ e teríamos  post[v] < post[w]. Segue daí que o arco v-w seria de retorno na floresta DFS que estava sendo (implicitamente) construída. Conclusão: v-w pertence a um ciclo.

(A propósito, observe que o ciclo eventualmente detectado por uma invocação de dfsRhcy() com argumentos (G, v) pode não passar pelo vértice v.)

Desempenho.  A função GRAPHcycle() é linear. O consumo de tempo da função é essencialmente igual ao de uma busca DFS. Assim, num grafo com V vértices e A arcos, o consumo de tempo é da ordem de  A + V  no pior caso. (Se o grafo fosse representado por uma matriz de adjacências, o consumo de tempo seria da ordem de V² no pior caso.)

Exemplo C.  Considere novamente o exemplo A. Veja as listas de adjacência do grafo (note que as listas não estão em ordem crescente de nomes):

 0: 1 5
 1:
 2: 3 0
 3: 5 2
 4: 2 3
 5: 4
 6: 0 4 9
 7: 6 8
 8: 7 9
 9: 10 11
10: 12
11: 4 12
12: 9

Segue o rastreamento da execução de GRAPHcycle( G):

0 dfsRhcy(G,0)        
0-1 dfsRhcy(G,1)      
  1                  
0-5 dfsRhcy(G,5)      
  5-4 dfsRhcy(G,4)    
    4-2 dfsRhcy(G,2)  
      2-3 dfsRhcy(G,3)
        3-5          
        3 return true
      2 return true
    4 return true
  5 return true
0 return true

O arco 3-5 é de retorno e fecha o ciclo 3-5-4-2-3. A título de curiosidade, veja o estado dos vetores pre[] e post[] no fim da execução da função:

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

Ciclo e permutação topológica explícitos.  A função GRAPHcycle() deixa algo a desejar: ela não exibe, explicitamente, um ciclo nem uma numeração topológica. É um bom exercício suprir essa lacuna. Comece por acrescentar o vetor de pais pa[] ao código. Ao encontrar um arco de retorno v-w, basta fazer pa[w] = v para que pa[] descreva um ciclo passando por v-w. Se não houver arco de retorno, post[] é uma numeração anti-topológica.