Finden aller Zyklen in einem gerichteten Graphen

Wie kann ich ALLE Zyklen in einem gerichteten Graphen von / zu einem bestimmten Knoten finden (durchlaufen)?

Zum Beispiel möchte ich so etwas:

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

aber nicht: B-> C-> B.

Ich habe diese Seite in meiner Suche gefunden und da Zyklen nicht mit stark verbundenen Komponenten identisch sind, habe ich weiter gesucht und schließlich einen effizienten Algorithmus gefunden, der alle (elementaren) Zyklen eines gerichteten Graphen auflistet. Es ist von Donald B. Johnson und das Papier kann unter dem folgenden Link gefunden werden:

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

Eine Java-Implementierung finden Sie in:

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

EIN Mathematica- Demonstration des Johnson-Algorithmus finden Sie hier . Die Implementierung kann von rechts heruntergeladen werden ( "Autorcode herunterladen" ).

Hinweis: Tatsächlich gibt es viele Algorithmen für dieses Problem. Einige von ihnen sind in diesem Artikel aufgeführt:

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

Laut dem Artikel ist Johnsons Algorithmus der schnellste.

Die Tiefensuche mit Backtracking sollte hier funktionieren. Behalten Sie ein Array von Booleschen Werten bei, um zu verfolgen, ob Sie zuvor einen Knoten besucht haben. Wenn Ihnen die neuen Knoten ausgehen (ohne einen Knoten zu treffen, den Sie bereits getroffen haben), gehen Sie einfach zurück und versuchen Sie es mit einem anderen Zweig.

Das DFS ist einfach zu implementieren, wenn Sie eine Adjazenzliste zur Darstellung des Diagramms haben. Zum Beispiel gibt adj [A] = {B, C} an, dass B und C die Kinder von A sind.

Zum Beispiel Pseudocode unten. "start" ist der Knoten, von dem aus Sie starten.

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;

Rufen Sie die obige Funktion mit dem Startknoten auf:

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

Zuallererst - Sie möchten nicht wirklich versuchen, buchstäblich alle Zyklen zu finden, denn wenn es 1 gibt, gibt es unendlich viele davon. Zum Beispiel ABA, ABABA usw. Oder es kann möglich sein, 2 Zyklen zu einem 8-ähnlichen Zyklus usw. usw. zusammenzufügen. Der sinnvolle Ansatz besteht darin, nach allen sogenannten einfachen Zyklen zu suchen - nach solchen, die sich nur kreuzen im Start- / Endpunkt. Wenn Sie möchten, können Sie dann Kombinationen einfacher Zyklen generieren.

Einer der Basisalgorithmen zum Auffinden aller einfachen Zyklen in einem gerichteten Diagramm ist folgender: Führen Sie eine Tiefen-Erst-Durchquerung aller einfachen Pfade (diejenigen, die sich nicht kreuzen) im Diagramm durch. Jedes Mal, wenn der aktuelle Knoten einen Nachfolger auf dem Stapel hat, wird ein einfacher Zyklus entdeckt. Es besteht aus den Elementen auf dem Stapel, die mit dem identifizierten Nachfolger beginnen und mit der Oberseite des Stapels enden. Die Tiefenüberquerung aller einfachen Pfade ähnelt der Tiefensuche, Sie markieren / zeichnen jedoch keine anderen besuchten Knoten als die derzeit auf dem Stapel befindlichen als Stopppunkte auf.

Der obige Brute-Force-Algorithmus ist furchtbar ineffizient und erzeugt zusätzlich mehrere Kopien der Zyklen. Es ist jedoch der Ausgangspunkt mehrerer praktischer Algorithmen, die verschiedene Verbesserungen anwenden, um die Leistung zu verbessern und Zyklusduplikationen zu vermeiden. Ich war überrascht, vor einiger Zeit herauszufinden, dass diese Algorithmen in Lehrbüchern und im Internet nicht ohne weiteres verfügbar sind. Also habe ich einige Nachforschungen angestellt und 4 solcher Algorithmen und 1 Algorithmus für Zyklen in ungerichteten Graphen in einer Open-Source-Java-Bibliothek hier implementiert: http://code.google.com/p/niographs/ .

Übrigens, da ich ungerichtete Graphen erwähnt habe: Der Algorithmus für diese ist unterschiedlich. Erstellen Sie einen Spannbaum, und dann bildet jede Kante, die nicht Teil des Baums ist, zusammen mit einigen Kanten im Baum einen einfachen Zyklus. Die so gefundenen Zyklen bilden eine sogenannte Zyklusbasis. Alle einfachen Zyklen können dann gefunden werden, indem 2 oder mehr verschiedene Basiszyklen kombiniert werden. Weitere Informationen finden Sie beispielsweise unter: http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf .

