Bester Algorithmus zum Erkennen von Zyklen in einem gerichteten Graphen

396

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.

Peauters
quelle
13
Sie sagen, Sie möchten alle Zyklen erkennen, aber Ihr Anwendungsfall legt nahe, dass es ausreichend wäre, zu erkennen, ob Zyklen vorhanden sind.
Steve Jessop
29
Es wäre besser, alle Zyklen zu erkennen, damit sie auf einmal repariert werden können, als zu prüfen, zu reparieren, zu überprüfen, zu reparieren usw.
Peauters
2
Sie sollten den Artikel "Finden aller Elementarkreise eines gerichteten Graphen" von Donald B. Johnson lesen. Es werden nur elementare Schaltkreise gefunden, dies sollte jedoch für Ihren Fall ausreichen. Und hier ist meine Java-Implementierung dieses Algorithmus einsatzbereit: github.com/1123/johnson
user152468
Führen Sie DFS mit zusätzlichen Änderungen für den Algorithmus aus: Markieren Sie jeden Knoten, den Sie besucht haben. Wenn Sie einen Knoten besuchen, der bereits besucht wurde, haben Sie einen Cicle. Wenn Sie sich von einem Pfad zurückziehen, heben Sie die Markierung der besuchten Knoten auf.
Hesham Yassin
2
@HeshamYassin, wenn Sie einen Knoten besuchen, den Sie bereits besucht haben, bedeutet dies nicht unbedingt, dass es eine Schleife gibt. Bitte lesen Sie meinen Kommentar cs.stackexchange.com/questions/9676/… .
Maksim Dmitriev

Antworten:

193

Tarjans stark verbundener Komponentenalgorithmus ist O(|E| + |V|)zeitlich komplex.

Weitere Algorithmen finden Sie unter Stark verbundene Komponenten in Wikipedia.

aku
quelle
69
Wie sagt Ihnen das Finden der stark verbundenen Komponenten über die Zyklen aus, die in der Grafik vorhanden sind?
Peter
4
Möglicherweise kann jemand bestätigen, aber der Tarjan-Algorithmus unterstützt keine Zyklen von Knoten, die direkt auf sich selbst zeigen, wie A-> A.
Cédric Guillemette
24
@ Cededr Richtig, nicht direkt. Dies ist kein Fehler in Tarjans Algorithmus, sondern die Art und Weise, wie er für diese Frage verwendet wird. Tarjan findet keine Zyklen direkt , sondern stark verbundene Komponenten. Natürlich impliziert jeder SCC mit einer Größe größer als 1 einen Zyklus. Nichtzyklische Komponenten haben selbst einen Singleton-SCC. Das Problem ist, dass eine Selbstschleife auch von selbst in einen SCC geht. Sie benötigen also eine separate Überprüfung für Selbstschleifen, was ziemlich trivial ist.
mgiuca
13
(alle stark verbundenen Komponenten in der Grafik)! = (alle Zyklen in der Grafik)
optimusfrenk
4
@ aku: Eine dreifarbige DFS hat auch die gleiche Laufzeit 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 !!
KGhatak
73

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 tsortsicherlich. 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:

http://en.wikipedia.org/wiki/Topological_sorting

hat den Pseudocode für einen Algorithmus und eine kurze Beschreibung eines anderen von Tarjan. Beide haben O(|V| + |E|)zeitliche Komplexität.

Steve Jessop
quelle
Eine topologische Sortierung kann Zyklen erkennen, da sie auf einem Tiefensuchalgorithmus beruht. Sie benötigen jedoch zusätzliche Buchhaltung, um Zyklen tatsächlich zu erkennen. Siehe Kurt Peeks richtige Antwort.
Luke Hutchison
33

Der einfachste Weg, dies zu tun, besteht darin , eine Tiefen-First-Traversal (DFT) des Graphen durchzuführen .

