Trouver tous les cycles dans un graphique dirigé

Comment puis-je trouver (itérer sur) TOUS les cycles dans un graphe orienté depuis / vers un nœud donné?

Par exemple, je veux quelque chose comme ça:

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

mais pas: B-> C-> B

J'ai trouvé cette page dans ma recherche et comme les cycles ne sont pas les mêmes que les composants fortement connectés, j'ai continué à chercher et finalement, j'ai trouvé un algorithme efficace qui répertorie tous les cycles (élémentaires) d'un graphe orienté. Il provient de Donald B. Johnson et l'article se trouve dans le lien suivant:

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

Une implémentation Java peut être trouvée dans:

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

Une démonstration Mathematica de l'algorithme de Johnson peut être trouvée ici , l'implémentation peut être téléchargée à droite ( "Download author code" ).

Remarque: En fait, il existe de nombreux algorithmes pour ce problème. Certains d'entre eux sont répertoriés dans cet article:

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

Selon l'article, l'algorithme de Johnson est le plus rapide.

La première recherche approfondie avec retour arrière devrait fonctionner ici. Conservez un tableau de valeurs booléennes pour savoir si vous avez déjà visité un nœud auparavant. Si vous manquez de nouveaux nœuds vers lesquels aller (sans toucher un nœud que vous avez déjà été), alors revenez en arrière et essayez une autre branche.

Le DFS est facile à implémenter si vous avez une liste d'adjacence pour représenter le graphique. Par exemple, adj [A] = {B, C} indique que B et C sont les enfants de A.

Par exemple, pseudo-code ci-dessous. "start" est le nœud à partir duquel vous commencez.

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;

Appelez la fonction ci-dessus avec le nœud de départ:

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

Tout d'abord - vous ne voulez pas vraiment essayer de trouver littéralement tous les cycles car s'il y a 1, il y en a un nombre infini. Par exemple ABA, ABABA etc. Ou il peut être possible de réunir 2 cycles en un cycle semblable à 8 etc., etc ... L'approche significative est de rechercher tous les soi-disant cycles simples - ceux qui ne se croisent pas sauf dans le point de début / fin. Ensuite, si vous le souhaitez, vous pouvez générer des combinaisons de cycles simples.

L'un des algorithmes de base pour trouver tous les cycles simples dans un graphe orienté est le suivant: effectuez une traversée en profondeur d'abord de tous les chemins simples (ceux qui ne se croisent pas) dans le graphe. Chaque fois que le nœud actuel a un successeur sur la pile, un cycle simple est découvert. Il se compose des éléments de la pile commençant par le successeur identifié et se terminant par le haut de la pile. La première traversée en profondeur de tous les chemins simples est similaire à la première recherche en profondeur, mais vous ne marquez / n'enregistrez pas les nœuds visités autres que ceux actuellement sur la pile comme points d'arrêt.

L'algorithme de force brute ci-dessus est terriblement inefficace et en plus de cela génère plusieurs copies des cycles. C'est cependant le point de départ de multiples algorithmes pratiques qui appliquent diverses améliorations afin d'améliorer les performances et d'éviter la duplication de cycle. J'ai été surpris de découvrir il y a quelque temps que ces algorithmes ne sont pas facilement disponibles dans les manuels et sur le Web. J'ai donc fait quelques recherches et implémenté 4 algorithmes de ce type et 1 algorithme pour les cycles dans des graphiques non dirigés dans une bibliothèque Java open source ici: http://code.google.com/p/niographs/ .

BTW, puisque j'ai mentionné des graphiques non orientés: l'algorithme pour ceux-ci est différent. Construisez un arbre couvrant, puis chaque bord qui ne fait pas partie de l'arbre forme un cycle simple avec quelques bords dans l'arbre. Les cycles ainsi trouvés forment une base dite de cycle. Tous les cycles simples peuvent ensuite être trouvés en combinant 2 cycles de base distincts ou plus. Pour plus de détails, voir par exemple ceci: http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf .

Le choix le plus simple que j'ai trouvé pour résoudre ce problème était d'utiliser la bibliothèque python appelée networkx .

Il implémente l'algorithme de Johnson mentionné dans la meilleure réponse à cette question mais il est assez simple à exécuter.

En bref, vous avez besoin des éléments suivants:

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

Réponse: [['a', 'b', 'd', 'e'], ['a', 'b', 'c']]

Clarifier:

1. Les composants fortement connectés trouveront tous les sous-graphiques qui contiennent au moins un cycle, pas tous les cycles possibles dans le graphique. Par exemple, si vous prenez tous les composants fortement connectés et réduisez / regroupez / fusionnez chacun d'eux en un seul nœud (c'est-à-dire un nœud par composant), vous obtiendrez un arbre sans cycles (un DAG en fait). Chaque composant (qui est essentiellement un sous-graphique contenant au moins un cycle) peut contenir de nombreux autres cycles possibles en interne, donc SCC ne trouvera PAS tous les cycles possibles, il trouvera tous les groupes possibles qui ont au moins un cycle, et si vous regroupez eux, alors le graphique n'aura pas de cycles.

2. pour trouver tous les cycles simples dans un graphique, comme d'autres l'ont mentionné, l'algorithme de Johnson est un candidat.

On m'a donné cela comme une question d'entrevue une fois, je soupçonne que cela vous est arrivé et vous venez ici pour obtenir de l'aide. Divisez le problème en trois questions et cela devient plus facile.

1. comment déterminez-vous le prochain itinéraire valide
2. comment déterminez-vous si un point a été utilisé
3. comment éviter de traverser à nouveau le même point

Problème 1) Utilisez le modèle d'itérateur pour fournir un moyen d'itérer les résultats de l'itinéraire. Un bon endroit pour mettre la logique pour obtenir le prochain itinéraire est probablement le "moveNext" de votre itérateur. Pour trouver un itinéraire valide, cela dépend de votre structure de données. Pour moi, c'était une table sql pleine de possibilités de routes valides, j'ai donc dû créer une requête pour obtenir les destinations valides en fonction d'une source.

Problème 2) Poussez chaque nœud au fur et à mesure que vous les trouvez dans une collection au fur et à mesure que vous les obtenez, cela signifie que vous pouvez voir si vous "doublez" un point très facilement en interrogeant la collection que vous construisez à la volée.

Problème 3) Si, à tout moment, vous constatez que vous doublez, vous pouvez retirer des éléments de la collection et "sauvegarder". Ensuite, à partir de là, essayez à nouveau de "progresser".

Hack: si vous utilisez Sql Server 2008, il existe de nouvelles "hiérarchies" que vous pouvez utiliser pour résoudre rapidement ce problème si vous structurez vos données dans une arborescence.

Les variantes basées sur DFS avec des bords arrière trouveront effectivement des cycles, mais dans de nombreux cas, ce ne sera PAS minimal cycles . En général, DFS vous donne l'indicateur qu'il y a un cycle mais il n'est pas assez bon pour réellement trouver des cycles. Par exemple, imaginez 5 cycles différents partageant deux bords. Il n'y a pas de moyen simple d'identifier les cycles en utilisant uniquement DFS (y compris les variantes de retour en arrière).

L'algorithme de Johnson donne en effet tous les cycles simples uniques et a une bonne complexité temporelle et spatiale.