Die einfachste Wahl, die ich gefunden habe, um dieses Problem zu lösen, war die Verwendung der aufgerufenen Python-Bibliothek networkx.

Es implementiert den Johnson-Algorithmus, der in der besten Antwort auf diese Frage erwähnt wird, ist jedoch recht einfach auszuführen.

Kurz gesagt, Sie benötigen Folgendes:

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

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

Zu klären:

1. Stark verbundene Komponenten finden alle Untergraphen, die mindestens einen Zyklus enthalten, nicht alle möglichen Zyklen im Diagramm. Wenn Sie beispielsweise alle stark verbundenen Komponenten nehmen und jede einzelne zu einem Knoten zusammenfassen / gruppieren / zusammenführen (dh einen Knoten pro Komponente), erhalten Sie einen Baum ohne Zyklen (tatsächlich eine DAG). Jede Komponente (im Grunde genommen ein Untergraph mit mindestens einem Zyklus) kann intern viel mehr mögliche Zyklen enthalten, sodass SCC NICHT alle möglichen Zyklen findet, sondern alle möglichen Gruppen mit mindestens einem Zyklus und wenn Sie gruppieren ihnen, dann hat der Graph keine Zyklen.

2. Um alle einfachen Zyklen in einem Diagramm zu finden, wie bereits erwähnt, ist Johnsons Algorithmus ein Kandidat.

Ich habe dies einmal als Interviewfrage erhalten. Ich vermute, dass Ihnen dies passiert ist und Sie hierher kommen, um Hilfe zu erhalten. Teilen Sie das Problem in drei Fragen auf und es wird einfacher.

1. Wie bestimmen Sie die nächste gültige Route?
2. Wie stellen Sie fest, ob ein Punkt verwendet wurde?
3. Wie vermeiden Sie es, denselben Punkt erneut zu überqueren?

Problem 1) Verwenden Sie das Iteratormuster, um Routenergebnisse zu iterieren. Ein guter Ort, um die Logik zu setzen, um die nächste Route zu erhalten, ist wahrscheinlich der "moveNext" Ihres Iterators. Um eine gültige Route zu finden, hängt dies von Ihrer Datenstruktur ab. Für mich war es eine SQL-Tabelle voller gültiger Routenmöglichkeiten, daher musste ich eine Abfrage erstellen, um die gültigen Ziele unter Angabe einer Quelle zu erhalten.

Problem 2) Schieben Sie jeden Knoten, sobald Sie ihn finden, in eine Sammlung, sobald Sie ihn erhalten. Dies bedeutet, dass Sie sehr leicht feststellen können, ob Sie sich über einen Punkt "verdoppeln", indem Sie die Sammlung abfragen, die Sie im laufenden Betrieb erstellen.

Problem 3) Wenn Sie zu irgendeinem Zeitpunkt sehen, dass Sie sich verdoppeln, können Sie Dinge aus der Sammlung entfernen und "sichern". Versuchen Sie dann von diesem Punkt an, erneut "vorwärts" zu gehen.

Hack: Wenn Sie SQL Server 2008 verwenden, gibt es einige neue "Hierarchie" -Dinge, mit denen Sie dies schnell lösen können, wenn Sie Ihre Daten in einem Baum strukturieren.

Die DFS-basierten Varianten mit Hinterkanten finden zwar Zyklen, in vielen Fällen handelt es sich jedoch NICHT um minimale Zyklen. Im Allgemeinen gibt Ihnen DFS das Flag, dass es einen Zyklus gibt, aber es ist nicht gut genug, um tatsächlich Zyklen zu finden. Stellen Sie sich zum Beispiel 5 verschiedene Zyklen vor, die sich zwei Kanten teilen. Es gibt keine einfache Möglichkeit, Zyklen nur mit DFS zu identifizieren (einschließlich Backtracking-Varianten).

Johnsons Algorithmus liefert in der Tat alle einzigartigen einfachen Zyklen und weist eine gute zeitliche und räumliche Komplexität auf.

Wenn Sie jedoch nur MINIMALE Zyklen finden möchten (was bedeutet, dass möglicherweise mehr als ein Zyklus durch einen beliebigen Scheitelpunkt verläuft und wir daran interessiert sind, minimale Zyklen zu finden) UND Ihr Diagramm nicht sehr groß ist, können Sie versuchen, die folgende einfache Methode zu verwenden. Es ist sehr einfach, aber im Vergleich zu Johnson ziemlich langsam.

