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

a) 1-5-3-1
b) 0-1-0
são ciclos. Já os caminhos abaixo, embora fechados, não são ciclos:

a) 1-5-3-1-0-1
b) 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.

Procurando ciclos: primeiro algoritmo

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

//Devolve 1 se tem ciclo no digrafo G, devolve 0 caso contrário.
int G[MAXV][MAXV];//G está representando um grafo por matriz de adjancências
int n; //n é o número total de vértices (que são números de 0 a N-1)
int cicloDigrafo(){
 int v, dest, saida;
 for( v = 0 ; v < n ; ++v ){
  for( dest = 0 ; dest < n ; ++dest ){
   if( G[v][dest] == 1 && Path(dest,v)){
    return 1;
   }
  }
 }
 return 0;
}

A função Path no código acima está implementada no artigo de caminhos em digrafos. A função análoga para grafos é bem mais complexa porque é preciso evitar os ciclos triviais.

int G[MAXV][MAXV];//G está representando um grafo por matriz de adjancências
int n; //n é o número total de vértices (que são números de 0 a N-1)
//A função a seguir remove uma Aresta
void removeAresta(int o,int d){
 G[o][d] = 0;
}

//A função a seguir insere uma Aresta
void insereAresta(int o,int d){
 G[o][d] = 1;
}

//A função a seguir devolve 1 se existe um ciclo não-trivial no grafo G, caso contrário devolve 0.
int cicloGrafo(){
 int v, w;
 int dest;
 int saida;

 for( v = 0 ; v < n ; ++v ){
  for( dest = 0 ; dest < n ; ++dest ){
   if( G[v][dest] == 1 ){
    if ( v < dest ){
     removeAresta(dest,v);
     saida = Path(dest,v);
     insereAresta(dest,v);
     if(saida == 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. Função para Digrafos:

#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 n; //número de vértices neste grafo
int count; //contador

//A função abaixo devolve 1 se o digrafo G tem um ciclo, 0 caso contrário
int cicloDigrafo(){
 int v;
 for( v = 0 ; v < n ; ++ v )
  ordemvisit[v] = -1;
 count = 0;
 for( v = 0 ; v < n ; ++ v )
  if( ordemvisit[v] == -1 )
   if(cicloR(v) == 1)
    return 1;
 return 0;
}

//A função abaixo devolve 1 quando encontra um ciclo ao percorrer G a partir de v
int cicloR(int v){
 int p;
 ordemvisit[v] = count++;
 for( p = 0 ; p < n ; ++p ){
  if(G[v][p] == 1 && ordemvisit[p] == -1){
   if(cicloR(p) == 1) return 1;
  }
  else if(ordemvisit[p] < ordemvisit[v]) return 1;
 }
 return 0;
}

A função cicloGrafo abaixo procura ciclos não-triviais em grafos. Para evitar ciclos triviais, a função precisa ter acesso à floresta DFS.

#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

//A função abaixo devolve 1 se o grafo G tem um ciclo não-trivial, 0 caso contrário
int cicloGrafo(){
 int v;
 for( v = 0 ; v < n ; ++ v )
  ordemvisit[v] = -1;
 count = 0;
 for( v = 0 ; v < n ; ++ v ){
  if( ordemvisit[v] == -1 ){
   pai[v] = v;
   if(ciclo3R(v) == 1)
    return 1;
  }
 }
 return 0;
}

//A função abaixo devolve 1 quando encontra um ciclo não-trivial ao percorrer G a partir de v
int cicloR(int v){
 int p;
 ordemvisit[v] = count++;
 for( p = 0 ; p < n ; ++p ){
  if(G[v][p] == 1 && ordemvisit[p] == -1){
   pai[p] = p;
   if(cicloR(p) == 1) return 1;
  }
  else if(ordemvisit[p] < ordemvisit[v] && p != pai[v]) 
   return 1;
 }
 return 0;
}

Exercícios para Fixação
1. Escreva uma função que conte o número de ciclos em um grafo.
2. Escreva o algoritmo eficiente para digrafos usando lista de adjacências.
3. Escreva o algoritmo eficiente para grafos usando lista de adjacências.
4. Execute o algoritmo cicloDigrafo eficiente e marque os principais passos para o digrafo da figura:

5. Execute o algoritmo cicloGrafo eficiente e marque os principais passos para o grafo da figura:

6. Escreva a função removeAresta para lista de adjacências
7. Escreva a função insereAresta para lista de adjacências

Referência: IME