Bester Algorithmus zur Erkennung von Zyklen in einem gerichteten Graphen

Da dies ein Zeitplan für Jobs ist, vermute ich, dass Sie sie irgendwann in eine vorgeschlagene Ausführungsreihenfolge sortieren .

Wenn dies der Fall ist, kann eine topologische Implementierung auf jeden Fall Zyklen erkennen. UNIX tsort sicherlich. Ich halte es für wahrscheinlich, dass es daher effizienter ist, Zyklen gleichzeitig mit der Sortierung zu erkennen, als in einem separaten Schritt.

So könnte die Frage lauten: "Wie sortiere ich am effizientesten?" Und nicht: "Wie erkenne ich Schleifen am effizientesten?". Worauf die Antwort wahrscheinlich "benutze eine Bibliothek" lautet, scheitert aber daran, dass 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|) Zeitkomplexität.

Beginnen Sie mit einem DFS: Ein Zyklus existiert genau dann, wenn ein Back-Edge während des DFS entdeckt wird. Dies wird durch das White-Path-Theorum bewiesen.

Der einfachste Weg, dies zu tun, ist erstmaliges Durchlaufen der Tiefe (DFT) des Graphen.

Wenn der Graph n Eckpunkte hat, ist dies ein O(n) Zeitkomplexitätsalgorithmus. Da Sie möglicherweise von jedem Eckpunkt aus eine DFT ausführen müssen, wird die Gesamtkomplexität zu O(n^2).

Sie müssen ein Stapel, der alle Scheitelpunkte in der ersten Durchquerung der aktuellen Tiefe enthält pflegen, 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.

Meiner Meinung nach ist der Graph-Coloring-Algorithmus der verständlichste Algorithmus zur Erkennung des Zyklus in einem gerichteten Graphen.

Grundsätzlich wandelt der Graph-Farbalgorithmus den Graphen in einer DFS-Weise (Depth First Search, dh, er untersucht einen Pfad vollständig, bevor er einen anderen Pfad untersucht). Wenn es eine Hinterkante findet, markiert es das Diagramm als eine Schleife enthaltend.

In diesem Artikel finden Sie eine ausführliche Erläuterung des Diagrammfärbealgorithmus: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

Außerdem biete ich eine Implementierung der Grafikfärbung in JavaScript an https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js

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 über den "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 sich bereits eine Abhängigkeit auf diesem Stapel befindet, bevor Sie ihn 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 N klein ist) und dass M mit jeder Abhängigkeit kleiner wird, die Sie als "ausgeführt" plus abhaken können Sie können die Suche stoppen, wenn Sie ein Blatt gefunden haben (also müssen Sie nie jeden Knoten überprüfen -> M wird auch klein sein).

In MetaMake habe ich das Diagramm als Liste von Listen erstellt und dann bei der Ausführung jeden Knoten gelöscht, wodurch sich das Suchvolumen auf natürliche Weise verringert hat. Ich musste nie wirklich 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 tatsächlichen Jobs deaktiviert.

Es gibt keinen Algorithmus, der alle Zyklen in einem gerichteten Graphen in Polynomialzeit findet. Angenommen, der gerichtete Graph hat n Knoten und jedes Knotenpaar hat Verbindungen miteinander, was bedeutet, dass Sie einen vollständigen Graphen haben. Jede nicht leere Untermenge dieser n Knoten gibt einen Zyklus an und es gibt 2 ^ n-1 Anzahl solcher Untermengen. Es gibt also keinen polynomialen Zeitalgorithmus. 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.

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 basierend auf Kapitel 22 von CLRS bereitstellen. Das Beispieldiagramm ist unten dargestellt.

Der CLRS-Pseudocode für die Tiefensuche lautet:

Im Beispiel in CLRS Abbildung 22.4 besteht das Diagramm aus zwei DFS-Bäumen: einem aus Knoten u , v , x und y und der andere der Knoten w und z . Jeder Baum enthält eine hintere Kante: eine von x bis v und eine andere von z bis z (eine Selbstschleife).

Die Schlüsselerkenntnis ist, dass eine Hinterkante angetroffen wird, wenn im DFS-VISIT Funktion, während Sie über die Nachbarn v von u iterieren, wird ein Knoten mit der Farbe GRAY gefunden.

Der folgende Python Code ist eine Anpassung des CLRS-Pseudocodes mit einer if -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 discovered and v not in finished:
            dfs_visit(G, v, discovered, finished)

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

    return discovered, finished


if __== "__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 time im CLRS-Pseudocode nicht erfasst wird, da wir nur daran interessiert sind, Zyklen zu erkennen. Es gibt auch einen Boilerplate-Code zum Erstellen der Adjazenzlistendarstellung eines Graphen aus einer Liste von Kanten.

Wenn dieses Skript ausgeführt wird, wird die folgende Ausgabe ausgegeben:

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

Dies sind genau die hinteren Kanten im Beispiel in CLRS Abbildung 22.4.

Ich hatte dieses Problem in sml (Imperative Programming) implementiert. Hier ist der Umriss. Finden Sie alle Knoten, die entweder einen Innen- oder Außengrad von 0 haben. Solche Knoten können nicht Teil eines Zyklus sein (also entfernen Sie sie). 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 mehr.

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

So mache ich eine topologische Sortierung, bei der die Anzahl der besuchten Scheitelpunkte gezählt wird. Wenn diese Anzahl kleiner ist als die Gesamtanzahl der Eckpunkte in der DAG, haben Sie einen Zyklus.

https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length Ich mag diese Lösung am besten speziell für 4 Länge :)

Der Assistent sagt auch, dass du O (V ^ 2) machen musst. Ich glaube, wir brauchen nur O (V)/O (V + E). Wenn der Graph verbunden ist, besucht die DFS alle Knoten. Wenn der Graph verbundene Subgraphen hat, werden wir jedes Mal, wenn wir einen DFS auf einem Scheitelpunkt dieses Subgraphen ausführen, die verbundenen Scheitelpunkte finden und müssen diese beim nächsten Durchlauf des DFS nicht berücksichtigen. Daher ist die Möglichkeit, für jeden Scheitelpunkt zu laufen, falsch.

Wie Sie sagten, Sie haben eine Reihe von Jobs, die in einer bestimmten Reihenfolge ausgeführt werden müssen. Topological sort, Wenn Sie einen Auftrag für die Einplanung von Aufträgen benötigen (oder für Abhängigkeitsprobleme, wenn es sich um einen direct acyclic graph Handelt). Führen Sie dfs aus, pflegen Sie eine Liste und beginnen Sie, Knoten am Anfang der Liste hinzuzufügen, und wenn Sie auf einen Knoten gestoßen sind, der bereits besucht wurde. Dann haben Sie in der angegebenen Grafik einen Zyklus gefunden.