Algoritmos para Grafos, via Sedgewick  |  Índice remissivo

"A circle is a figure with 0 corners and only one side."

— From a high school paper

Ciclos em grafos e digrafos

Ciclos são caminhos fechados quase simples de comprimento pelo menos 2.  Em grafos, os ciclos de comprimento 2 não são considerados "válidos".

Ciclos

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

Dizemos que um arco v-w pertence a um dado ciclo 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 lugar do nosso "ciclo".

No digrafo  0-1 0-5 1-0 1-5 2-4 3-1 5-3,  os caminhos

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

são ciclos.   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, pois usam os dois arcos de uma mesma aresta.

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.
2. Repita o exercício anterior com "grafo" no lugar de "digrafo".
3. [Bom!]  Escreva uma função que receba um digrafo sem sorvedouros e imprima um ciclo do digrafo.
4. 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

5. 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

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 abaixo 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;
}

A função análoga para grafos é bem mais complexa porque é preciso evitar os ciclos triviais.

/* A função abaixo 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;
}

Procurando ciclos: algoritmo eficiente

A estratégia da 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 código abaixo usa o vetor de rótulos lbl da maneira um pouco diferente da empregada na discussão da busca em profundidade:  lbl[v] terá valor -1 se o vértice v ainda não foi visitado, valor -2 se v já foi visitado mas seus vizinhos ainda não foram todos visitados, e valor -3 se v e todos os seus vizinhos já foram visitados.

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

static int lbl[maxV];

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

int DIGRAPHcycle (Digraph G) { 
   Vertex v;
   for (v = 0; v < G->V; v++) lbl[v] = -1;
   for (v = 0; v < G->V; v++)
      if (lbl[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. */

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

[Uma versão anterior do código estava errada…  O erro foi apontado por Juliana de Melo Bezerra do ITA.]

Agora considere o caso especial de grafos (ou seja, digrafos simétricos). A função GRAPHcycle abaixo procura ciclos não triviais em grafos. Como o digrafo é simétrico, não é necessário distinguir entre os valores -2 e -3 dos rótulos lbl. Para evitar ciclos triviais, a função precisa ter acesso à floresta DFS, representada pelo vetor parent. 

static int lbl[maxV];
static Vertex parent[maxV];

/* A função abaixo 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;
   for (v = 0; v < G->V; v++) lbl[v] = -1;
   for (v = 0; v < G->V; v++)
      if (lbl[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;
   lbl[v] = -2;
   for (p = G->adj[v]; p != NULL; p = p->next) {
      Vertex w = p->w;
      if (lbl[w] == -1) {
         parent[w] = v;
         if (cycle3R(G, w) == 1) return 1;
      }
      else if (w != parent[v]) return 1;
   }
   return 0;
}

Exercícios

7. Que acontece se suprimirmos  "if (lbl[w] == -2)"  no código de DIGRAPHcycle?  Mesma pergunta para GRAPHcycle.
8. A função GRAPHcycle é capaz de encontrar um ciclo não trivial num digrafo não simétrico?
9. Escreva uma versão de GRAPHcycle que não usa o vetor de pais parent mas compensa isso adotando o protótipo

   int cycle3R (Graph G, Arc e);

   para a função cycle3R. 

10. Escreva uma versão de DIGRAPHcycle que imprima um ciclo imediatamente antes de devolver 1.  Compile e teste sua função. 
11. Escreva uma versão de GRAPHcycle que imprima um ciclo não trivial imediatamente antes de devolver 1.  Compile e teste sua função. 
12. Escreva uma função que conte o número de ciclos em um grafo.