Localizando todos os ciclos em um gráfico direcionado

Como posso encontrar (iterar) TODOS os ciclos em um gráfico direcionado de / para um determinado nó?

Por exemplo, eu quero algo como isto:

A->B->A
A->B->C->A

mas não: B-> C-> B

Encontrei esta página na minha pesquisa e, como os ciclos não são os mesmos que os componentes fortemente conectados, continuei pesquisando e, finalmente, encontrei um algoritmo eficiente que lista todos os ciclos (elementares) de um gráfico direcionado. É de Donald B. Johnson e o artigo pode ser encontrado no seguinte link:

http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF

Uma implementação java pode ser encontrada em:

http://normalisiert.de/code/java/elementaryCycles.zip

Uma demonstração do algoritmo de Johnson no Mathematica pode ser encontrada aqui , a implementação pode ser baixada da direita ( "Baixar código do autor" ).

Nota: Na verdade, existem muitos algoritmos para esse problema. Alguns deles estão listados neste artigo:

http://dx.doi.org/10.1137/0205007

Segundo o artigo, o algoritmo de Johnson é o mais rápido.

A primeira pesquisa profunda com retorno deve funcionar aqui. Mantenha uma matriz de valores booleanos para acompanhar se você visitou um nó antes. Se você ficar sem novos nós para acessar (sem bater em um nó que você já esteve), basta voltar atrás e tentar uma ramificação diferente.

O DFS é fácil de implementar se você tiver uma lista de adjacências para representar o gráfico. Por exemplo, adj [A] = {B, C} indica que B e C são filhos de A.

Por exemplo, pseudo-código abaixo. "start" é o nó do qual você inicia.

dfs(adj,node,visited):  
  if (visited[node]):  
    if (node == start):  
      "found a path"  
    return;  
  visited[node]=YES;  
  for child in adj[node]:  
    dfs(adj,child,visited)
  visited[node]=NO;

Chame a função acima com o nó inicial:

visited = {}
dfs(adj,start,visited)

Primeiro de tudo - você realmente não quer tentar encontrar literalmente todos os ciclos, porque se houver 1, haverá um número infinito deles. Por exemplo, ABA, ABABA etc. Ou pode ser possível unir 2 ciclos em um ciclo semelhante a 8 etc., etc ... A abordagem significativa é procurar todos os chamados ciclos simples - aqueles que não se cruzam, exceto no ponto inicial / final. Então, se desejar, você pode gerar combinações de ciclos simples.

Um dos algoritmos de linha de base para encontrar todos os ciclos simples em um gráfico direcionado é o seguinte: Faça uma travessia profunda de todos os caminhos simples (aqueles que não se cruzam) no gráfico. Sempre que o nó atual tem um sucessor na pilha, um ciclo simples é descoberto. Consiste nos elementos da pilha que começam com o sucessor identificado e terminam com o topo da pilha. O primeiro percurso de profundidade de todos os caminhos simples é semelhante à primeira pesquisa de profundidade, mas você não marca / grava os nós visitados que não sejam os que estão atualmente na pilha como pontos de parada.

O algoritmo de força bruta acima é terrivelmente ineficiente e, além disso, gera várias cópias dos ciclos. No entanto, é o ponto de partida de vários algoritmos práticos que aplicam várias melhorias para melhorar o desempenho e evitar a duplicação de ciclos. Fiquei surpreso ao descobrir há algum tempo que esses algoritmos não estão prontamente disponíveis em livros didáticos e na web. Então, pesquisei e implementei 4 desses algoritmos e 1 algoritmo para ciclos em gráficos não direcionados em uma biblioteca Java de código aberto aqui: http://code.google.com/p/niographs/ .

BTW, desde que mencionei gráficos não direcionados: O algoritmo para esses é diferente. Construa uma árvore de abrangência e, em seguida, todas as arestas que não fazem parte da árvore formam um ciclo simples, juntamente com algumas arestas. Os ciclos encontrados desta maneira formam a chamada base de ciclo. Todos os ciclos simples podem ser encontrados combinando 2 ou mais ciclos básicos distintos. Para mais detalhes, por exemplo, consulte: http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf .

A escolha mais simples que encontrei para resolver esse problema foi usar a lib python chamada networkx.