Wenn der Graph nEckpunkte hat, ist dies ein O(n)Zeitkomplexitätsalgorithmus. Da Sie möglicherweise von jedem Scheitelpunkt aus eine DFT durchführen müssen, wird die Gesamtkomplexität O(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.

nbro
quelle
21
Dies wäre für einen "normalen" Graphen wahr, für einen gerichteten Graphen jedoch falsch . Betrachten Sie beispielsweise das "Diamantabhängigkeitsdiagramm" mit vier Knoten: A mit Kanten, die auf B und C zeigen, von denen jeder eine Kante auf D zeigt. Ihre DFT-Durchquerung dieses Diagramms von A würde fälschlicherweise zu dem Schluss führen, dass die "Schleife" war Eigentlich ein Zyklus - obwohl es eine Schleife gibt, ist es kein Zyklus, da er nicht durch Befolgen der Pfeile durchlaufen werden kann.
Peter
9
@ Peter Kannst du bitte erklären, wie DFT aus A fälschlicherweise zu dem Schluss kommt, dass es einen Zyklus gibt?
Deepak
10
@Deepak - Tatsächlich habe ich die Antwort von "phys wizard" falsch verstanden: wo er "in den Stapel" schrieb "Ich dachte" wurde bereits gefunden ". Es wäre in der Tat ausreichend (zum Erkennen einer gerichteten Schleife), während der Ausführung einer DFT nach Dupes "im Stapel" zu suchen. Eine Gegenstimme für jeden von euch.
Peter
2
Warum ist die Zeitkomplexität, 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 die O(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 markieren
James Wierzba
Wie Peter sagte, ist dies für gerichtete Graphen unvollständig. Siehe Kurt Peeks richtige Antwort.
Luke Hutchison
32

Nach Lemma 22.11 von Cormen et al., Einführung in Algorithmen (CLRS):

Ein gerichteter Graph G ist genau dann azyklisch, wenn eine Tiefensuche von G keine Hinterkanten ergibt.

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.

Geben Sie hier die Bildbeschreibung ein

Der Pseudocode von CLRS für die Tiefensuche lautet:

Geben Sie hier die Bildbeschreibung ein

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-VISITFunktion beim Iterieren über die Nachbarn vvon uein Knoten mit der GRAYFarbe angetroffen wird.

Der folgende Python-Code ist eine Anpassung des CLRS-Pseudocodes mit einer ifhinzugefügten Klausel, die Zyklen erkennt:

import collections


class Graph(object):
    def __init__(self, edges):
        self.edges = edges
        self.adj = Graph._build_adjacency_list(edges)

    @staticmethod
    def _build_adjacency_list(edges):
        adj = collections.defaultdict(list)
        for edge in edges:
            adj[edge[0]].append(edge[1])
        return adj


def dfs(G):
    discovered = set()
    finished = set()

    for u in G.adj:
        if u not in discovered and u not in finished:
            discovered, finished = dfs_visit(G, u, discovered, finished)


def dfs_visit(G, u, discovered, finished):
    discovered.add(u)

    for v in G.adj[u]:
        # Detect cycles
        if v in discovered:
            print(f"Cycle detected: found a back edge from {u} to {v}.")

        # Recurse into DFS tree
        if v not in finished:
            dfs_visit(G, v, discovered, finished)

    discovered.remove(u)
    finished.add(u)

    return discovered, finished


if __name__ == "__main__":
    G = Graph([
        ('u', 'v'),
        ('u', 'x'),
        ('v', 'y'),
        ('w', 'y'),
        ('w', 'z'),
        ('x', 'v'),
        ('y', 'x'),
        ('z', 'z')])

    dfs(G)

Beachten Sie, dass in diesem Beispiel der timePseudocode 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:

Cycle detected: found a back edge from x to v.
Cycle detected: found a back edge from z to z.

Dies sind genau die Hinterkanten im Beispiel in CLRS Abbildung 22.4.

Kurt Peek
quelle
29

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.

Ajay Garg
quelle
3
Ja, ich denke das gleiche, aber das ist nicht genug, ich poste meinen Weg cs.stackexchange.com/questions/7216/find-the-simple-cycles-in-a-directed-graph
jonaprieto
Wahr. Ajay Garg erzählt nur, wie man "einen Zyklus" findet, was eine Teilantwort auf diese Frage ist. Ihr Link spricht davon, alle Zyklen gemäß der gestellten Frage zu finden, aber es sieht wieder so aus, als würde er denselben Ansatz wie Ajay Garg verwenden, aber auch alle möglichen dfs-Bäume.
Manohar Reddy Poreddy
Dies ist für gerichtete Graphen unvollständig. Siehe Kurt Peeks richtige Antwort.
Luke Hutchison
26

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

Armin Primadi
quelle
8

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.

Aaron Digulla
quelle
7

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.

Yuwen
quelle
1
True, wenn die Anzahl der Knoten als Größe der Eingabe verwendet wird. Sie können die Laufzeitkomplexität auch anhand der Anzahl der Kanten oder sogar Zyklen oder einer Kombination dieser Kennzahlen beschreiben. Der Algorithmus "Finden aller Elementarschaltungen eines gerichteten Graphen" von Donald B. Johnson hat eine Polynomlaufzeit, die durch O ((n + e) ​​(c + 1)) gegeben ist, wobei n die Anzahl der Knoten und e die Anzahl der Kanten ist und c die Anzahl der Elementarschaltungen des Graphen. Und hier ist meine Java-Implementierung dieses Algorithmus: github.com/1123/johnson .
Benutzer152468
4

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.

Rpant
quelle
2

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.

Steve
quelle
4
Das macht keinen Sinn. Wenn der Graph Zyklen hat, gibt es keine topologische Sortierung, was bedeutet, dass jeder korrekte Algorithmus für die topologische Sortierung abgebrochen wird.
Sleske
4
aus Wikipedia: Viele topologische Sortieralgorithmen erkennen auch Zyklen, da dies Hindernisse für die Existenz der topologischen Ordnung sind.
Oleg Mikheev
1
@OlegMikheev Ja, aber Steve sagt "Wenn diese Anzahl kleiner ist als die Gesamtzahl der Eckpunkte in der DAG, haben Sie einen Zyklus", was keinen Sinn ergibt.
nbro
@nbro Ich wette, sie bedeuten eine Variante des topologischen Sortieralgorithmus, die abgebrochen wird, wenn keine topologische Sortierung vorhanden ist (und dann nicht alle Scheitelpunkte besuchen).
Maaartinus
Wenn Sie eine topologische Sortierung in einem Diagramm mit Zyklus durchführen, erhalten Sie eine Reihenfolge mit der geringsten Anzahl fehlerhafter Kanten (Bestellnummer> Bestellnummer des Nachbarn). Aber nachdem Sie die Sortierung durchführen müssen, ist es einfach, diese schlechten Kanten zu erkennen, was dazu führt, dass ein Diagramm mit einem Zyklus
erkannt
2

/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.

Amitgoswami
quelle
1

Wenn die DFS eine Kante findet, die auf einen bereits besuchten Scheitelpunkt zeigt, haben Sie dort einen Zyklus.

Mafonya
quelle
1
Schlägt bei 1,2,3: 1,2 fehl; 1,3; 2,3;
laute Katze
4
@JakeGreene Schauen Sie hier: i.imgur.com/tEkM5xy.png Einfach genug, um zu verstehen. Nehmen wir an, Sie beginnen bei 0. Dann gehen Sie zum Knoten 1, keine Pfade mehr von dort, die Reucrsion geht zurück. Jetzt besuchen Sie Knoten 2, der eine Kante zum Scheitelpunkt 1 hat, der bereits besucht wurde. Ihrer Meinung nach hätten Sie dann einen Zyklus - und Sie haben keinen wirklich
lauten Katze
3
@kittyPL Dieses Diagramm enthält keinen Zyklus. Aus Wikipedia: "Ein gerichteter Zyklus in einem gerichteten Graphen ist eine Folge von Scheitelpunkten, die am gleichen Scheitelpunkt beginnen und enden, so dass für jeweils zwei aufeinanderfolgende Scheitelpunkte des Zyklus eine Kante existiert, die vom früheren Scheitelpunkt zum späteren gerichtet ist." müssen in der Lage sein, einem Pfad von V zu folgen, der für einen gerichteten Zyklus zurück zu V führt. Mafonyas Lösung funktioniert für das gegebene Problem
Jake Greene
2
@ JakeGreene Natürlich nicht. Wenn Sie Ihren Algorithmus verwenden und ab 1 beginnen, erkennen Sie ohnehin einen Zyklus ... Dieser Algorithmus ist einfach schlecht ... Normalerweise reicht es aus, rückwärts zu gehen, wenn Sie auf einen besuchten Scheitelpunkt stoßen.
laute Katze
6
@kittyPL DFS erkennt Zyklen vom angegebenen Startknoten. Wenn Sie jedoch DFS ausführen, müssen Sie besuchte Knoten färben, um eine Querkante von einer Hinterkante zu unterscheiden. Wenn Sie einen Scheitelpunkt zum ersten Mal besuchen, wird er grau, und Sie werden schwarz, sobald alle Kanten besucht wurden. Wenn Sie bei der DFS einen grauen Scheitelpunkt treffen, ist dieser Scheitelpunkt ein Vorfahr (dh Sie haben einen Zyklus). Wenn der Scheitelpunkt schwarz ist, ist es nur eine Kreuzkante.
Kyrra
0

Wie Sie sagten, haben Sie eine Reihe von Jobs, die in einer bestimmten Reihenfolge ausgeführt werden müssen. Topological sortvorausgesetzt, Sie benötigen die Reihenfolge für die Planung von Jobs (oder für Abhängigkeitsprobleme, wenn es sich um a handelt direct acyclic graph). Führen Sie dfseine 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.

Bhagwati Malav
quelle
-11

Wenn ein Graph diese Eigenschaft erfüllt

|e| > |v| - 1

dann enthält der Graph mindestens einen Zyklus.

Dharmendra Singh
quelle
10
Dies gilt möglicherweise für ungerichtete Diagramme, aber sicherlich nicht für gerichtete Diagramme.
Hans-Peter Störr
6
Ein Gegenbeispiel wäre A-> B, B-> C, A-> C.
Benutzer152468
Nicht alle Eckpunkte haben Kanten.
Debanjan Dhar