Encontrar todos los ciclos en un gráfico dirigido

¿Cómo puedo encontrar (iterar) TODOS los ciclos en un gráfico dirigido desde / hacia un nodo dado?

Por ejemplo, quiero algo como esto:

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

pero no: B-> C-> B

Encontré esta página en mi búsqueda y dado que los ciclos no son los mismos que los componentes fuertemente conectados, seguí buscando y finalmente, encontré un algoritmo eficiente que enumera todos los ciclos (elementales) de un gráfico dirigido. Es de Donald B. Johnson y el documento se puede encontrar en el siguiente enlace:

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

Una implementación de Java se puede encontrar en:

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

Una demostración de Mathematica del algoritmo de Johnson se puede encontrar aquí , la implementación se puede descargar desde la derecha ( "Descargar código de autor" ).

Nota: En realidad, hay muchos algoritmos para este problema. Algunos de ellos se enumeran en este artículo:

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

Según el artículo, el algoritmo de Johnson es el más rápido.

La primera búsqueda en profundidad con retroceso debería funcionar aquí. Mantenga una matriz de valores booleanos para realizar un seguimiento de si visitó un nodo anteriormente. Si te quedas sin nuevos nodos para ir (sin golpear un nodo que ya has estado), entonces retrocede e intenta con una rama diferente.

El DFS es fácil de implementar si tiene una lista de adyacencia para representar el gráfico. Por ejemplo, adj [A] = {B, C} indica que B y C son hijos de A.

Por ejemplo, pseudocódigo a continuación. "inicio" es el nodo desde el que comienza.

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;

Llame a la función anterior con el nodo de inicio:

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

En primer lugar, realmente no desea intentar encontrar literalmente todos los ciclos porque si hay 1, entonces hay un número infinito de esos. Por ejemplo, ABA, ABABA, etc. O puede ser posible unir 2 ciclos en un ciclo similar a 8, etc., etc. El enfoque significativo es buscar todos los llamados ciclos simples, aquellos que no se cruzan excepto en el punto inicial / final. Entonces, si lo desea, puede generar combinaciones de ciclos simples.

Uno de los algoritmos de línea de base para encontrar todos los ciclos simples en un gráfico dirigido es este: Realice un recorrido en profundidad de todos los caminos simples (aquellos que no se cruzan) en el gráfico. Cada vez que el nodo actual tiene un sucesor en la pila, se descubre un ciclo simple. Consiste en los elementos en la pila que comienzan con el sucesor identificado y terminan con la parte superior de la pila. El primer recorrido en profundidad de todas las rutas simples es similar a la primera búsqueda en profundidad, pero no marca / registra nodos visitados distintos de los que están actualmente en la pila como puntos de parada.

El algoritmo de fuerza bruta anterior es terriblemente ineficiente y, además, genera múltiples copias de los ciclos. Sin embargo, es el punto de partida de múltiples algoritmos prácticos que aplican varias mejoras para mejorar el rendimiento y evitar la duplicación de ciclos. Me sorprendió descubrir hace algún tiempo que estos algoritmos no están disponibles en los libros de texto y en la web. Así que investigué un poco e implementé 4 algoritmos y 1 algoritmo para ciclos en gráficos no dirigidos en una biblioteca Java de código abierto aquí: http://code.google.com/p/niographs/ .

Por cierto, ya que mencioné gráficos no dirigidos: el algoritmo para ellos es diferente. Construya un árbol de expansión y luego cada borde que no sea parte del árbol forma un ciclo simple junto con algunos bordes del árbol. Los ciclos encontrados de esta manera forman una llamada base de ciclo. Todos los ciclos simples se pueden encontrar combinando 2 o más ciclos básicos distintos. Para más detalles ver, por ejemplo, esto: http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf .

La opción más simple que encontré para resolver este problema fue usar la lib llamada python networkx.

Implementa el algoritmo de Johnson mencionado en la mejor respuesta de esta pregunta, pero es bastante simple de ejecutar.

En resumen, necesitas lo siguiente:

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))

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

Para aclarar:

1. Strongly Connected Components encontrará todos los subgrafos que tienen al menos un ciclo en ellos, no todos los ciclos posibles en el gráfico. por ejemplo, si toma todos los componentes fuertemente conectados y contrae / agrupa / fusiona cada uno de ellos en un nodo (es decir, un nodo por componente), obtendrá un árbol sin ciclos (un DAG en realidad). Cada componente (que es básicamente un subgrafo con al menos un ciclo) puede contener muchos más ciclos posibles internamente, por lo que SCC NO encontrará todos los ciclos posibles, encontrará todos los grupos posibles que tengan al menos un ciclo, y si agrupa ellos, entonces el gráfico no tendrá ciclos.

2. Para encontrar todos los ciclos simples en un gráfico, como otros mencionaron, el algoritmo de Johnson es un candidato.

