Recherche de tous les cycles dans un graphe orienté

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 liste tous les cycles (élémentaires) d’un graphe orienté. Il est de Donald B. Johnson et l’article peut être trouvé 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 à partir de la droite ( “Télécharger le code de l’auteur” ).

Remarque: En fait, il existe de nombreux algorithmes pour résoudre 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 recherche en profondeur avec retour en arrière devrait fonctionner ici. Conservez un tableau de valeurs booléennes pour savoir si vous avez déjà visité un nœud. Si vous êtes à court de nouveaux nœuds (sans toucher un nœud que vous avez déjà été), revenez simplement en arrière et essayez une twig différente.

Le DFS est facile à implémenter si vous avez une liste de contiguïté 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 noeud à 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émarrage:

 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 en a 1, ils sont infinis. Par exemple, ABA, ABABA, etc. Ou il peut être possible de réunir 2 cycles dans un cycle de type 8, etc. etc. L’approche significative consiste à rechercher tous les cycles simples – ceux qui ne se croisent pas, sauf dans le sharepoint départ / fin. Ensuite, si vous le souhaitez, vous pouvez générer des combinaisons de cycles simples.

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

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

BTW, depuis que j’ai mentionné les graphes non orientés: L’algorithme pour ceux-ci est différent. Construisez un arbre recouvrant et chaque arête qui ne fait pas partie de l’arbre forme un cycle simple avec quelques arêtes dans l’arbre. Les cycles trouvés de cette manière forment une base de cycle. Tous les cycles simples peuvent alors être trouvés en combinant 2 cycles de base distincts ou plus. Pour plus de détails, voir par exemple: 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 lib 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-graphes qui ont au moins un cycle en eux, pas tous les cycles possibles dans le graphique. Par exemple, si vous prenez tous les composants fortement connectés et réduisez / groupez / fusionnez chacun d’eux en un seul nœud (c.-à-d. un nœud par composant), vous obtiendrez un arbre sans cycle (un DAG en fait). Chaque composant (qui est fondamentalement un sous-graphe avec au moins un cycle) peut contenir beaucoup plus de cycles possibles en interne, donc SCC ne trouvera PAS tous les cycles possibles, il trouvera tous les groupes possibles ayant au moins un cycle et si vous groupez 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é cette question d’interview une fois, je pense que cela vous est arrivé et que 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 le même point

Problème 1) Utilisez le modèle d’iterator pour fournir un moyen d’itérer les résultats d’itinéraire. Un bon endroit pour placer la logique pour obtenir la prochaine route est probablement le “moveNext” de votre iterator. Pour trouver un itinéraire valide, cela dépend de votre structure de données. Pour moi, il s’agissait d’une table SQL pleine de possibilités de routes valides. J’ai donc dû créer une requête pour obtenir les destinations valides à partir d’une source.

Problème 2) Poussez chaque nœud au fur et à mesure que vous les trouvez dans une collection, 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 vous voyez doubler, vous pouvez enlever les éléments de la collection et “sauvegarder”. Ensuite, essayez à nouveau de “progresser”.

Hack: si vous utilisez Sql Server 2008, il existe de nouvelles fonctionnalités de «hiérarchie» pour résoudre rapidement ce problème si vous structurez vos données dans une arborescence.

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. Partir de n’importe quel sumt arbitraire.
2. DFS de ce sumt. Pour chaque noeud x, conservez deux nombres, dfs_index [x] et dfs_lowval [x]. dfs_index [x] stocke quand ce noeud est visité, tandis que dfs_lowval [x] = min (dfs_low [k]) où k est tous les enfants de x qui n’est pas le parent direct de x dans l’arbre dfs-spanning.
3. Tous les nœuds ayant le même dfs_lowval [x] sont dans le même composant fortement connecté.

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

L’idée est la suivante:

1. Choisissez n’importe quel sumt de départ v, et suivez une piste d’arêtes de ce sumt jusqu’à ce que vous reveniez à v. Il n’est pas possible de restr bloqué sur un sumt autre que v, car le degré pair de tous les sumts vertex w il doit y avoir un bord inutilisé laissant w. Le tour ainsi formé est un tour fermé, mais peut ne pas couvrir tous les sumts et arêtes du graphe initial.
2. Tant qu’il existe un sumt v appartenant au tour en cours mais dont les arêtes adjacentes ne font pas partie du tour, démarrez un autre tracé à partir de v, en suivant les arêtes inutilisées jusqu’à ce que vous reveniez à v et rejoignez le tour ainsi formé. tournée précédente

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

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