Ele implementa o algoritmo de Johnson mencionado na melhor resposta desta pergunta, mas simplifica sua execução.

Em resumo, você precisa do seguinte:

import networkx as nx
import matplotlib.pyplot as plt

# Create Directed Graph
G=nx.DiGraph()

# Add a list of nodes:
G.add_nodes_from(["a","b","c","d","e"])

# Add a list of edges:
G.add_edges_from([("a","b"),("b","c"), ("c","a"), ("b","d"), ("d","e"), ("e","a")])

#Return a list of cycles described as a list o nodes
list(nx.simple_cycles(G))

Resposta: [['a', 'b', 'd', 'e'], ['a', 'b', 'c']]

Esclarecer:

1. Os Componentes fortemente conectados encontrarão todos os subgráficos que possuem pelo menos um ciclo, nem todos os ciclos possíveis no gráfico. por exemplo, se você pegar todos os componentes fortemente conectados e recolher / agrupar / mesclar cada um deles em um nó (ou seja, um nó por componente), obterá uma árvore sem ciclos (na verdade, um DAG). Cada componente (que é basicamente um subgráfico com pelo menos um ciclo) pode conter muitos mais ciclos possíveis internamente, portanto, o SCC NÃO encontrará todos os ciclos possíveis, encontrará todos os grupos possíveis que têm pelo menos um ciclo e, se você agrupar eles, o gráfico não terá ciclos.

2. para encontrar todos os ciclos simples em um gráfico, como outros mencionados, o algoritmo de Johnson é um candidato.

Recebi isso como uma pergunta de entrevista uma vez. Suspeito que isso tenha acontecido com você e você está vindo aqui para obter ajuda. Divida o problema em três perguntas e fica mais fácil.

1. como você determina a próxima rota válida
2. como você determina se um ponto foi usado
3. como você evita atravessar o mesmo ponto novamente

Problema 1) Use o padrão do iterador para fornecer uma maneira de iterar os resultados da rota. Um bom lugar para colocar a lógica para obter a próxima rota é provavelmente o "moveNext" do seu iterador. Para encontrar uma rota válida, isso depende da sua estrutura de dados. Para mim, era uma tabela sql cheia de possibilidades válidas de rota, então tive que criar uma consulta para obter os destinos válidos, de acordo com uma fonte.

Problema 2) Empurre cada nó à medida que os encontrar em uma coleção à medida que os obtém, isso significa que você pode ver se está "dobrando de volta" sobre um ponto com muita facilidade, interrogando a coleção que está construindo em tempo real.

Problema 3) Se, a qualquer momento, você voltar a dobrar, poderá retirar as coisas da coleção e "fazer backup". Então, a partir desse ponto, tente "avançar" novamente.

Hack: se você estiver usando o Sql Server 2008, existem algumas novas coisas de "hierarquia" que você pode usar para resolver rapidamente isso se você estruturar seus dados em uma árvore.

As variantes baseadas em DFS com bordas traseiras encontrarão ciclos de fato, mas em muitos casos NÃO serão ciclos mínimos . Em geral, o DFS indica que há um ciclo, mas não é bom o suficiente para encontrar ciclos. Por exemplo, imagine 5 ciclos diferentes compartilhando duas arestas. Não há uma maneira simples de identificar ciclos usando apenas DFS (incluindo variantes de retorno).

De fato, o algoritmo de Johnson fornece todos os ciclos simples únicos e possui boa complexidade de tempo e espaço.

Mas se você deseja apenas encontrar ciclos MÍNIMOS (o que significa que pode haver mais de um ciclo passando por qualquer vértice e estamos interessados ​​em encontrar um mínimo) E seu gráfico não é muito grande, tente usar o método simples abaixo. É MUITO simples, mas bastante lento em comparação com o de Johnson.