Eine der absolut einfachsten Möglichkeiten, MINIMAL-Zyklen zu finden, ist die Verwendung des Floyd-Algorithmus, um mithilfe der Adjazenzmatrix minimale Pfade zwischen allen Scheitelpunkten zu finden. Dieser Algorithmus ist bei weitem nicht so optimal wie der von Johnson, aber er ist so einfach und seine innere Schleife ist so eng, dass es für kleinere Graphen (<= 50-100 Knoten) absolut sinnvoll ist, ihn zu verwenden. Die zeitliche Komplexität ist O (n ^ 3), die räumliche Komplexität O (n ^ 2), wenn Sie die übergeordnete Verfolgung verwenden, und O (1), wenn Sie dies nicht tun. Lassen Sie uns zunächst die Antwort auf die Frage finden, ob es einen Zyklus gibt. Der Algorithmus ist kinderleicht. Unten ist ein Ausschnitt in 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
      }
    }
  }

Ursprünglich arbeitet dieser Algorithmus mit einem Graphen mit gewichteten Kanten, um alle kürzesten Pfade zwischen allen Knotenpaaren zu finden (daher das Argument für Gewichte). Damit es richtig funktioniert, müssen Sie 1 angeben, wenn sich zwischen den Knoten eine gerichtete Kante befindet, oder NO_EDGE. Nachdem der Algorithmus ausgeführt wurde, können Sie die Hauptdiagonale überprüfen, wenn Werte kleiner als NO_EDGE vorhanden sind, als dieser Knoten an einem Zyklus mit einer Länge teilnimmt, die dem Wert entspricht. Jeder andere Knoten desselben Zyklus hat denselben Wert (auf der Hauptdiagonale).

Um den Zyklus selbst zu rekonstruieren, müssen wir eine leicht modifizierte Version des Algorithmus mit übergeordnetem Tracking verwenden.

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

Die Elternmatrix sollte anfänglich den Quellscheitelpunktindex in einer Randzelle enthalten, wenn sich zwischen den Scheitelpunkten eine Kante befindet, andernfalls -1. Nach der Rückkehr der Funktion haben Sie für jede Kante einen Verweis auf den übergeordneten Knoten im kürzesten Pfadbaum. Und dann ist es einfach, tatsächliche Zyklen wiederherzustellen.

Alles in allem haben wir das folgende Programm, um alle minimalen Zyklen zu finden

  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
  }

und eine kleine Hauptmethode, um das Ergebnis zu testen

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

und die Ausgabe ist

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

Im Fall eines ungerichteten Graphen bietet ein kürzlich veröffentlichtes Papier ( Optimale Auflistung von Zyklen und St-Pfaden in ungerichteten Graphen ) eine asymptotisch optimale Lösung. Sie können es hier lesen http://arxiv.org/abs/1205.2766 oder hier http://dl.acm.org/citation.cfm?id=2627951 Ich weiß, es beantwortet Ihre Frage nicht, aber seit dem Titel von In Ihrer Frage wird die Richtung nicht erwähnt. Möglicherweise ist sie für die Google-Suche hilfreich

