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

Tarjans Algorithmus für stark verbundene Komponenten hat O(|E| + |V|) Zeitkomplexität.

Für andere Algorithmen, siehe Stark verbundene Komponenten auf Wikipedia.

Answer 2

Da es sich hier um einen Stellenplan handelt, vermute ich, dass Sie an einem bestimmten Punkt sortieren in einen Vorschlag für die Reihenfolge der Ausführung.

Wenn das der Fall ist, dann muss ein topologische Sortierung Implementierung kann in jedem Fall Zyklen erkennen. UNIX tsort tut es sicherlich. Ich denke, es ist daher wahrscheinlich effizienter, die Zyklen gleichzeitig mit der Sortierung zu erkennen, als in einem separaten Schritt.

Die Frage könnte also lauten: "Wie kann ich am effizientesten sortieren?" und nicht: "Wie kann ich am effizientesten Schleifen erkennen?". Die Antwort darauf lautet wahrscheinlich "eine Bibliothek verwenden", andernfalls den folgenden Wikipedia-Artikel:

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

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

Answer 3

Gemäß Lemma 22.11 von Cormen et al, Einführung in Algorithmen (CLRS):

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

Dies wurde bereits in mehreren Antworten erwähnt; hier werde ich auch ein Codebeispiel auf der Grundlage von Kapitel 22 des CLRS bereitstellen. Das Beispieldiagramm ist unten abgebildet.

CLRS-Pseudocode für Deep-First-Suchläufe:

In dem Beispiel in CLRS-Abbildung 22.4 besteht der Graph aus zwei DFS-Bäumen: Einer besteht aus Knoten u , v , x y y und der andere der Knotenpunkte w y z . Jeder Baum enthält eine Rückkante: eine von x a v und eine weitere von z a z (eine Selbstschleife).

Die wichtigste Erkenntnis ist, dass eine hintere Kante dann auftritt, wenn in der DFS-VISIT Funktion, während sie über die Nachbarn iteriert v の u wird ein Knoten gefunden, der die GRAY Farbe.

Der folgende Python-Code ist eine Anpassung des Pseudocodes von CLRS mit einer if Klausel zur Erkennung von Zyklen hinzugefügt:

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 die time im Pseudocode von CLRS wird nicht erfasst, da wir nur an der Erkennung von Zyklen interessiert sind. Es gibt auch einige Standardcodes für die Erstellung der Adjazenzlisten-Darstellung eines Graphen aus einer Liste von Kanten.

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

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 in dem Beispiel in CLRS-Abbildung 22.4.

Answer 4

Am einfachsten ist es, wenn Sie ein "depth first traversal" (DFT) des Graphen durchführen .

Wenn der Graph eine n Scheitelpunkte, ist dies eine O(n) Algorithmus mit hoher Zeitkomplexität. Da Sie möglicherweise von jedem Scheitelpunkt aus eine DFT durchführen müssen, wird die Gesamtkomplexität O(n^2) .

Sie müssen eine Stapel, der alle Scheitelpunkte des aktuellen Durchlaufs in der ersten Tiefe enthält , dessen erstes Element der Wurzelknoten ist. Wenn Sie während der DFT auf ein Element stoßen, das sich bereits auf dem Stapel befindet, haben Sie einen Zyklus.

Answer 5

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

Grundsätzlich durchläuft der Graphfärbungsalgorithmus den Graphen nach dem DFS-Prinzip (Depth First Search, d. h. er erkundet einen Pfad vollständig, bevor er einen anderen Pfad erkundet). Wenn er eine Rückkante findet, markiert er den Graphen als eine Schleife enthaltend.

Eine ausführliche Erläuterung des Algorithmus zur Graphenfärbung finden Sie in diesem Artikel: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

Außerdem stelle ich eine Implementierung der Graphenfärbung in JavaScript zur Verfügung https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js