Schnellster Algorithmus eine Schleife in einem Diagramm zum Detektieren

Question

Bei einem ungerichteten Graphen, was ist der beste Algorithmus, um festzustellen, ob es einen Zyklus enthält oder nicht?

eine Breite erste oder Tiefensuche, während Spur des besuchten Knoten zu halten, ist eine Methode, aber es ist O (n ^ 2). Gibt es etwas schneller?

Answer 1

Die BFS und DFS-Algorithmus für Graphen G (V, E) Zeitkomplexität von O (| V | + | E |). So wie Sie es lineare Abhängigkeit von Eingang sehen können. Sie können einige Heuristiken im Fall führen Sie sehr spezielle grafische Darstellung haben, aber im Allgemeinen ist es nicht so schlimm DFS für das verwenden. Sie können einige Informationen rel="noreferrer">. Auf jeden Fall müssen Sie die ganze Graph durchlaufen.

Answer 2

Hier ist Ihr O(V) Algorithmus:

def hasCycles(G, V, E): 
    if E>=V:
        return True
    else:
        # here E<V
        # perform O(E+V) = O(V) algorithm 
        ...

Das ... kann mit DFS durchgeführt werden. Wenn Sie E<V haben und Kanten sind in sinnvoller Weise (als Liste) gespeichert sind, können Sie wahrscheinlich tun O (E) + Protokolle, die den gesamten Algorithmus O(min(E,V))+logs machen würde.

Hoffnung mögen Sie diese Antwort, wenn auch ein wenig spät!

Answer 3

Prüfung auf das Vorhandensein eines Zyklus in einem Graphen G (V, E) Tiefensuche mit O (| V |, | E |), wenn der Graph einer Adjazenzliste dargestellt wird mit

.

Es ist notwendig, das gesamte Graphen zu überqueren, dort zu zeigen, sind keine Zyklen. Wenn Sie einfach nur Interesse an der An- / Abwesenheit eines Zyklus sind, können Sie offensichtlich an dem Punkt beenden ein Zyklus entdeckt wird.

Answer 4

Wenn Sie eine einfache grafische Darstellung haben, können Sie die zyklomatische Zahl berechnen:

C = E − N + P

, wobei C die Anzahl der Zyklen ist, E die Anzahl der Kanten ist, N die Anzahl von Knoten, und P ist die Anzahl der Komponenten. Wenn Sie ist mit Grafik, es ist:

C = E - N + 1