Dans le cas d’un graphe non orienté, un article récemment publié ( Optimal list of cycles and st-traject dans des 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 qu’il ne répond pas à votre question, mais depuis le titre de votre question ne mentionne pas la direction, il peut toujours être utile pour la recherche Google

Commencez par le nœud X et vérifiez tous les nœuds enfants (les nœuds parents et enfants sont équivalents s’ils ne sont pas orientés). Marquez ces nœuds enfants comme étant des enfants de X. À partir de n’importe quel nœud enfant A, cochez ses enfants comme étant des enfants de A, X ‘, où X est noté à 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 de 3 nœuds. Revenir en arrière à son parent est facile (tel quel, l’algorithme n’a aucun support pour cela, donc vous trouverez n’importe quel parent ayant X ‘).

Remarque: si le graphique n’est pas orienté ou comporte des arêtes bidirectionnelles, cet algorithme devient plus compliqué, en supposant que vous ne souhaitiez pas parcourir 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 tel que j’ai réussi à l’implémenter en php (j’espère qu’il n’y a pas d’erreurs est montré ci-dessous). Il peut aussi trouver des boucles s’il y en a. Les circuits dans cette implémentation (qui essaie de cloner l’original) sont les éléments non nuls. Zero signifie ici la non-existence (nulle comme on le sait).

En dehors de cela ci-dessous suit une autre implémentation qui donne à l’algorithme une plus grande 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.

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

Vous devrez peut-être étudier l’article original, Algorithme du circuit élémentaire James C. Tiernan

 

"; $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 tableaux, mais utilise des clés de tableaux, le chemin, le graphe et les circuits sont stockés en tant que clés de tableaux (utilisez les valeurs du tableau si lignes). L’exemple de graphique commence à -4 pour montrer son indépendance.

 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 "
"; 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é le CE mais malheureusement la documentation est en grec. 

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 (du moins pour les plus grands graphiques). Je ne suis toutefois pas sûr de sa performance par rapport à l’algorithme de Tarjan.
De plus, je ne l’ai vérifié que pour les sortingangles. Si vous êtes intéressé, veuillez consulter “Algorithmes de la liste des arborescences et des sous-graphes” par Norishige Chiba et Takao Nishizeki ( http://dx.doi.org/10.1137/0214017 )

ne pouvez-vous pas faire une petite fonction récursive pour parcourir les nœuds?

 readDiGraph( ssortingng pathSoFar, Node x) { if(NoChildren) MasterList.add( pathsofar + Node.name ) ; foreach( child ) { readDiGraph( pathsofar + "->" + this.name, child) } } 

si vous avez une tonne de nœuds, vous manquerez de stack

Solution Javascript utilisant des listes liées par ensembles disjoints. Peut être mis à niveau pour créer des 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 adjMasortingx = []; 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 (xy) ) 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(masortingx, pair){ return masortingx[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émarrage 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 d’access à s. (v, s) est un bord arrière dans l’arborescence DFS et indique donc un cycle contenant s.

En ce qui concerne 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 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]); } } 

Les variantes basées sur DFS avec des arêtes de fond trouveront des cycles, mais dans de nombreux cas, cela ne sera PAS un cycle minimal . En général, DFS vous donne le drapeau indiquant qu’il y a un cycle, mais ce n’est pas suffisant pour 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 présente une bonne complexité en termes de temps et d’espace.

Mais si vous voulez juste trouver des cycles MINIMAUX (ce qui signifie qu’il peut y avoir plus d’un cycle passant par un sumt et que nous sums intéressés à en trouver un minimum) ET que votre graphique n’est pas très volumineux, vous pouvez utiliser la méthode simple ci-dessous. C’est très simple mais plutôt lent comparé à celui de Johnson.

Ainsi, l’un des moyens les plus simples de trouver des cycles MINIMAL consiste à utiliser l’algorithme de Floyd pour trouver des chemins minimaux entre tous les sumts à l’aide de la masortingce d’adjacence. Cet algorithme est loin d’être aussi optimal que celui de Johnson, mais il est si simple et sa boucle interne est tellement étroite que pour des graphes plus petits (<= 50-100 nœuds), il est absolument logique de l'utiliser. La complexité temporelle est O (n ^ 3), la complexité de l'espace O (n ^ 2) si vous utilisez le suivi parent 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 simple. Ci-dessous, l'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 opère sur un graphe de bord pondéré pour trouver tous les chemins les plus courts entre toutes les paires de nœuds (d'où l'argument de pondération). Pour que cela fonctionne correctement, vous devez fournir 1 s'il y a un bord dirigé entre les noeuds ou NO_EDGE sinon. Après l'exécution de l'algorithme, vous pouvez vérifier la diagonale principale, s'il y a des valeurs moins, alors NO_EDGE que ce nœud participe à un cycle de longueur égal à 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 un suivi parent.

  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 masortingce des parents doit initialement contenir un index de sumts source dans une cellule de bord s'il existe un bord entre les sumts et -1 dans le cas contraire. Après le retour de la fonction, pour chaque front, vous aurez une référence au nœud parent dans l'arborescence de 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[Ssortingng]): 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.mkSsortingng)) println(s"Total: ${cycles.size} cycle found") } 

et la sortie est

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