Una vez me dieron esto como una pregunta de entrevista, sospecho que esto te ha sucedido y que vienes aquí por ayuda. Divide el problema en tres preguntas y se vuelve más fácil.

1. ¿Cómo se determina la siguiente ruta válida?
2. ¿Cómo se determina si se ha utilizado un punto?
3. ¿Cómo evitas cruzar el mismo punto nuevamente?

Problema 1) Use el patrón iterador para proporcionar una forma de iterar los resultados de la ruta. Un buen lugar para poner la lógica para obtener la siguiente ruta es probablemente el "moveNext" de su iterador. Para encontrar una ruta válida, depende de su estructura de datos. Para mí, era una tabla sql llena de posibilidades de ruta válidas, así que tuve que construir una consulta para obtener los destinos válidos dada una fuente.

Problema 2) Empuje cada nodo a medida que los encuentre en una colección a medida que los obtiene, esto significa que puede ver si está "duplicando" un punto muy fácilmente al interrogar la colección que está construyendo sobre la marcha.

Problema 3) Si en algún momento ves que te estás duplicando, puedes sacar cosas de la colección y "hacer una copia de seguridad". Luego, a partir de ese momento, intente "avanzar" nuevamente.

Hack: si está usando Sql Server 2008, hay algunas cosas nuevas de "jerarquía" que puede usar para resolver esto rápidamente si estructura sus datos en un árbol.

Las variantes basadas en DFS con bordes traseros encontrarán ciclos de hecho, pero en muchos casos NO serán ciclos mínimos . En general, DFS le da la señal de que hay un ciclo, pero no es lo suficientemente bueno como para encontrar ciclos. Por ejemplo, imagine 5 ciclos diferentes que comparten dos aristas. No hay una manera simple de identificar ciclos usando solo DFS (incluidas las variantes de retroceso).

De hecho, el algoritmo de Johnson ofrece todos los ciclos simples únicos y tiene una buena complejidad de tiempo y espacio.

Pero si solo desea encontrar ciclos MÍNIMOS (lo que significa que puede haber más de un ciclo atravesando cualquier vértice y estamos interesados ​​en encontrar los mínimos) Y su gráfico no es muy grande, puede intentar usar el método simple a continuación. Es MUY simple pero bastante lento en comparación con el de Johnson.

Por lo tanto, uno de los absolutamente manera más fácil de encontrar ciclos mínima es utilizar el algoritmo de Floyd para encontrar caminos mínimos entre todos los vértices utilizando matriz de adyacencia. Este algoritmo no es tan óptimo como el de Johnson, pero es tan simple y su bucle interno es tan estrecho que para gráficos más pequeños (<= 50-100 nodos) tiene sentido usarlo. La complejidad temporal es O (n ^ 3), la complejidad espacial O (n ^ 2) si usa el seguimiento principal y O (1) si no lo hace. En primer lugar, busquemos la respuesta a la pregunta si hay un ciclo. El algoritmo es muy simple. A continuación se muestra un fragmento en 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, este algoritmo funciona en un gráfico de borde ponderado para encontrar todas las rutas más cortas entre todos los pares de nodos (de ahí el argumento de los pesos). Para que funcione correctamente, debe proporcionar 1 si hay un borde dirigido entre los nodos o NO_EDGE de lo contrario. Después de que se ejecute el algoritmo, puede verificar la diagonal principal, si hay valores inferiores a NO_EDGE que este nodo participa en un ciclo de longitud igual al valor. Todos los demás nodos del mismo ciclo tendrán el mismo valor (en la diagonal principal).

Para reconstruir el ciclo en sí mismo, necesitamos usar una versión ligeramente modificada del algoritmo con el seguimiento principal.

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

La matriz de los padres inicialmente debe contener el índice de vértice de origen en una celda de borde si hay un borde entre los vértices y -1 de lo contrario. Después de que la función regrese, para cada borde tendrá referencia al nodo padre en el árbol de ruta más corto. Y luego es fácil recuperar los ciclos reales.

En general, tenemos el siguiente programa para encontrar todos los 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
  }

y un pequeño método principal solo para probar el 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")
  }

y la salida es

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

En el caso del gráfico no dirigido, un artículo publicado recientemente ( Lista óptima de ciclos y rutas st en gráficos no dirigidos ) ofrece una solución asintóticamente óptima. Puede leerlo aquí http://arxiv.org/abs/1205.2766 o aquí http://dl.acm.org/citation.cfm?id=2627951 Sé que no responde a su pregunta, pero desde el título de su pregunta no menciona la dirección, aún podría ser útil para la búsqueda de Google