Portanto, uma das maneiras absolutamente mais fáceis de encontrar ciclos MÍNIMOS é usar o algoritmo de Floyd para encontrar caminhos mínimos entre todos os vértices usando a matriz de adjacência. Esse algoritmo não é nem de longe tão ótimo quanto o de Johnson, mas é tão simples e seu loop interno é tão rígido que, para gráficos menores (<= 50-100 nós), faz absolutamente sentido usá-lo. A complexidade do tempo é O (n ^ 3), a complexidade do espaço O (n ^ 2) se você usar o rastreamento dos pais e O (1) se não usar. Primeiro de tudo, vamos encontrar a resposta para a pergunta, se houver um ciclo. O algoritmo é simples. Abaixo está um trecho de código em Scala.

  val NO_EDGE = Integer.MAX_VALUE / 2

  def shortestPath(weights: Array[Array[Int]]) = {
    for (k <- weights.indices;
         i <- weights.indices;
         j <- weights.indices) {
      val throughK = weights(i)(k) + weights(k)(j)
      if (throughK < weights(i)(j)) {
        weights(i)(j) = throughK
      }
    }
  }

Originalmente, esse algoritmo opera no gráfico de borda ponderada para encontrar todos os caminhos mais curtos entre todos os pares de nós (daí o argumento de pesos). Para que funcione corretamente, é necessário fornecer 1 se houver uma borda direcionada entre os nós ou NO_EDGE, caso contrário. Após a execução do algoritmo, você pode verificar a diagonal principal, se houver valores menores que NO_EDGE do que este nó participará de um ciclo de duração igual ao valor. Todos os outros nós do mesmo ciclo terão o mesmo valor (na diagonal principal).

Para reconstruir o próprio ciclo, precisamos usar a versão ligeiramente modificada do algoritmo com o rastreamento dos pais.

  def shortestPath(weights: Array[Array[Int]], parents: Array[Array[Int]]) = {
    for (k <- weights.indices;
         i <- weights.indices;
         j <- weights.indices) {
      val throughK = weights(i)(k) + weights(k)(j)
      if (throughK < weights(i)(j)) {
        parents(i)(j) = k
        weights(i)(j) = throughK
      }
    }
  }

A matriz dos pais inicialmente deve conter o índice de vértices de origem em uma célula de aresta, se houver uma aresta entre os vértices e -1 caso contrário. Após o retorno da função, para cada borda, você terá referência ao nó pai na árvore de caminho mais curto. E então é fácil recuperar os ciclos reais.

Em suma, temos o seguinte programa para encontrar todos os ciclos mínimos

  val NO_EDGE = Integer.MAX_VALUE / 2;

  def shortestPathWithParentTracking(
         weights: Array[Array[Int]],
         parents: Array[Array[Int]]) = {
    for (k <- weights.indices;
         i <- weights.indices;
         j <- weights.indices) {
      val throughK = weights(i)(k) + weights(k)(j)
      if (throughK < weights(i)(j)) {
        parents(i)(j) = parents(i)(k)
        weights(i)(j) = throughK
      }
    }
  }

  def recoverCycles(
         cycleNodes: Seq[Int], 
         parents: Array[Array[Int]]): Set[Seq[Int]] = {
    val res = new mutable.HashSet[Seq[Int]]()
    for (node <- cycleNodes) {
      var cycle = new mutable.ArrayBuffer[Int]()
      cycle += node
      var other = parents(node)(node)
      do {
        cycle += other
        other = parents(other)(node)
      } while(other != node)
      res += cycle.sorted
    }
    res.toSet
  }

e um pequeno método principal apenas para testar o resultado

  def main(args: Array[String]): Unit = {
    val n = 3
    val weights = Array(Array(NO_EDGE, 1, NO_EDGE), Array(NO_EDGE, NO_EDGE, 1), Array(1, NO_EDGE, NO_EDGE))
    val parents = Array(Array(-1, 1, -1), Array(-1, -1, 2), Array(0, -1, -1))
    shortestPathWithParentTracking(weights, parents)
    val cycleNodes = parents.indices.filter(i => parents(i)(i) < NO_EDGE)
    val cycles: Set[Seq[Int]] = recoverCycles(cycleNodes, parents)
    println("The following minimal cycle found:")
    cycles.foreach(c => println(c.mkString))
    println(s"Total: ${cycles.size} cycle found")
  }

e a saída é

The following minimal cycle found:
012
Total: 1 cycle found

No caso de gráfico não direcionado, um artigo publicado recentemente ( lista ideal de ciclos e caminhos st em gráficos não direcionados ) oferece uma solução assintoticamente ideal. Você pode lê-lo aqui http://arxiv.org/abs/1205.2766 ou aqui http://dl.acm.org/citation.cfm?id=2627951 Eu sei que isso não responde à sua pergunta, mas desde o título de sua pergunta não mencionar direção, ainda pode ser útil para a pesquisa do Google

