Alle Zyklen in einem gerichteten Graphen finden
Wie kann ich ALLE Zyklen in einem gerichteten Graphen von/zu einem bestimmten Knoten finden (iterieren)?
Zum Beispiel möchte ich so etwas:
A->B->A
A->B->C->A
aber nicht: B-> C-> B
Ich fand diese Seite in meiner Suche und da Zyklen nicht mit stark verbundenen Komponenten identisch sind, suchte ich weiter und fand schließlich einen effizienten Algorithmus, der alle (elementaren) Zyklen eines gerichteten Graphen auflistet. Es ist von Donald B. Johnson und der Artikel ist unter folgendem Link zu finden:
http://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF
Eine Implementierung von Java findet sich in:
http://normalisiert.de/code/Java/elementaryCycles.Zip
Eine Mathematica Demonstration von Johnsons Algorithmus finden Sie hier , die Implementierung kann von rechts heruntergeladen werden ( "Download") Autorencode " ).
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
Nach dem Artikel ist Johnsons Algorithmus der schnellste.
Die Tiefensuche mit Rückverfolgung 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 besucht haben), gehen Sie einfach zurück und probieren Sie einen anderen Zweig aus.
Das DFS ist einfach zu implementieren, wenn Sie eine Adjazenzliste zur Darstellung des Diagramms haben. Zum Beispiel bedeutet adj [A] = {B, C}, 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 eine unendliche Anzahl von diesen. Zum Beispiel ABA, ABABA usw. Oder es ist möglich, 2 Zyklen zu einem 8-ähnlichen Zyklus usw. zusammenzufügen. Der sinnvolle Ansatz besteht darin, nach allen sogenannten einfachen Zyklen zu suchen, die sich nicht kreuzen, außer im Start-/Endpunkt. Wenn Sie möchten, können Sie dann Kombinationen einfacher Zyklen erstellen.
Einer der grundlegenden Algorithmen zum Auffinden aller einfachen Zyklen in einem gerichteten Graphen lautet wie folgt: Führen Sie eine Tiefendurchquerung aller einfachen Pfade (die sich nicht kreuzen) im Graphen 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. Das erste Durchlaufen der Tiefe aller einfachen Pfade ähnelt der ersten Tiefensuche, aber Sie markieren/notieren keine besuchten Knoten, die sich nicht auf dem Stapel befinden, als Stoppunkte.
Der obige Brute-Force-Algorithmus ist schrecklich ineffizient und erzeugt darüber hinaus mehrere Kopien der Zyklen. Es ist jedoch der Ausgangspunkt mehrerer praktischer Algorithmen, die verschiedene Verbesserungen anwenden, um die Leistung zu verbessern und Doppelarbeit zu vermeiden. Ich war vor einiger Zeit überrascht, dass diese Algorithmen nicht ohne weiteres in Lehrbüchern und im Internet verfügbar sind. Also habe ich ein paar Nachforschungen angestellt und 4 solcher Algorithmen und 1 Algorithmus für Zyklen in ungerichteten Diagrammen in einer Open-Source-Bibliothek Java hier implementiert: http://code.google.com/p/niographs/ .
Übrigens, da ich ungerichtete Graphen erwähnte: Der Algorithmus für diese ist unterschiedlich. Bauen 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 durch Kombinieren von 2 oder mehr unterschiedlichen Basiszyklen gefunden werden. Für weitere Einzelheiten siehe z.B. dies: http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf .
Die einfachste Wahl, die ich zur Lösung dieses Problems getroffen habe, war die Verwendung der python lib mit dem Namen networkx.
Es implementiert den in der besten Antwort auf diese Frage erwähnten Johnson-Algorithmus, 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 ']]
Um klarzustellen:
Stark verbundene Komponenten finden alle Untergraphen, in denen mindestens ein Zyklus enthalten ist, nicht alle möglichen Zyklen im Diagramm. z.B. Wenn Sie alle stark verbundenen Komponenten nehmen und jede einzelne zu einem Knoten zusammenfassen (d. h. einen Knoten pro Komponente), erhalten Sie einen Baum ohne Zyklen (tatsächlich eine DAG). Jede Komponente (bei der es sich im Grunde um einen Untergraphen mit mindestens einem Zyklus handelt) kann intern viel mehr mögliche Zyklen enthalten. SCC findet NICHT alle möglichen Zyklen, sondern alle möglichen Gruppen mit Wenn Sie mindestens einen Zyklus gruppieren, enthält das Diagramm keine Zyklen.
um alle einfache Zyklen in einem Graphen zu finden, ist der Johnson-Algorithmus, wie bereits erwähnt, ein Kandidat.
Die DFS-basierten Varianten mit hinteren Kanten finden zwar Zyklen, in vielen Fällen sind es jedoch KEINE minimalen 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 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 hat eine gute zeitliche und räumliche Komplexität.
Wenn Sie jedoch nur MINIMALE Zyklen finden möchten (was bedeutet, dass möglicherweise mehr als ein Zyklus durch einen 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 Johnsons ziemlich langsam.
Einer der absolut einfachsten Wege, 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 Sinn macht, 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 auf die Frage, ob es einen Zyklus gibt. Der Algorithmus ist denkbar einfach. 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 gewichteten Kantengraphen, um alle kürzesten Pfade zwischen allen Knotenpaaren zu finden (daher das Gewichtungsargument). Damit dies korrekt funktioniert, müssen Sie 1 angeben, wenn sich zwischen den Knoten eine gerichtete Kante befindet, andernfalls NO_Edge. Nachdem der Algorithmus ausgeführt wurde, können Sie die Hauptdiagonale überprüfen. Wenn Werte kleiner als NO_Edge sind, nimmt dieser Knoten an einem Zyklus mit einer Länge teil, die dem Wert entspricht. Jeder zweite Knoten desselben Zyklus hat denselben Wert (in der Hauptdiagonale).
Um den Zyklus selbst zu rekonstruieren, müssen wir eine leicht modifizierte Version des Algorithmus mit Eltern-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 übergeordnete Matrix sollte anfangs den Quellscheitelpunktindex in einer Kantenzelle enthalten, wenn sich zwischen den Scheitelpunkten eine Kante befindet, andernfalls -1. Nach der Rückkehr der Funktion wird für jede Kante im Baum mit dem kürzesten Pfad auf den übergeordneten Knoten verwiesen. Und dann ist es einfach, die tatsächlichen Zyklen wiederherzustellen.
Insgesamt 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
Ich habe dies einmal als Interviewfrage erhalten, ich vermute, das ist dir passiert und du kommst hierher, um Hilfe zu holen. Teilen Sie das Problem in drei Fragen auf und es wird einfacher.
- wie bestimmen Sie die nächste gültige Route?
- wie stellen Sie fest, ob ein Punkt verwendet wurde?
- wie vermeidet man es, denselben Punkt erneut zu überqueren?
Problem 1) Verwenden Sie das Iterationsmuster, um Routenergebnisse zu iterieren. Ein guter Ort, um die Logik zum Abrufen der nächsten Route zu platzieren, ist wahrscheinlich "moveNext" Ihres Iterators. Um eine gültige Route zu finden, hängt sie 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 mit einer bestimmten Quelle zu ermitteln.
Problem 2) Verschieben Sie jeden Knoten, sobald Sie ihn gefunden haben, in eine Sammlung. Dies bedeutet, dass Sie leicht feststellen können, ob Sie über einen Punkt "zurückverdoppeln", indem Sie die Sammlung, die Sie gerade erstellen, abfragen.
Problem 3) Wenn Sie irgendwann feststellen, dass Sie sich verdoppeln, können Sie Dinge aus der Sammlung entfernen und "sichern". Versuchen Sie dann ab diesem Punkt 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.
Bei ungerichteten Graphen wurde kürzlich ein Artikel veröffentlicht ( Optimale Auflistung von Zyklen und St-Pfaden in ungerichteten Graphen ) bietet 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 I Ich weiß, dass es Ihre Frage nicht beantwortet, aber da der Titel Ihrer Frage keine Richtung angibt, ist es möglicherweise dennoch nützlich für die Google-Suche
Wenn Sie alle Elementarkreise in einem Graphen finden möchten, können Sie den EC-Algorithmus von JAMES C. TIERNAN verwenden, der seit 1970 auf einer Veröffentlichung veröffentlicht wurde.
Der sehr originelle EC-Algorithmus, wie ich ihn in PHP implementiert habe (ich hoffe, es gibt keine Fehler, siehe unten). Es kann auch Schleifen finden, wenn es welche gibt. Die Schaltkreise in dieser Implementierung (die versuchen, das Original zu klonen) sind die Nicht-Null-Elemente. Null steht hier für Nichtexistenz (Null, wie wir es kennen).
Abgesehen davon folgt eine andere Implementierung, die dem Algorithmus mehr Unabhängigkeit verleiht. Dies bedeutet, dass die Knoten von überall her beginnen können, auch von negativen Zahlen, z. B. -4, -3, -2 usw.
In beiden Fällen müssen die Knoten sequentiell sein.
Möglicherweise müssen Sie die Originalarbeit lesen, 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);
?>
dann ist dies die andere Implementierung, die vom Graphen unabhängiger ist, ohne goto und ohne Array-Werte, stattdessen werden Array-Schlüssel verwendet, der Pfad, der Graph und die Schaltkreise werden als Array-Schlüssel gespeichert (verwenden Sie Array-Werte, wenn Sie möchten, ändern Sie einfach die erforderlichen Werte Linien). Das Beispieldiagramm beginnt bei -4, um die Unabhängigkeit zu verdeutlichen.
<?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.
Beginnen Sie an Knoten X und suchen Sie nach allen untergeordneten Knoten (übergeordnete und untergeordnete Knoten sind gleichwertig, wenn sie nicht gerichtet sind). Markieren Sie diese untergeordneten Knoten als untergeordnete Knoten von X. Markieren Sie von einem solchen untergeordneten Knoten A aus die untergeordneten Knoten von A, X ', wobei X' als 2 Schritte entfernt markiert ist.). Wenn Sie später X drücken und als untergeordnetes Element von X '' markieren, bedeutet dies, dass sich X in einem 3-Knoten-Zyklus befindet. Das Zurückverfolgen zu seinem übergeordneten Element ist einfach (der Algorithmus unterstützt dies so wie er ist nicht, sodass Sie feststellen können, welches übergeordnete Element X 'hat).
Hinweis: Wenn das Diagramm ungerichtet ist oder bidirektionale Kanten aufweist, wird dieser Algorithmus komplizierter, vorausgesetzt, Sie möchten dieselbe Kante nicht zweimal für einen Zyklus durchlaufen.
können Sie nicht eine kleine rekursive Funktion ausführen, um die Knoten zu durchlaufen?
readDiGraph( string pathSoFar, Node x)
{
if(NoChildren) MasterList.add( pathsofar + Node.name ) ;
foreach( child )
{
readDiGraph( pathsofar + "->" + this.name, child)
}
}
wenn Sie eine Tonne von Knoten haben, wird Ihnen der Stapel ausgehen
Es gibt zwei Schritte (Algorithmen), um alle Zyklen in einer DAG zu finden.
Der erste Schritt besteht darin, den Tarjan-Algorithmus zu verwenden, um die Menge der stark verbundenen Komponenten zu finden.
- Beginnen Sie mit einem beliebigen Scheitelpunkt.
- DFS von diesem Scheitelpunkt. Behalten Sie für jeden Knoten x zwei Zahlen, 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]) ist, wobei k alle untergeordneten Elemente von x sind, die nicht das direkte übergeordnete Element von x im dfs-Spanning Tree sind.
- 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:
- 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 die Spur in einen anderen eintritt Scheitel w Es muss eine nicht verwendete 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.
- Solange es einen Scheitelpunkt v gibt, der zur aktuellen Tour gehört, aber angrenzende Kanten hat, die nicht Teil der Tour sind, starten Sie eine andere Spur von v, folgen Sie nicht verwendeten Kanten, bis Sie zu v zurückkehren, und verbinden Sie die auf diese Weise gebildete Tour mit der 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
DFS vom Startknoten s aus, 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 Rückkante im DFS-Baum und zeigt somit einen Zyklus an, der s enthält.
Ich bin über den folgenden Algorithmus gestolpert, der effizienter zu sein scheint als der von Johnson (zumindest für größere Grafiken). Ich bin mir jedoch nicht sicher, was die Leistung im Vergleich zu Tarjans Algorithmus angeht.
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 )
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 Ziffernanzahl 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]);
}
}
Javascript-Lösung mit disjunkt eingestellten 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;
}