Ciclos em grafos e digrafos

Ciclos são estruturas muito importantes em digrafos. Saber encontrar um ciclo num digrafo (ou decidir que o digrafo não tem ciclos) é uma habilidade muito útil. O problema é um pouco mais difícil em grafos se quisermos ignorar os ciclos de comprimento 2.

Ciclos

Um ciclo (= cycle) num digrafo é um caminho fechado sem vértices repetidos, exceto o último (que coincide com o primeiro). É claro que todo ciclo tem comprimento pelo menos 2.

Dizemos que um arco v-w pertence a um dado ciclo (ou que o ciclo passa pelo arco) se o vértice w é o sucessor de v no ciclo. Todos os arcos de um ciclo apontam no mesmo sentido, de um vértice do ciclo para o seu sucessor. Há quem goste de enfatizar esse fato dizendo ciclo dirigido em vez de ciclo.

No digrafo 0-1 0-5 1-0 1-5 2-4 3-1 5-3, os caminhos a seguir são ciclos.

     1-5-3-1
     0-1-0

Já os caminhos abaixo, embora fechados, não são ciclos.

     1-5-3-1-0-1
     1

Ciclos em grafos

Um ciclo é trivial se tem comprimento 2. Num grafo, ciclos triviais são ignorados porque usam os dois arcos de uma mesma aresta. Assim, só estamos interessados nos ciclos de comprimento pelo menos 3.

Exercícios 1

Escreva uma função que verifique se uma sequência seq[0..k] de vértices de um digrafo é um ciclo. A função deve devolver 1 se a sequência é um ciclo e 0 em caso contrário. Faça duas versões da função: uma supõe que o digrafo é dado por sua matriz de adjacência e outra supõe que o digrafo é dado por listas de adjacência.
Repita o exercício anterior com "grafo" no lugar de "digrafo".
Escreva uma função que receba um digrafo sem sorvedouros e imprima um ciclo do digrafo.
Digamos que dois ciclos são equivalentes se têm o mesmo conjunto de vértices e o mesmo conjunto de arcos. (Por exemplo, o ciclo 4-3-5-4 é equivalente a 3-5-4-3.) Faça uma lista de todos os ciclos dois-a-dois não equivalentes do digrafo abaixo.
```
     0-5 5-4 7-8 4-3 0-2 9-11 0-1 11-12 3-5 9-12 9-10 10-9 6-4 0-6
```
Num grafo (ou seja, num digrafo simétrico), convém dizer que dois ciclos são equivalentes não só se forem equivalentes no sentido do exercício anterior, mas também se um dos ciclos for o inverso do outro (por exemplo, 4-3-5-4 e 4-5-3-4 são equivalentes). Faça uma lista de todos os ciclos não triviais dois-a-dois não equivalentes do grafo definido pelo conjunto de arestas abaixo.
```
     0-5 5-4 7-8 4-3 0-2 9-11 0-1 11-12 3-5 9-12 9-10 6-4 0-6
```
Faça uma lista de todos os ciclos não triviais dois-a-dois não equivalentes do grafo definido pelo conjunto de arestas abaixo.
```
     3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4
```

Procurando ciclos: primeiro algoritmo

A seguinte função implementa uma maneira óbvia mas pouco eficiente de encontrar um ciclo num digrafo. A ideia é procurar, para cada arco v-w, um ciclo que passe por v-w.

/* A função devolve 1 se existe um ciclo no digrafo G e devolve 0 em caso contrário. */

int digraphcycle( Digraph G) { 
   Vertex v; link p; int output;
   for (v = 0; v < G->V; v++) 
      for (p = G->adj[v]; p != NULL; p = p->next) {
         output = DIGRAPHpath( G, p->w, v);
         if (output == 1) return 1; 
      }
   return 0;
}

Consumo de tempo: Num digrafo com V vértices e A arcos, o consumo de tempo é A vezes o consumo de tempo de DIGRAPHpath. Portanto, o consumo de tempo no pior caso é da ordem de A V² se o digrafo for representado por uma matriz de adjacência, e da ordem de A (A+V) se o digrafo for representado por listas de adjacência.

Grafos

Procurar ciclos em grafos é mais difícil porque evita os ciclos triviais.

/* A função devolve 1 se existe um ciclo não trivial no grafo G e devolve 0 em caso contrário. */

int graphcycle( Graph G) { 
   Vertex v, w; link p; int output;
   for (v = 0; v < G->V; v++)
      for (p = G->adj[v]; p != NULL; p = p->next) {
         w = p->w;
         if (v < w) {
            GRAPHremoveE( G, w, v);
            output = DIGRAPHpath( G, w, v);
            GRAPHinsertE( G, w, v);
            if (output == 1) return 1;
         }
      }
   return 0;
}

O "if (v < w)" está lá apenas para evitar que se faça a mesma verificação duas vezes, uma para o arco v-w e outra para o arco w-v. (Veja o conceito de equivalência de ciclos em grafos num dos execícios acima.)