Mais si vous voulez simplement trouver des cycles MINIMAUX (ce qui signifie qu'il peut y avoir plus d'un cycle passant par n'importe quel sommet et que nous sommes intéressés à en trouver un minimum) ET que votre graphique n'est pas très grand, vous pouvez essayer d'utiliser la méthode simple ci-dessous. C'est TRÈS simple mais plutôt lent par rapport à Johnson.

Ainsi, l' un des tout à fait moyen le plus facile de trouver des cycles MINIMAL est d'utiliser l'algorithme de Floyd pour trouver des chemins minimaux entre tous les sommets en utilisant la matrice de contiguïté. Cet algorithme est loin d'être aussi optimal que celui de Johnson, mais il est si simple et sa boucle interne est si serrée que pour des graphiques plus petits (<= 50-100 nœuds), il est absolument logique de l'utiliser. La complexité temporelle est O (n ^ 3), la complexité spatiale O (n ^ 2) si vous utilisez le suivi des parents et O (1) si vous ne l'utilisez pas. Tout d'abord, trouvons la réponse à la question s'il y a un cycle. L'algorithme est extrêmement simple. Ci-dessous, un extrait de 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
      }
    }
  }

À l'origine, cet algorithme fonctionne sur un graphe à bords pondérés pour trouver tous les chemins les plus courts entre toutes les paires de nœuds (d'où l'argument des poids). Pour que cela fonctionne correctement, vous devez fournir 1 s'il y a un bord dirigé entre les nœuds ou NO_EDGE sinon. Après l'exécution de l'algorithme, vous pouvez vérifier la diagonale principale, s'il existe des valeurs inférieures à NO_EDGE à ce que ce nœud participe à un cycle de longueur égale à la valeur. Tous les autres nœuds du même cycle auront la même valeur (sur la diagonale principale).

Pour reconstruire le cycle lui-même, nous devons utiliser une version légèrement modifiée de l'algorithme avec suivi des parents.

  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 matrice des parents doit initialement contenir l'index du sommet source dans une cellule de bord s'il y a un bord entre les sommets et -1 sinon. Après le retour de la fonction, pour chaque bord, vous aurez une référence au nœud parent dans l'arborescence du chemin le plus court. Et puis, il est facile de récupérer des cycles réels.

Dans l'ensemble, nous avons le programme suivant pour trouver tous les cycles minimaux

  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
  }

et une petite méthode principale juste pour tester le résultat

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

et la sortie est

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

Dans le cas du graphe non orienté, un article récemment publié ( Liste optimale des cycles et des chemins st dans les graphes non orientés ) offre une solution asymptotiquement optimale. Vous pouvez le lire ici http://arxiv.org/abs/1205.2766 ou ici http://dl.acm.org/citation.cfm?id=2627951 Je sais que cela ne répond pas à votre question, mais depuis le titre de votre question ne mentionne pas la direction, elle pourrait quand même être utile pour la recherche Google

Commencez au nœud X et recherchez tous les nœuds enfants (les nœuds parent et enfant sont équivalents s'ils ne sont pas dirigés). Marquez ces nœuds enfants comme étant des enfants de X. À partir d'un tel nœud enfant A, marquez ses enfants d'être des enfants de A, X ', où X' est marqué comme étant à 2 pas.). Si vous frappez plus tard X et le marquez comme étant un enfant de X '', cela signifie que X est dans un cycle à 3 nœuds. Le retour en arrière vers son parent est facile (en l'état, l'algorithme ne prend pas en charge cela, vous trouverez donc le parent qui a X ').

Remarque: Si le graphique n'est pas orienté ou a des bords bidirectionnels, cet algorithme devient plus compliqué, en supposant que vous ne voulez pas traverser le même bord deux fois pour un cycle.

Si vous voulez trouver tous les circuits élémentaires dans un graphique, vous pouvez utiliser l'algorithme EC, de JAMES C.TIERNAN, trouvé sur un papier depuis 1970.

