Beste Algorithmus zum erkennen von Zyklen in einem gerichteten Graphen

StackOverflow https://stackoverflow.com/questions/261573

Frage

Was ist der effizienteste Algorithmus zum erkennen von Zyklen in einem gerichteten Graphen?

Ich habe einen gerichteten Graphen repräsentiert einen Zeitplan für die jobs, die ausgeführt werden müssen, einen job als Knoten und eine Abhängigkeit wird eine Kante.Ich brauche, um den Fehler zu erkennen bei einem Zyklus in diesem Graphen führt zu zyklischen Abhängigkeiten.

War es hilfreich?

Lösung

Tarjan der starken Komponenten Algorithmus verbunden Zeitkomplexität O(|E| + |V|) hat.

Für andere Algorithmen finden Sie unter stark verbundenen Komponenten auf Wikipedia.

Andere Tipps

Da dies ist eine Liste von jobs, vermute ich, dass an einem gewissen Punkt Sie sind gehen zu Sortieren in einer vorgeschlagenen Reihenfolge der Ausführung.

Wenn das der Fall ist, dann eine topologische Sortieren die Umsetzung kann auf jeden Fall erkennen Zyklen.UNIX tsort sicherlich nicht.Ich denke, es ist wahrscheinlich, daß es daher effizienter zum erkennen von Zyklen in der gleichen Zeit wie tsorting, anstatt in einem separaten Schritt.

So könnte die Frage werden: "wie kann ich möglichst effizient tsort", anstatt "wie kann ich möglichst effizient zu erkennen loops".Die Antwort ist wahrscheinlich "eine Bibliothek", nicht aber, dass der folgende Wikipedia-Artikel:

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

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

Starten Sie mit einem DFS: ein Zyklus liegt vor, wenn und nur wenn ein Hinterkante während DFS entdeckt. Dies erwies sich als Folge der weiß-Pfad theorum.

Der einfachste Weg, es zu tun ist, um hat eine Tiefe erste Traversal (DFT) des Graphen .

Wenn der Graph n Ecken hat, ist dies eine O(n) Zeitkomplexität Algorithmus. Da Sie möglicherweise eine DFT ausgehend von jedem Scheitelpunkt zu tun haben, wird die Gesamtkomplexität O(n^2).

Sie haben zu halten a Stapel alle Vertices in der aktuellen Tiefe erste Traversierung mit , wobei das erste Element der Wurzelknoten ist. Wenn Sie über ein Element kommen, die während der DFT bereits in dem Stapel ist, dann haben Sie einen Zyklus.

Meiner Meinung nach ist der verständlichste Algorithmus für den Zyklus in einem gerichteten Graphen Erfassung ist der Graph-Färbung-Algorithmus.

Grundsätzlich geht der Kurvenfärbungs Algorithmus die Graphen in einer Weise DFS (Tiefensuche, was bedeutet, dass sie vollständig einen Weg erforscht, bevor anderen Weg erforscht). Wenn es eine Hinterkante findet, markiert es die Grafik als eine Schleife enthält.

Für eine tiefer gehende Erklärung des Graphenfärbungs Algorithmus, lesen Sie in diesem Artikel: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

Auch biete ich eine Implementierung von Graphenfärbungs in JavaScript https: / /github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js

Wenn Sie eine „besuchten“ Eigenschaft zu den Knoten nicht hinzuzufügen, verwenden Sie einen Satz (oder Karte) und fügen Sie einfach alle besuchten Knoten zu dem Satz, wenn sie nicht bereits in der Gruppe sind. Verwenden Sie einen eindeutigen Schlüssel oder die Adresse der Objekte als „Schlüssel“.

Dies gibt Ihnen auch die Informationen über die „root“ Knoten der zyklischen Abhängigkeit, die sich als nützlich erweisen, wenn ein Benutzer das Problem zu beheben hat.

Eine andere Lösung ist zu versuchen, die nächste Abhängigkeit finden auszuführen. Dazu müssen Sie einige Stapel haben, wo Sie sich erinnern können, wo Sie jetzt sind und was Sie als nächstes zu tun. Überprüfen Sie, ob eine Abhängigkeit bereits auf diesem Stapel ist, bevor Sie es ausführen. Wenn ja, haben Sie einen Zyklus gefunden.

Während dies eine Komplexität von O (N * M) zu haben scheinen Sie müssen bedenken, dass der Stapel eine sehr begrenzte Tiefe hat (so N klein ist) und dass M kleiner wird mit jeder Abhängigkeit, die Sie abhaken können als " ausgeführt“plus Sie können die Suche beenden, wenn Sie ein Blatt gefunden (so Sie nie hat jeden Knoten überprüfen -> M wird klein, sein).

In MetaMake, habe ich die Grafik als eine Liste von Listen und gelöscht dann jeden Knoten, wie ich sie ausgeführt, die abgeholzt natürlich das Suchvolumen. Ich habe nie wirklich hatte eine unabhängige Prüfung durchgeführt, es ist alles automatisch während der normalen Ausführung passiert ist.

