Was ist der effizienteste Algorithmus zum Erkennen aller Zyklen innerhalb eines gerichteten Graphen?
Ich habe ein gerichtetes Diagramm, das einen Zeitplan von Jobs darstellt, die ausgeführt werden müssen, wobei ein Job ein Knoten und eine Abhängigkeit eine Kante ist. Ich muss den Fehlerfall eines Zyklus in diesem Diagramm erkennen, der zu zyklischen Abhängigkeiten führt.
algorithm
graph-theory
directed-graph
Peauters
quelle
quelle
Antworten:
Tarjans stark verbundener Komponentenalgorithmus ist
O(|E| + |V|)
zeitlich komplex.Weitere Algorithmen finden Sie unter Stark verbundene Komponenten in Wikipedia.
quelle
O(|E| + |V|)
. Wenn ein grauer Knoten einen anderen grauen Knoten findet, verwenden wir die Farbcodierung Weiß (nie besucht), Grau (aktueller Knoten wird besucht, aber alle erreichbaren Knoten werden noch nicht besucht) und Schwarz (alle erreichbaren Knoten werden zusammen mit dem aktuellen Knoten besucht). Ich habe einen Zyklus. [So ziemlich das, was wir in Cormens Algorithmusbuch haben]. Ich frage mich, ob 'Tarjans Algorithmus' irgendeinen Vorteil gegenüber einer solchen DFS hat !!Angesichts der Tatsache, dass dies ein Zeitplan für Jobs ist, vermute ich, dass Sie sie irgendwann in eine vorgeschlagene Ausführungsreihenfolge sortieren werden.
Wenn dies der Fall ist, kann eine topologische Sortierimplementierung in jedem Fall Zyklen erkennen. UNIX
tsort
sicherlich. Ich halte es daher für wahrscheinlich, dass es effizienter ist, Zyklen gleichzeitig mit dem Sortieren zu erkennen, als in einem separaten Schritt.Die Frage könnte also lauten: "Wie sortiere ich am effizientesten?" Und nicht: "Wie erkenne ich Schleifen am effizientesten?". Worauf die Antwort wahrscheinlich lautet "benutze eine Bibliothek", aber andernfalls der folgende Wikipedia-Artikel:
hat den Pseudocode für einen Algorithmus und eine kurze Beschreibung eines anderen von Tarjan. Beide haben
O(|V| + |E|)
zeitliche Komplexität.quelle
Der einfachste Weg, dies zu tun, besteht darin , eine Tiefen-First-Traversal (DFT) des Graphen durchzuführen .
Wenn der Graph
n
Eckpunkte hat, ist dies einO(n)
Zeitkomplexitätsalgorithmus. Da Sie möglicherweise von jedem Scheitelpunkt aus eine DFT durchführen müssen, wird die GesamtkomplexitätO(n^2)
.Sie müssen einen Stapel verwalten, der alle Scheitelpunkte in der aktuellen Tiefe der ersten Durchquerung enthält , wobei das erste Element der Wurzelknoten ist. Wenn Sie während der DFT auf ein Element stoßen, das sich bereits im Stapel befindet, haben Sie einen Zyklus.
quelle
O(n)
während Sie vorschlagen, den Stapel zu überprüfen, um festzustellen, ob er bereits einen besuchten Knoten enthält? Durch das Scannen des Stapels wird dieO(n)
Laufzeit verlängert, da der Stapel auf jedem neuen Knoten gescannt werden muss. Sie können erreichen,O(n)
wenn Sie die besuchten Knoten markierenNach Lemma 22.11 von Cormen et al., Einführung in Algorithmen (CLRS):
Dies wurde in mehreren Antworten erwähnt; Hier werde ich auch ein Codebeispiel bereitstellen, das auf Kapitel 22 von CLRS basiert. Das Beispieldiagramm ist unten dargestellt.
Der Pseudocode von CLRS für die Tiefensuche lautet:
In dem Beispiel in CLRS Abbildung 22.4 besteht der Graph aus zwei DFS-Bäumen: einer besteht aus den Knoten u , v , x und y und der andere aus den Knoten w und z . Jeder Baum enthält eine Hinterkante: eine von x nach v und eine von z nach z (eine Selbstschleife).
Die Schlüsselrealisierung besteht darin, dass eine Hinterkante angetroffen wird, wenn in der
DFS-VISIT
Funktion beim Iterieren über die Nachbarnv
vonu
ein Knoten mit derGRAY
Farbe angetroffen wird.Der folgende Python-Code ist eine Anpassung des CLRS-Pseudocodes mit einer
if
hinzugefügten Klausel, die Zyklen erkennt:Beachten Sie, dass in diesem Beispiel der
time
Pseudocode in CLRS nicht erfasst wird, da wir nur an der Erkennung von Zyklen interessiert sind. Es gibt auch einen Boilerplate-Code zum Erstellen der Adjazenzlistendarstellung eines Diagramms aus einer Liste von Kanten.Wenn dieses Skript ausgeführt wird, wird die folgende Ausgabe gedruckt:
Dies sind genau die Hinterkanten im Beispiel in CLRS Abbildung 22.4.
quelle
Beginnen Sie mit einer DFS: Ein Zyklus existiert genau dann, wenn während der DFS eine Hinterkante entdeckt wird . Dies wird als Ergebnis des White-Path-Theorums bewiesen.
quelle
Meiner Meinung nach ist der Graph-Coloring-Algorithmus der verständlichste Algorithmus zur Erkennung des Zyklus in einem gerichteten Graphen.
Grundsätzlich führt der Algorithmus zum Färben von Graphen den Graphen in einer DFS-Weise durch (Depth First Search, dh, er erkundet einen Pfad vollständig, bevor er einen anderen Pfad untersucht). Wenn eine Hinterkante gefunden wird, wird das Diagramm als eine Schleife enthaltend markiert.
Eine ausführliche Erläuterung des Algorithmus zum Färben von Grafiken finden Sie in diesem Artikel: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/
Außerdem biete ich eine Implementierung der Grafikfärbung in JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js an
quelle
Wenn Sie den Knoten keine "besuchte" Eigenschaft hinzufügen können, verwenden Sie einen Satz (oder eine Karte) und fügen Sie einfach alle besuchten Knoten zum Satz hinzu, es sei denn, sie befinden sich bereits im Satz. Verwenden Sie einen eindeutigen Schlüssel oder die Adresse der Objekte als "Schlüssel".
Auf diese Weise erhalten Sie auch Informationen zum "Root" -Knoten der zyklischen Abhängigkeit, die nützlich sind, wenn ein Benutzer das Problem beheben muss.
Eine andere Lösung besteht darin, zu versuchen, die nächste auszuführende Abhängigkeit zu finden. Dazu müssen Sie einen Stapel haben, in dem Sie sich erinnern können, wo Sie sich gerade befinden und was Sie als Nächstes tun müssen. Überprüfen Sie, ob bereits eine Abhängigkeit von diesem Stapel vorhanden ist, bevor Sie sie ausführen. Wenn ja, haben Sie einen Zyklus gefunden.
Während dies eine Komplexität von O (N * M) zu haben scheint, müssen Sie sich daran erinnern, dass der Stapel eine sehr begrenzte Tiefe hat (also ist N klein) und dass M mit jeder Abhängigkeit kleiner wird, die Sie als "ausgeführt" plus abhaken können Sie können die Suche beenden, wenn Sie ein Blatt gefunden haben (Sie müssen also nie jeden Knoten überprüfen -> M ist auch klein).
In MetaMake habe ich das Diagramm als Liste von Listen erstellt und dann jeden Knoten bei der Ausführung gelöscht, wodurch das Suchvolumen natürlich verringert wurde. Ich musste eigentlich nie eine unabhängige Prüfung durchführen, alles geschah automatisch während der normalen Ausführung.
Wenn Sie einen "Nur Test" -Modus benötigen, fügen Sie einfach ein "Trockenlauf" -Flag hinzu, das die Ausführung der eigentlichen Jobs deaktiviert.
quelle
Es gibt keinen Algorithmus, der alle Zyklen in einem gerichteten Graphen in Polynomzeit finden kann. Angenommen, der gerichtete Graph hat n Knoten und jedes Knotenpaar hat Verbindungen zueinander, was bedeutet, dass Sie einen vollständigen Graphen haben. Jede nicht leere Teilmenge dieser n Knoten zeigt also einen Zyklus an, und es gibt 2 ^ n-1 Anzahl solcher Teilmengen. Es existiert also kein Polynomzeitalgorithmus. Angenommen, Sie haben einen effizienten (nicht dummen) Algorithmus, der Ihnen die Anzahl der gerichteten Zyklen in einem Diagramm angibt. Sie können zuerst die stark verbundenen Komponenten finden und dann Ihren Algorithmus auf diese verbundenen Komponenten anwenden. Da Zyklen nur innerhalb der Komponenten existieren und nicht zwischen ihnen.
quelle
Ich hatte dieses Problem in sml (imperative Programmierung) implementiert. Hier ist der Umriss. Suchen Sie alle Knoten, die entweder einen Grad oder einen Grad von 0 haben. Solche Knoten können nicht Teil eines Zyklus sein (entfernen Sie sie daher). Entfernen Sie als Nächstes alle eingehenden oder ausgehenden Kanten von solchen Knoten. Wenden Sie diesen Prozess rekursiv auf das resultierende Diagramm an. Wenn Sie am Ende keinen Knoten oder keine Kante mehr haben, hat der Graph keine Zyklen, sonst hat er.
quelle
Ich mache eine topologische Sortierung, bei der die Anzahl der besuchten Scheitelpunkte gezählt wird. Wenn diese Anzahl kleiner als die Gesamtzahl der Scheitelpunkte in der DAG ist, haben Sie einen Zyklus.
quelle
/mathpro/16393/finding-a-cycle-of-fixed-length Ich mag diese Lösung am besten speziell für 4 Längen :)
Auch der Phys-Assistent sagt, du musst O machen (V ^ 2). Ich glaube, wir brauchen nur O (V) / O (V + E). Wenn das Diagramm verbunden ist, besucht DFS alle Knoten. Wenn der Graph Untergraphen verbunden hat, finden wir jedes Mal, wenn wir eine DFS auf einem Scheitelpunkt dieses Untergraphen ausführen, die verbundenen Scheitelpunkte und müssen diese für den nächsten Lauf der DFS nicht berücksichtigen. Daher ist die Möglichkeit, für jeden Scheitelpunkt ausgeführt zu werden, falsch.
quelle
Wenn die DFS eine Kante findet, die auf einen bereits besuchten Scheitelpunkt zeigt, haben Sie dort einen Zyklus.
quelle
Wie Sie sagten, haben Sie eine Reihe von Jobs, die in einer bestimmten Reihenfolge ausgeführt werden müssen.
Topological sort
vorausgesetzt, Sie benötigen die Reihenfolge für die Planung von Jobs (oder für Abhängigkeitsprobleme, wenn es sich um a handeltdirect acyclic graph
). Führen Siedfs
eine Liste aus, pflegen Sie sie und fügen Sie am Anfang der Liste einen Knoten hinzu. Wenn Sie auf einen Knoten gestoßen sind, der bereits besucht wurde. Dann haben Sie in einem bestimmten Diagramm einen Zyklus gefunden.quelle
Wenn ein Graph diese Eigenschaft erfüllt
dann enthält der Graph mindestens einen Zyklus.
quelle