L' algorithme EC très original que j'ai réussi à implémenter en php (espérons qu'il n'y a pas d'erreur est montré ci-dessous). Il peut également trouver des boucles s'il y en a. Les circuits de cette implémentation (qui essaie de cloner l'original) sont les éléments non nuls. Zéro signifie ici non-existence (nul comme nous le savons).

En dehors de celle ci-dessous, une autre implémentation donne à l'algorithme plus d'indépendance, cela signifie que les nœuds peuvent commencer de n'importe où, même à partir de nombres négatifs, par exemple -4, -3, -2, etc. etc.

Dans les deux cas, il est nécessaire que les nœuds soient séquentiels.

Vous pourriez avoir besoin d'étudier l'article 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);
?>

alors c'est l'autre implémentation, plus indépendante du graphe, sans goto et sans valeurs de tableau, à la place il utilise des clés de tableau, le chemin, le graphe et les circuits sont stockés sous forme de clés de tableau (utilisez des valeurs de tableau si vous le souhaitez, changez simplement le requis lignes). Le graphique d'exemple commence à -4 pour montrer son indépendance.

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

?>

J'ai analysé et documenté la CE, mais malheureusement, la documentation est en grec.

Il y a deux étapes (algorithmes) impliquées dans la recherche de tous les cycles dans un DAG.

La première étape consiste à utiliser l'algorithme de Tarjan pour trouver l'ensemble des composants fortement connectés.

1. Commencez à partir de n'importe quel sommet arbitraire.
2. DFS de ce sommet. Pour chaque nœud x, conservez deux nombres, dfs_index [x] et dfs_lowval [x]. dfs_index [x] stocke lorsque ce nœud est visité, tandis que dfs_lowval [x] = min (dfs_low [k]) où k est tous les enfants de x qui ne sont pas le parent direct de x dans l'arbre couvrant dfs.
3. Tous les nœuds avec le même dfs_lowval [x] sont dans le même composant fortement connecté.

La deuxième étape consiste à trouver des cycles (chemins) au sein des composants connectés. Ma suggestion est d'utiliser une version modifiée de l'algorithme de Hierholzer.

L'idée est:

1. Choisissez un sommet de départ v et suivez une traînée d'arêtes à partir de ce sommet jusqu'à ce que vous reveniez à v. Il n'est pas possible de rester bloqué sur un sommet autre que v, car le degré pair de tous les sommets garantit que, lorsque le sentier entre dans un autre sommet w il doit y avoir un bord inutilisé quittant w. Le tour ainsi formé est un tour fermé, mais peut ne pas couvrir tous les sommets et bords du graphe initial.
2. Tant qu'il existe un sommet v qui appartient à la visite en cours mais qui a des bords adjacents ne faisant pas partie de la visite, commencez une autre piste à partir de v, en suivant les bords inutilisés jusqu'à ce que vous reveniez à v, et joignez la visite ainsi formée à la tournée précédente.

Voici le lien vers une implémentation Java avec un cas de test:

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

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

Je suis tombé sur l'algorithme suivant qui semble être plus efficace que l'algorithme de Johnson (au moins pour les graphiques plus grands). Je ne suis cependant pas sûr de ses performances par rapport à l'algorithme de Tarjan.
De plus, je ne l'ai vérifié que pour les triangles jusqu'à présent. Si vous êtes intéressé, veuillez consulter «Algorithmes de listage d'arboricité et de sous-graphiques» de Norishige Chiba et Takao Nishizeki ( http://dx.doi.org/10.1137/0214017 )

Solution Javascript utilisant des listes chaînées disjointes. Peut être mis à niveau pour séparer les forêts définies pour des temps d'exécution plus rapides.

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 à partir du nœud de départ s, gardez une trace du chemin DFS pendant la traversée et enregistrez le chemin si vous trouvez un bord du nœud v dans le chemin vers s. (v, s) est un bord arrière de l'arborescence DFS et indique donc un cycle contenant s.

Concernant votre question sur le cycle de permutation , lisez plus ici: https://www.codechef.com/problems/PCYCLE

Vous pouvez essayer ce code (entrez la taille et le nombre de chiffres):

# 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]);
    }
}

Version DFS c ++ pour le pseudo-code dans la réponse du deuxième étage:

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