Procurando ciclos: algoritmo eficiente

O algoritmo de busca em profundidade permite encontrar ciclos de maneira muito eficiente. O algoritmo abaixo tem por base a seguinte observação: em relação a qualquer floresta de busca em profundidade,

todo arco de retorno pertence a um ciclo e
todo ciclo tem um arco de retorno.

O algoritmo é uma extensão da enumeração combinada em vértices em pré- e pós-ordem:

/* Vamos supor que nossos digrafos têm no máximo maxV vértices. */

static int conta, pre[maxV], pos[maxV];

/* A função devolve 1 se o digrafo G tem um ciclo e devolve 0 em caso contrário. */

int DIGRAPHcycle( Digraph G) { 
   Vertex v;
   conta = 0;
   for (v = 0; v < G->V; v++)
      pre[v] = pos[v] = -1;
   for (v = 0; v < G->V; v++)
      if (pre[v] == -1) 
         if (cycleR( G, v) == 1) return 1;
   return 0;
}

/* A função cycleR devolve 1 quando encontra um ciclo ao percorrer G a partir do vértice v e devolve 0 em caso contrário. */

int cycleR( Digraph G, Vertex v) { 
   link p;
   pre[v] = conta++;
   for (p = G->adj[v]; p != NULL; p = p->next) {
      Vertex w = p->w;
      if (pre[w] == -1) {
         if (cycleR( G, w) == 1) return 1;
      } else if (pos[w] == -1) return 1;
   }
   pos[v] = conta++;
   return 0;
}

Considere os testes if (pre[w] == -1) e if (pos[w] == -1). Se pre[w] != -1 mas pos[w] == -1 então certamente teremos pre[w] < pre[v] < pos[v] < pos[w] no fim da execução do algoritmo (supondo que o algoritmo não seja interrompido antes do fim da busca DFS) e portanto o arco v-w é de retorno. Nesse caso, v-w pertence a um ciclo. Por outro lado, se pre[w] != -1 e pos[w] != -1 então certamente teremos pre[w] < pos[w] < pre[v] < pos[v] no fim da execução do algoritmo e portanto o arco v-w é cruzado. Nesse caso, v-w não pertence a um ciclo.

Consumo de tempo: Num digrafo com V vértices e A arcos, o consumo de tempo é essencialmente igual ao de uma busca em profundidade. Portanto, o consumo de tempo no pior caso é da ordem de V² se o digrafo for representado por uma matriz de adjacência e da ordem de A + V se o digrafo for representado por listas de adjacência.

Grafos

Agora considere o caso especial de digrafos simétricos, ou seja, grafos. A função GRAPHcycle abaixo procura ciclos não triviais em grafos. Para evitar ciclos triviais, a função precisa ter acesso à floresta DFS, representada pelo vetor parent.

static int conta, pre[maxV], pos[maxV];
static Vertex parent[maxV];

/* A função devolve 1 se o grafo G tem um ciclo não trivial e devolve 0 em caso contrário. */

int GRAPHcycle( Graph G) { 
   Vertex v;
   conta = 0;
   for (v = 0; v < G->V; v++)
      pre[v] = pos[v] = -1;
   for (v = 0; v < G->V; v++)
      if (pre[v] == -1) {
         parent[v] = v;
         if (cycle3R( G, v) == 1) return 1;
      }
   return 0;
}

/* A função cycle3R devolve 1 quando encontra um ciclo não trivial ao percorrer G a partir do vértice v. */

int cycle3R( Graph G, Vertex v) { 
   link p;
   pre[v] = conta++;
   for (p = G->adj[v]; p != NULL; p = p->next) {
      Vertex w = p->w;
      if (pre[w] == -1) {
         parent[w] = v;
         if (cycle3R( G, w) == 1) return 1;
      } else if (w != parent[v]) return 1;
   }
   pos[v] = conta++;
   return 0;
}

No caso em que pre[w] != -1 , teremos necesssariamente pos[w] == -1 pois grafos não têm arcos cruzados. Assim, pre[w] != -1 então v-w pertence a um ciclo, restando apenas verificar se o ciclo é trivial.

Exercícios 2

A função GRAPHcycle é capaz de encontrar um ciclo de comprimento maior que 2 num digrafo não simétrico?
Escreva uma versão de DIGRAPHcycle que imprima um ciclo imediatamente antes de devolver 1. Compile e teste sua função.
Escreva uma versão de GRAPHcycle que não usa o vetor de pais parent. Em vez disso, passa para cycle3R o arco que dá origem a mais uma instância recursiva de exploração do grafo. Assim, a linha if (cycle3R(G,w) == 1) return 1 no código de cycle3R será substituída por if (cycle3R(G,v,w) == 1) return 1.
Escreva uma versão de GRAPHcycle que imprima um ciclo não trivial imediatamente antes de devolver 1. Compile e teste sua função.
Escreva uma função que conte o número de ciclos em um grafo.