Inicie no nó X e verifique todos os nós filhos (os nós pai e filho são equivalentes se não forem direcionados). Marque esses nós filhos como filhos de X. Em qualquer nó filho A, marque seus filhos como filhos de A, X ', onde X' é marcado como 2 passos de distância.). Se você pressionar X mais tarde e marcar como filho de X '', isso significa que X está em um ciclo de 3 nós. Voltar para o pai é fácil (como está, o algoritmo não tem suporte para isso, então você encontrará o pai com X ').

Nota: Se o gráfico não for direcionado ou tiver arestas bidirecionais, esse algoritmo se tornará mais complicado, supondo que você não deseje atravessar a mesma aresta duas vezes durante um ciclo.

Se o que você deseja é encontrar todos os circuitos elementares em um gráfico, você pode usar o algoritmo EC, de JAMES C. TIERNAN, encontrado em um artigo desde 1970.

O algoritmo EC muito original , como eu consegui implementá-lo em php (espero que não haja erros, é mostrado abaixo). Pode encontrar loops também, se houver algum. Os circuitos nesta implementação (que tenta clonar o original) são os elementos diferentes de zero. Zero aqui significa inexistência (nulo como o conhecemos).

Além disso, segue uma outra implementação que dá ao algoritmo mais independência, isso significa que os nós podem começar de qualquer lugar, inclusive de números negativos, por exemplo, -4, -3, -2, etc.

Nos dois casos, é necessário que os nós sejam seqüenciais.

Você pode precisar estudar o artigo original, James C. Tiernan Elementary Circuit Algorithm

<?php
echo  "<pre><br><br>";

$G = array(
        1=>array(1,2,3),
        2=>array(1,2,3),
        3=>array(1,2,3)
);


define('N',key(array_slice($G, -1, 1, true)));
$P = array(1=>0,2=>0,3=>0,4=>0,5=>0);
$H = array(1=>$P, 2=>$P, 3=>$P, 4=>$P, 5=>$P );
$k = 1;
$P[$k] = key($G);
$Circ = array();


#[Path Extension]
EC2_Path_Extension:
foreach($G[$P[$k]] as $j => $child ){
    if( $child>$P[1] and in_array($child, $P)===false and in_array($child, $H[$P[$k]])===false ){
    $k++;
    $P[$k] = $child;
    goto EC2_Path_Extension;
}   }

#[EC3 Circuit Confirmation]
if( in_array($P[1], $G[$P[$k]])===true ){//if PATH[1] is not child of PATH[current] then don't have a cycle
    $Circ[] = $P;
}

#[EC4 Vertex Closure]
if($k===1){
    goto EC5_Advance_Initial_Vertex;
}
//afou den ksana theoreitai einai asfales na svisoume
for( $m=1; $m<=N; $m++){//H[P[k], m] <- O, m = 1, 2, . . . , N
    if( $H[$P[$k-1]][$m]===0 ){
        $H[$P[$k-1]][$m]=$P[$k];
        break(1);
    }
}
for( $m=1; $m<=N; $m++ ){//H[P[k], m] <- O, m = 1, 2, . . . , N
    $H[$P[$k]][$m]=0;
}
$P[$k]=0;
$k--;
goto EC2_Path_Extension;

#[EC5 Advance Initial Vertex]
EC5_Advance_Initial_Vertex:
if($P[1] === N){
    goto EC6_Terminate;
}
$P[1]++;
$k=1;
$H=array(
        1=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
        2=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
        3=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
        4=>array(1=>0,2=>0,3=>0,4=>0,5=>0),
        5=>array(1=>0,2=>0,3=>0,4=>0,5=>0)
);
goto EC2_Path_Extension;

#[EC5 Advance Initial Vertex]
EC6_Terminate:
print_r($Circ);
?>

então esta é a outra implementação, mais independente do gráfico, sem saltar e sem valores de matriz; em vez disso, usa chaves de matriz, o caminho, o gráfico e os circuitos são armazenados como chaves de matriz (use valores de matriz, se desejar, altere apenas o necessário linhas). O gráfico de exemplo começa em -4 para mostrar sua independência.

<?php

$G = array(
        -4=>array(-4=>true,-3=>true,-2=>true),
        -3=>array(-4=>true,-3=>true,-2=>true),
        -2=>array(-4=>true,-3=>true,-2=>true)
);


$C = array();


EC($G,$C);
echo "<pre>";
print_r($C);
function EC($G, &$C){

    $CNST_not_closed =  false;                          // this flag indicates no closure
    $CNST_closed        = true;                         // this flag indicates closure
    // define the state where there is no closures for some node
    $tmp_first_node  =  key($G);                        // first node = first key
    $tmp_last_node  =   $tmp_first_node-1+count($G);    // last node  = last  key
    $CNST_closure_reset = array();
    for($k=$tmp_first_node; $k<=$tmp_last_node; $k++){
        $CNST_closure_reset[$k] = $CNST_not_closed;
    }
    // define the state where there is no closure for all nodes
    for($k=$tmp_first_node; $k<=$tmp_last_node; $k++){
        $H[$k] = $CNST_closure_reset;   // Key in the closure arrays represent nodes
    }
    unset($tmp_first_node);
    unset($tmp_last_node);


    # Start algorithm
    foreach($G as $init_node => $children){#[Jump to initial node set]
        #[Initial Node Set]
        $P = array();                   // declare at starup, remove the old $init_node from path on loop
        $P[$init_node]=true;            // the first key in P is always the new initial node
        $k=$init_node;                  // update the current node
                                        // On loop H[old_init_node] is not cleared cause is never checked again
        do{#Path 1,3,7,4 jump here to extend father 7
            do{#Path from 1,3,8,5 became 2,4,8,5,6 jump here to extend child 6
                $new_expansion = false;
                foreach( $G[$k] as $child => $foo ){#Consider each child of 7 or 6
                    if( $child>$init_node and isset($P[$child])===false and $H[$k][$child]===$CNST_not_closed ){
                        $P[$child]=true;    // add this child to the path
                        $k = $child;        // update the current node
                        $new_expansion=true;// set the flag for expanding the child of k
                        break(1);           // we are done, one child at a time
            }   }   }while(($new_expansion===true));// Do while a new child has been added to the path

            # If the first node is child of the last we have a circuit
            if( isset($G[$k][$init_node])===true ){
                $C[] = $P;  // Leaving this out of closure will catch loops to
            }

            # Closure
            if($k>$init_node){                  //if k>init_node then alwaya count(P)>1, so proceed to closure
                $new_expansion=true;            // $new_expansion is never true, set true to expand father of k
                unset($P[$k]);                  // remove k from path
                end($P); $k_father = key($P);   // get father of k
                $H[$k_father][$k]=$CNST_closed; // mark k as closed
                $H[$k] = $CNST_closure_reset;   // reset k closure
                $k = $k_father;                 // update k
        }   } while($new_expansion===true);//if we don't wnter the if block m has the old k$k_father_old = $k;
        // Advance Initial Vertex Context
    }//foreach initial


}//function

?>

Analisei e documentei a CE, mas infelizmente a documentação está em grego.

Existem duas etapas (algoritmos) envolvidas na localização de todos os ciclos em um DAG.

O primeiro passo é usar o algoritmo de Tarjan para encontrar o conjunto de componentes fortemente conectados.

1. Comece de qualquer vértice arbitrário.
2. DFS desse vértice. Para cada nó x, mantenha dois números, dfs_index [x] e dfs_lowval [x]. dfs_index [x] armazena quando esse nó é visitado, enquanto dfs_lowval [x] = min (dfs_low [k]) em que k são todos os filhos de x que não são os pais diretamente de x na árvore de abrangência do dfs.
3. Todos os nós com o mesmo dfs_lowval [x] estão no mesmo componente fortemente conectado.

O segundo passo é encontrar ciclos (caminhos) dentro dos componentes conectados. Minha sugestão é usar uma versão modificada do algoritmo de Hierholzer.

A ideia é:

1. Escolha qualquer vértice inicial v e siga uma trilha de arestas desse vértice até retornar a v. Não é possível ficar preso em nenhum vértice que não seja v, porque o grau par de todos os vértices garante que, quando a trilha entra em outro vértice w deve haver uma aresta não utilizada deixando w. O tour formado dessa maneira é um tour fechado, mas pode não cobrir todos os vértices e arestas do gráfico inicial.
2. Desde que exista um vértice v que pertença ao passeio atual, mas que tenha arestas adjacentes que não façam parte do passeio, inicie outra trilha de v, seguindo as arestas não utilizadas até retornar a ve junte-se ao passeio formado dessa maneira para o tour anterior.

Aqui está o link para uma implementação Java com um caso de teste:

http://stones333.blogspot.com/2013/12/find-cycles-in-directed-graph-dag.html

http://www.me.utexas.edu/~bard/IP/Handouts/cycles.pdf

Eu tropecei no algoritmo a seguir, que parece ser mais eficiente que o algoritmo de Johnson (pelo menos para gráficos maiores). No entanto, não tenho certeza sobre seu desempenho em comparação com o algoritmo de Tarjan.
Além disso, só verifiquei se há triângulos até agora. Se estiver interessado, consulte "Algoritmos de listagem de arboricidade e subgráfico" de Norishige Chiba e Takao Nishizeki ( http://dx.doi.org/10.1137/0214017 )

Solução Javascript usando listas vinculadas de conjuntos disjuntos. Pode ser atualizado para separar florestas definidas para tempos de execução mais rápidos.

var input = '5\nYYNNN\nYYYNN\nNYYNN\nNNNYN\nNNNNY'
console.log(input);
//above solution should be 3 because the components are
//{0,1,2}, because {0,1} and {1,2} therefore {0,1,2}
//{3}
//{4}

//MIT license, authored by Ling Qing Meng

//'4\nYYNN\nYYYN\nNYYN\nNNNY'

//Read Input, preformatting
var reformat = input.split(/\n/);
var N = reformat[0];
var adjMatrix = [];
for (var i = 1; i < reformat.length; i++) {
    adjMatrix.push(reformat[i]);
}

//for (each person x from 1 to N) CREATE-SET(x)
var sets = [];
for (var i = 0; i < N; i++) {
    var s = new LinkedList();
    s.add(i);
    sets.push(s);
}

//populate friend potentials using combinatorics, then filters
var people =  [];
var friends = [];
for (var i = 0; i < N; i++) {
    people.push(i);
}
var potentialFriends = k_combinations(people,2);
for (var i = 0; i < potentialFriends.length; i++){
    if (isFriend(adjMatrix,potentialFriends[i]) === 'Y'){
        friends.push(potentialFriends[i]);
    }
}


//for (each pair of friends (x y) ) if (FIND-SET(x) != FIND-SET(y)) MERGE-SETS(x, y)
for (var i = 0; i < friends.length; i++) {
    var x = friends[i][0];
    var y = friends[i][1];
    if (FindSet(x) != FindSet(y)) {
        sets.push(MergeSet(x,y));
    }
}


for (var i = 0; i < sets.length; i++) {
    //sets[i].traverse();
}
console.log('How many distinct connected components?',sets.length);



//Linked List data structures neccesary for above to work
function Node(){
    this.data = null;
    this.next = null;
}

function LinkedList(){
    this.head = null;
    this.tail = null;
    this.size = 0;

    // Add node to the end
    this.add = function(data){
        var node = new Node();
        node.data = data;
        if (this.head == null){
            this.head = node;
            this.tail = node;
        } else {
            this.tail.next = node;
            this.tail = node;
        }
        this.size++;
    };


    this.contains = function(data) {
        if (this.head.data === data) 
            return this;
        var next = this.head.next;
        while (next !== null) {
            if (next.data === data) {
                return this;
            }
            next = next.next;
        }
        return null;
    };

    this.traverse = function() {
        var current = this.head;
        var toPrint = '';
        while (current !== null) {
            //callback.call(this, current); put callback as an argument to top function
            toPrint += current.data.toString() + ' ';
            current = current.next; 
        }
        console.log('list data: ',toPrint);
    }

    this.merge = function(list) {
        var current = this.head;
        var next = current.next;
        while (next !== null) {
            current = next;
            next = next.next;
        }
        current.next = list.head;
        this.size += list.size;
        return this;
    };

    this.reverse = function() {
      if (this.head == null) 
        return;
      if (this.head.next == null) 
        return;

      var currentNode = this.head;
      var nextNode = this.head.next;
      var prevNode = this.head;
      this.head.next = null;
      while (nextNode != null) {
        currentNode = nextNode;
        nextNode = currentNode.next;
        currentNode.next = prevNode;
        prevNode = currentNode;
      }
      this.head = currentNode;
      return this;
    }


}


/**
 * GENERAL HELPER FUNCTIONS
 */

function FindSet(x) {
    for (var i = 0; i < sets.length; i++){
        if (sets[i].contains(x) != null) {
            return sets[i].contains(x);
        }
    }
    return null;
}

function MergeSet(x,y) {
    var listA,listB;
    for (var i = 0; i < sets.length; i++){
        if (sets[i].contains(x) != null) {
            listA = sets[i].contains(x);
            sets.splice(i,1);
        }
    }
    for (var i = 0; i < sets.length; i++) {
        if (sets[i].contains(y) != null) {
            listB = sets[i].contains(y);
            sets.splice(i,1);
        }
    }
    var res = MergeLists(listA,listB);
    return res;

}


function MergeLists(listA, listB) {
    var listC = new LinkedList();
    listA.merge(listB);
    listC = listA;
    return listC;
}

//access matrix by i,j -> returns 'Y' or 'N'
function isFriend(matrix, pair){
    return matrix[pair[0]].charAt(pair[1]);
}

function k_combinations(set, k) {
    var i, j, combs, head, tailcombs;
    if (k > set.length || k <= 0) {
        return [];
    }
    if (k == set.length) {
        return [set];
    }
    if (k == 1) {
        combs = [];
        for (i = 0; i < set.length; i++) {
            combs.push([set[i]]);
        }
        return combs;
    }
    // Assert {1 < k < set.length}
    combs = [];
    for (i = 0; i < set.length - k + 1; i++) {
        head = set.slice(i, i+1);
        tailcombs = k_combinations(set.slice(i + 1), k - 1);
        for (j = 0; j < tailcombs.length; j++) {
            combs.push(head.concat(tailcombs[j]));
        }
    }
    return combs;
}

DFS a partir do nó inicial s, acompanhe o caminho do DFS durante a travessia e registre o caminho se encontrar uma borda do nó v no caminho para s. (v, s) é uma extremidade traseira na árvore DFS e, portanto, indica um ciclo contendo s.

Em relação à sua pergunta sobre o ciclo de permutação , leia mais aqui: https://www.codechef.com/problems/PCYCLE

Você pode tentar este código (digite o tamanho e o número dos dígitos):

# include<cstdio>
using namespace std;

int main()
{
    int n;
    scanf("%d",&n);

    int num[1000];
    int visited[1000]={0};
    int vindex[2000];
    for(int i=1;i<=n;i++)
        scanf("%d",&num[i]);

    int t_visited=0;
    int cycles=0;
    int start=0, index;

    while(t_visited < n)
    {
        for(int i=1;i<=n;i++)
        {
            if(visited[i]==0)
            {
                vindex[start]=i;
                visited[i]=1;
                t_visited++;
                index=start;
                break;
            }
        }
        while(true)
        {
            index++;
            vindex[index]=num[vindex[index-1]];

            if(vindex[index]==vindex[start])
                break;
            visited[vindex[index]]=1;
            t_visited++;
        }
        vindex[++index]=0;
        start=index+1;
        cycles++;
    }

    printf("%d\n",cycles,vindex[0]);

    for(int i=0;i<(n+2*cycles);i++)
    {
        if(vindex[i]==0)
            printf("\n");
        else
            printf("%d ",vindex[i]);
    }
}

Versão DFS c ++ para o pseudocódigo na resposta do segundo andar:

void findCircleUnit(int start, int v, bool* visited, vector<int>& path) {
    if(visited[v]) {
        if(v == start) {
            for(auto c : path)
                cout << c << " ";
            cout << endl;
            return;
        }
        else 
            return;
    }
    visited[v] = true;
    path.push_back(v);
    for(auto i : G[v])
        findCircleUnit(start, i, visited, path);
    visited[v] = false;
    path.pop_back();
}