Comience en el nodo X y verifique todos los nodos secundarios (los nodos primarios y secundarios son equivalentes si no están dirigidos). Marque esos nodos hijos como hijos de X. Desde cualquier nodo hijo A, marque hijos de ser hijos de A, X ', donde X' está marcado como a 2 pasos de distancia). Si luego presiona X y lo marca como hijo de X '', eso significa que X está en un ciclo de 3 nodos. Retroceder a su padre es fácil (tal como está, el algoritmo no tiene soporte para esto, por lo que encontrará el padre que tenga X ').

Nota: Si el gráfico no está dirigido o tiene bordes bidireccionales, este algoritmo se vuelve más complicado, suponiendo que no desea atravesar el mismo borde dos veces durante un ciclo.

Si lo que desea es encontrar todos los circuitos elementales en un gráfico, puede usar el algoritmo EC, de JAMES C. TIERNAN, encontrado en un documento desde 1970.

El muy original algoritmo EC que logré implementar en php (espero que no haya errores se muestra a continuación). También puede encontrar bucles si hay alguno. Los circuitos en esta implementación (que intenta clonar el original) son los elementos distintos de cero. Cero aquí significa no existencia (nulo como lo conocemos).

Además de lo que sigue a continuación, otra implementación que le da al algoritmo más independencia, esto significa que los nodos pueden comenzar desde cualquier lugar incluso desde números negativos, por ejemplo -4, -3, -2, etc.

En ambos casos se requiere que los nodos sean secuenciales.

Es posible que deba estudiar el documento original, Algoritmo del circuito de James C. Tiernan Elementary

<?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);
?>

entonces esta es la otra implementación, más independiente del gráfico, sin goto y sin valores de matriz, en su lugar utiliza claves de matriz, la ruta, el gráfico y los circuitos se almacenan como claves de matriz (use valores de matriz si lo desea, simplemente cambie los valores requeridos líneas). El gráfico de ejemplo comienza desde -4 para mostrar su independencia.

<?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

?>

He analizado y documentado la CE, pero desafortunadamente la documentación está en griego.

Hay dos pasos (algoritmos) involucrados en la búsqueda de todos los ciclos en un DAG.

El primer paso es usar el algoritmo de Tarjan para encontrar el conjunto de componentes fuertemente conectados.

1. Comience desde cualquier vértice arbitrario.
2. DFS de ese vértice. Para cada nodo x, mantenga dos números, dfs_index [x] y dfs_lowval [x]. dfs_index [x] se almacena cuando se visita ese nodo, mientras que dfs_lowval [x] = min (dfs_low [k]) donde k son todos los hijos de x que no son los padres directamente de x en el árbol de expansión dfs.
3. Todos los nodos con el mismo dfs_lowval [x] están en el mismo componente fuertemente conectado.

El segundo paso es encontrar ciclos (rutas) dentro de los componentes conectados. Mi sugerencia es usar una versión modificada del algoritmo de Hierholzer.

La idea es:

1. Elija cualquier vértice inicial v, y siga un rastro de bordes desde ese vértice hasta que regrese a v. No es posible quedarse atascado en ningún vértice que no sea v, porque el grado uniforme de todos los vértices asegura que, cuando el rastro ingrese a otro vértice w debe haber un borde no utilizado dejando w. El recorrido formado de esta manera es un recorrido cerrado, pero puede que no cubra todos los vértices y bordes del gráfico inicial.
2. Siempre que exista un vértice v que pertenezca al recorrido actual pero que tenga bordes adyacentes que no formen parte del recorrido, comience otro recorrido desde v, siguiendo los bordes no utilizados hasta que regrese a v, y únase al recorrido formado de esta manera al tour anterior

Aquí está el enlace a una implementación de Java con un caso de prueba:

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

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

Me topé con el siguiente algoritmo que parece ser más eficiente que el algoritmo de Johnson (al menos para gráficos más grandes). Sin embargo, no estoy seguro de su rendimiento en comparación con el algoritmo de Tarjan.
Además, solo lo revisé para ver triángulos hasta ahora. Si está interesado, consulte "Algoritmos de listado de arboricidad y subgrafía" por Norishige Chiba y Takao Nishizeki ( http://dx.doi.org/10.1137/0214017 )

Solución Javascript que utiliza listas enlazadas de conjuntos disjuntos. Se puede actualizar a bosques conjuntos disjuntos para tiempos de ejecución más 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 desde el nodo de inicio s, realice un seguimiento de la ruta de DFS durante el recorrido y registre la ruta si encuentra un borde desde el nodo v en la ruta hacia s. (v, s) es un back-edge en el árbol DFS y por lo tanto indica un ciclo que contiene s.

Con respecto a su pregunta sobre el ciclo de permutación , lea más aquí: https://www.codechef.com/problems/PCYCLE

Puede probar este código (ingrese el tamaño y el número de 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]);
    }
}

Versión DFS c ++ para el pseudocódigo en la respuesta del segundo piso:

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();
}