Wenn Sie einen „Test only“ -Modus müssen, fügen Sie einfach einen „Trockenlauf“ Flagge, die die Ausführung der aktuellen Jobs deaktiviert.

Es gibt keinen Algorithmus, der alle Zyklen in einem gerichteten Graphen in Polynomzeit finden. Nehmen wir an, hat der gerichtete Graph n Knoten und jedes Paar der Knoten hat Verbindungen zueinander, was bedeutet, dass Sie einen vollständigen Graphen haben. So eine nicht leere Untergruppe dieser n Knoten gibt einen Zyklus und gibt es 2 ^ n-1 Anzahl solcher Teilmengen. Also kein Polynomialzeitalgorithmus existiert.     So nehme an, Sie haben einen effizienten (nicht dumm) Algorithmus, der die Anzahl der gerichteten Zyklen in einem Diagramm sagen können, können Sie zunächst die stark verbundenen Komponenten finden, dann ist Ihren Algorithmus auf diesen angeschlossenen Komponenten anwenden. Da Zyklen existieren nur innerhalb der Komponenten und nicht zwischen ihnen.

Wenn die DFS eine Kante fest, dass eine verweist auf bereits besuchte Vertex, haben Sie einen Zyklus gibt.

Nach Lemma 22.11 von Cormen et al, Introduction to Algorithms (CLRS).

  

Ein gerichteter Graph G ist azyklisch, wenn und nur wenn eine Tiefensuche von G keine Hinterkanten ergibt.

Dies wurde in mehreren Antworten erwähnt; hier werde ich auch ein Codebeispiel basierend auf 22 von CLRS Kapitel liefern. Das Beispiel Graph ist unten dargestellt.

CLRS‘Pseudo-Code für Tiefensuche lautet:

Im Beispiel in CLRS Abbildung 22,4, Der Graph besteht aus zwei DFS Bäumen: einer der Knoten bestehend u , v , x , und y , und der andere der Knoten W und z . Jeder Baum enthält eine Hinterkante: eine von x v und ein anderes von z bis z (a Selbst Schleife).

Der Schlüssel Erkenntnis ist, dass eine hintere Kante angetroffen wird, wenn in der DFS-VISIT Funktion, während sie über die Nachbarn der v u Iterieren, ein Knoten mit der GRAY Farbe angetroffen wird.

Der folgende Python-Code ist eine Adaption des CLRS‘Pseudo-Code mit einer if Klausel hinzugefügt, die Zyklen erfaßt: 

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 __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 wird die time in CLRS‘Pseudo-Code nicht erfaßt, weil wir bei der Aufdeckung von Zyklen nur interessiert sind. Es gibt auch einige Standardcodes die Adjazenzliste Darstellung eines Graphen aus einer Liste von Kanten für den Bau.

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

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

Das sind genau die hinteren Kanten in dem Beispiel in CLRS Abbildung 22.4.

So wie ich es tue, ist eine topologische Sortierung zu tun, um die Anzahl der Ecken besucht zu zählen. Wenn diese Zahl kleiner als die Gesamtzahl der Knoten in der DAG ist, haben Sie einen Zyklus.

hatte ich dieses Problem in sml (imperativen Programmierung) umgesetzt. Hier ist der Umriss. Finden Sie alle Knoten, die entweder eine indegree oder outdegree von 0. Solche Knoten können nicht Teil eines Zyklus (so entfernen sie) sein. entfernen Weiter alle eingehenden oder ausgehenden Kanten von einem solchen Knoten. Rekursiv anwenden, diesen Prozess zu dem resultierenden Graphen. Wenn Sie am Ende mit einem beliebigen Knoten oder Kante nicht verlassen werden, wird der Graph keine Zyklen haben, sonst hat es.

https://mathoverflow.net/questions/16393/finding-a-cycle -von-fester Länge ich diese Lösung gefällt besonders das beste für 4 Länge:)

Auch Phys Assistent sagt u haben O (V ^ 2) zu tun. Ich glaube, dass wir nur O (V) / O (V + E) benötigen. Wenn der Graph verbunden ist, dann wird die DFS alle Knoten besuchen. Wenn der Graph Untergraphen verbunden hat dann jedes Mal, wenn wir eine DFS an einem Scheitelpunkt dieses Unter Graph laufen wir die angeschlossenen Ecken finden und pflegen diese für den nächsten Lauf der DFS zu prüfen haben. Deshalb ist die Möglichkeit, für jeden Eckpunkt des Laufens ist falsch.

Wie Sie sagten, Sie haben von Arbeitsplätzen setzen, müssen sie in bestimmten Reihenfolge ausgeführt werden. Topological sort gegeben Sie Auftrag für die Planung von Arbeitsplätzen erforderlich (oder für Abhängigkeitsprobleme, wenn es ein direct acyclic graph). Führen dfs und führt eine Liste, und starten Sie Knoten in den Anfang der Liste hinzugefügt, und wenn Sie einen Knoten angetroffen, die bereits besucht wird. Dann fand man einen Zyklus in Graphen.

Wenn eine grafische Darstellung, diese Eigenschaft erfüllt 

|e| > |v| - 1

dann enthält der Graph mindestens auf Zyklus.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top