Beginnen Sie am Knoten X und suchen Sie nach allen untergeordneten Knoten (übergeordnete und untergeordnete Knoten sind äquivalent, wenn sie nicht gerichtet sind). Markieren Sie diese untergeordneten Knoten als Kinder von X. Markieren Sie von einem solchen untergeordneten Knoten A aus Kinder von A, X ', wobei X' als 2 Schritte entfernt markiert ist.). Wenn Sie später X drücken und es als untergeordnetes Element von X '' markieren, bedeutet dies, dass sich X in einem Zyklus mit 3 Knoten befindet. Das Zurückverfolgen zu seinem übergeordneten Element ist einfach (wie es ist, unterstützt der Algorithmus dies nicht, sodass Sie feststellen würden, welches übergeordnete Element X 'hat).

Hinweis: Wenn der Graph ungerichtet ist oder bidirektionale Kanten aufweist, wird dieser Algorithmus komplizierter, vorausgesetzt, Sie möchten dieselbe Kante nicht zweimal für einen Zyklus durchlaufen.

Wenn Sie alle Elementarschaltungen in einem Diagramm finden möchten, können Sie den EC-Algorithmus von JAMES C. TIERNAN verwenden, der seit 1970 auf einem Papier zu finden ist.

Der sehr originelle EC-Algorithmus, wie ich ihn in PHP implementiert habe (ich hoffe, es gibt keine Fehler, wird unten gezeigt). Es kann auch Schleifen finden, wenn es welche gibt. Die Schaltungen in dieser Implementierung (die versucht, das Original zu klonen) sind die Nicht-Null-Elemente. Null steht hier für Nichtexistenz (Null, wie wir es kennen).

Abgesehen davon folgt unten eine andere Implementierung, die dem Algorithmus mehr Unabhängigkeit verleiht. Dies bedeutet, dass die Knoten von jedem Ort aus starten können, selbst von negativen Zahlen, z. B. -4, -3, -2 usw.

In beiden Fällen müssen die Knoten sequentiell sein.

Möglicherweise müssen Sie das Originalpapier, James C. Tiernan Elementary Circuit Algorithm , studieren

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

Dann ist dies die andere Implementierung, die unabhängiger vom Diagramm ist, ohne goto und ohne Array-Werte. Stattdessen werden Array-Schlüssel verwendet. Der Pfad, das Diagramm und die Schaltkreise werden als Array-Schlüssel gespeichert (verwenden Sie Array-Werte, wenn Sie möchten, ändern Sie einfach die erforderlichen Linien). Das Beispieldiagramm beginnt bei -4, um seine Unabhängigkeit zu zeigen.

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

?>

Ich habe die EU analysiert und dokumentiert, aber leider ist die Dokumentation in Griechisch.

Es gibt zwei Schritte (Algorithmen), um alle Zyklen in einer DAG zu finden.

Der erste Schritt besteht darin, den Tarjan-Algorithmus zu verwenden, um den Satz stark verbundener Komponenten zu finden.

1. Beginnen Sie mit einem beliebigen Scheitelpunkt.
2. DFS von diesem Scheitelpunkt. Behalten Sie für jeden Knoten x zwei Zahlen bei, dfs_index [x] und dfs_lowval [x]. dfs_index [x] speichert, wann dieser Knoten besucht wird, während dfs_lowval [x] = min (dfs_low [k]), wobei k alle untergeordneten Elemente von x sind, die nicht das direkt übergeordnete Element von x im dfs-überspannenden Baum sind.
3. Alle Knoten mit demselben dfs_lowval [x] befinden sich in derselben stark verbundenen Komponente.

Der zweite Schritt besteht darin, Zyklen (Pfade) innerhalb der verbundenen Komponenten zu finden. Mein Vorschlag ist, eine modifizierte Version des Hierholzer-Algorithmus zu verwenden.

Die Idee ist:

1. Wählen Sie einen beliebigen Startscheitelpunkt v und folgen Sie einer Spur von Kanten von diesem Scheitelpunkt aus, bis Sie zu v zurückkehren. Es ist nicht möglich, an einem anderen Scheitelpunkt als v hängen zu bleiben, da der gleichmäßige Grad aller Scheitelpunkte sicherstellt, dass der Pfad in einen anderen eintritt Scheitelpunkt w Es muss eine unbenutzte Kante vorhanden sein, die w verlässt. Die auf diese Weise gebildete Tour ist eine geschlossene Tour, deckt jedoch möglicherweise nicht alle Eckpunkte und Kanten des ursprünglichen Diagramms ab.
2. Solange es einen Scheitelpunkt v gibt, der zur aktuellen Tour gehört, dessen angrenzende Kanten jedoch nicht Teil der Tour sind, starten Sie einen weiteren Pfad von v, folgen Sie nicht verwendeten Kanten, bis Sie zu v zurückkehren, und schließen Sie sich der auf diese Weise gebildeten Tour an die an vorherige Tour.

Hier ist der Link zu einer Java-Implementierung mit einem Testfall:

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

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

Ich bin über den folgenden Algorithmus gestolpert, der effizienter zu sein scheint als Johnsons Algorithmus (zumindest für größere Diagramme). Ich bin mir jedoch nicht sicher über die Leistung im Vergleich zu Tarjans Algorithmus.
Außerdem habe ich es bisher nur auf Dreiecke überprüft. Bei Interesse lesen Sie bitte "Arboricity and Subgraph Listing Algorithms" von Norishige Chiba und Takao Nishizeki ( http://dx.doi.org/10.1137/0214017 ).

Javascript-Lösung mit disjunkten verknüpften Listen. Kann aktualisiert werden, um festgelegte Gesamtstrukturen für schnellere Laufzeiten zu trennen.

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 vom Startknoten s, verfolgen Sie den DFS-Pfad während des Durchlaufs und zeichnen Sie den Pfad auf, wenn Sie eine Kante vom Knoten v im Pfad zu s finden. (v, s) ist eine Hinterkante im DFS-Baum und zeigt somit einen Zyklus an, der s enthält.

Weitere Informationen zu Ihrer Frage zum Permutationszyklus finden Sie hier: https://www.codechef.com/problems/PCYCLE

Sie können diesen Code ausprobieren (geben Sie die Größe und die Ziffernnummer ein):

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

DFS c ++ - Version für den Pseudocode in der Antwort im zweiten Stock:

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