Bester Algorithmus zur Erkennung von Zyklen in einem gerichteten Graphen

Question

Gibt es einen effizienten Algorithmus zur Erkennung von Zyklen innerhalb eines gerichteten Graphen?

Ich habe einen gerichteten Graphen, der einen Zeitplan von auszuführenden Aufträgen darstellt, wobei ein Auftrag ein Knoten und eine Abhängigkeit eine Kante ist. Ich muss den Fehlerfall eines Zyklus innerhalb dieses Graphen erkennen, der zu zyklischen Abhängigkeiten führt.

Answer 1

Beginnen Sie mit einem DFS: Ein Zyklus existiert nur dann, wenn a die Hinterkante wird beim DFS entdeckt . Dies wird als Ergebnis des Theorems des weißen Pfades bewiesen.

Answer 2

Wenn Sie den Knoten keine Eigenschaft "besucht" hinzufügen können, verwenden Sie eine Menge (oder eine Karte) und fügen Sie einfach alle besuchten Knoten der Menge hinzu, sofern sie nicht bereits in der Menge enthalten sind. Verwenden Sie einen eindeutigen Schlüssel oder die Adresse der Objekte als "Schlüssel".

Dadurch erhalten Sie auch Informationen über den "Root"-Knoten der zyklischen Abhängigkeit, was sich als nützlich erweisen wird, 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, auf dem Sie sich merken können, wo Sie sich gerade befinden und was Sie als nächstes tun müssen. Prüfen Sie, ob sich eine Abhängigkeit bereits auf diesem Stapel befindet, bevor Sie sie ausführen. Wenn ja, haben Sie einen Zyklus gefunden.

Auch wenn dies eine Komplexität von O(N*M) zu haben scheint, darf man nicht vergessen, dass der Stapel eine sehr begrenzte Tiefe hat (daher ist N klein) und dass M mit jeder Abhängigkeit, die man als "ausgeführt" abhaken kann, kleiner wird, und dass man die Suche beenden kann, wenn man ein Blatt gefunden hat (daher kann man niemals jeden Knoten überprüfen müssen -> M wird ebenfalls klein sein).

In MetaMake habe ich den Graphen als eine Liste von Listen erstellt und dann jeden Knoten bei der Ausführung gelöscht, was natürlich das Suchvolumen reduzierte. Ich musste eigentlich nie eine unabhängige Prüfung durchführen, das geschah alles 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 Aufträge deaktiviert.

Answer 3

Es gibt keinen Algorithmus, der alle Zyklen in einem gerichteten Graphen in polynomieller Zeit finden kann. Nehmen wir an, der gerichtete Graph hat n Knoten und jedes Knotenpaar hat Verbindungen zueinander, d.h. es handelt sich um einen vollständigen Graphen. Jede nicht leere Teilmenge dieser n Knoten ist also ein Zyklus, und es gibt 2^n-1 solcher Teilmengen. Es gibt also keinen Polynomialzeit-Algorithmus. Angenommen, man hat einen effizienten (nicht dummen) Algorithmus, der die Anzahl der gerichteten Zyklen in einem Graphen ermitteln kann, so kann man zunächst die stark zusammenhängenden Komponenten finden und dann den Algorithmus auf diese Komponenten anwenden. Denn Zyklen gibt es nur innerhalb der Komponenten und nicht zwischen ihnen.

Answer 4

Ich führe eine topologische Sortierung durch und zähle die Anzahl der besuchten Scheitelpunkte. Wenn diese Zahl kleiner ist als die Gesamtzahl der Knoten in der DAG, haben Sie einen Zyklus.

Answer 5

Wie Sie sagten, haben Sie eine Reihe von Aufträgen, die in einer bestimmten Reihenfolge ausgeführt werden müssen. Topological sort für die Planung von Aufträgen (oder für Abhängigkeitsprobleme, wenn es sich um eine direct acyclic graph ). ausführen. dfs und pflegen Sie eine Liste, und beginnen Sie mit dem Hinzufügen von Knoten am Anfang der Liste, und wenn Sie auf einen Knoten stoßen, der bereits besucht wird. Dann haben Sie einen Zyklus im gegebenen Graphen gefunden.