Wie überprüfe ich, ob ein gerichteter Graph azyklisch ist?

82

Wie überprüfe ich, ob ein gerichteter Graph azyklisch ist? Und wie heißt der Algorithmus? Ich würde mich über eine Referenz freuen.

nes1983
quelle
Ein weiterer Fall zugunsten einer Möglichkeit, falsche Antworten auf SO zu "korrigieren".
Sparr
2
Also, ähm, ich interessiere mich hauptsächlich für die Zeit, die benötigt wird, um es zu finden. Also brauche ich nur den abstrakten Algorithmus.
nes1983
Sie müssen alle Kanten durchlaufen und alle Scheitelpunkte überprüfen, sodass die Untergrenze O (| V | + | E |) ist. DFS und BFS sind beide gleich komplex, aber DFS ist einfacher zu codieren, wenn Sie eine Rekursion haben, da dies den Stapel für Sie verwaltet ...
ShuggyCoUk
DFS ist nicht die gleiche Komplexität. Betrachten Sie den Graphen mit den Knoten {1 .. N} und Kanten in der Form {(a, b) | a <b}. Dieser Graph ist azyklisch und dennoch wäre DFS O (n!)
FryGuy
1
DFS ist niemals O (n!). Es besucht jeden Knoten einmal und jede Kante höchstens zweimal. Also O (| V | + | E |) oder O (n).
Jay Conrod

Antworten:

94

Ich würde versuchen, das Diagramm topologisch zu sortieren , und wenn Sie nicht können, dann hat es Zyklen.

FryGuy
quelle
2
Wie hatte das keine Stimmen? Es ist linear auf Knoten + Kanten und den O (n ^ 2) -Lösungen weit überlegen!
Loren Pechtel
5
In vielen Fällen kann eine DFS (siehe Antwort von J.Conrod) einfacher sein, insbesondere wenn eine DFS trotzdem durchgeführt werden muss. Aber das hängt natürlich vom Kontext ab.
Sleske
1
Die topologische Reihenfolge wird in einer Endlosschleife sein, aber es würde uns nicht sagen, wo der Zyklus auftritt ...
Baradwaj Aryasomayajula
34

Eine einfache Tiefensuche ist nicht gut genug, um einen Zyklus zu finden. Es ist möglich, einen Knoten in einer DFS mehrmals zu besuchen, ohne dass ein Zyklus vorhanden ist. Je nachdem, wo Sie beginnen, besuchen Sie möglicherweise auch nicht das gesamte Diagramm.

Sie können in einer verbundenen Komponente eines Diagramms wie folgt nach Zyklen suchen. Suchen Sie einen Knoten, der nur ausgehende Kanten hat. Wenn es keinen solchen Knoten gibt, gibt es einen Zyklus. Starten Sie an diesem Knoten eine DFS. Überprüfen Sie beim Durchlaufen jeder Kante, ob die Kante auf einen Knoten zurückweist, der sich bereits auf Ihrem Stapel befindet. Dies zeigt die Existenz eines Zyklus an. Wenn Sie keine solche Kante finden, gibt es in dieser verbundenen Komponente keine Zyklen.

Wie Rutger Prins betont, müssen Sie die Suche für jede verbundene Komponente wiederholen, wenn Ihr Diagramm nicht verbunden ist.

Als Referenz ist Tarjans stark verbundener Komponentenalgorithmus eng verwandt. Es hilft Ihnen auch dabei, die Zyklen zu finden und nicht nur zu melden, ob sie vorhanden sind.

Jay Conrod
quelle
2
Übrigens: Eine Kante, die "auf einen Knoten zurückweist, der sich bereits auf Ihrem Stapel befindet", wird in der Literatur aus offensichtlichen Gründen häufig als "Hinterkante" bezeichnet. Und ja, dies ist möglicherweise einfacher als das topologische Sortieren des Diagramms, insbesondere wenn Sie ohnehin eine DFS durchführen müssen.
Sleske
Damit das Diagramm azyklisch ist, muss jede verbundene Komponente einen Knoten mit nur ausgehenden Kanten enthalten. Können Sie einen Algorithmus empfehlen, um die verbundenen Komponenten (im Gegensatz zu "stark" verbundenen Komponenten) eines gerichteten Graphen zur Verwendung durch Ihren Hauptalgorithmus zu finden?
Kostmo
@kostmo, wenn der Graph mehr als eine verbundene Komponente hat, werden Sie nicht alle Knoten in Ihrer ersten DFS besuchen. Behalten Sie die von Ihnen besuchten Knoten im Auge und wiederholen Sie den Algorithmus mit nicht besuchten Knoten, bis Sie alle erreichen. So funktioniert im Grunde ein Algorithmus für verbundene Komponenten.
Jay Conrod
6
Obwohl die Absicht dieser Antwort korrekt ist, ist die Antwort verwirrend, wenn eine stapelbasierte Implementierung von DFS verwendet wird: Der zur Implementierung von DFS verwendete Stapel enthält nicht die richtigen Elemente, gegen die getestet werden soll. Es ist erforderlich, dem Algorithmus einen zusätzlichen Stapel hinzuzufügen, um die Menge der Ahnenknoten zu verfolgen.
Theodore Murdock
Ich habe mehrere Fragen zu Ihrer Antwort. Ich habe sie hier gepostet: stackoverflow.com/questions/37582599/…
Ari
14

In Lemma 22.11 über das Buch Introduction to Algorithms(2. Auflage) heißt es:

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

Filipe Miguel Fonseca
quelle
1
Dies ist im Grunde nur eine Kurzfassung von Jay Conrods Antwort :-).
Sleske
Eines der Probleme aus demselben Buch scheint darauf hinzudeuten, dass es ein | V | gibt Zeitalgorithmus. Es wird hier beantwortet: stackoverflow.com/questions/526331/…
Justin
9

Lösung 1 : Kahn-Algorithmus zur Überprüfung des Zyklus . Hauptidee: Pflegen Sie eine Warteschlange, in der Knoten mit einem Grad von Null in die Warteschlange aufgenommen werden. Ziehen Sie dann den Knoten nacheinander ab, bis die Warteschlange leer ist. Überprüfen Sie, ob die In-Kanten eines Knotens vorhanden sind.

Lösung 2 : Tarjan-Algorithmus zur Überprüfung der stark verbundenen Komponente.

Lösung 3 : DFS . Verwenden Sie ein Integer-Array, um den aktuellen Status des Knotens zu kennzeichnen: dh 0 - bedeutet, dass dieser Knoten zuvor noch nicht besucht wurde. -1 - bedeutet, dass dieser Knoten besucht wurde und seine untergeordneten Knoten besucht werden. 1 - bedeutet, dass dieser Knoten besucht wurde und fertig ist. Wenn der Status eines Knotens während der DFS -1 ist, bedeutet dies, dass ein Zyklus vorhanden sein muss.

Chris Su
quelle
1

Die von ShuggyCoUk angegebene Lösung ist unvollständig, da möglicherweise nicht alle Knoten überprüft werden.


def isDAG(nodes V):
    while there is an unvisited node v in V:
        bool cycleFound = dfs(v)
        if cyclefound:
            return false
    return true

Dies hat die Zeitkomplexität O (n + m) oder O (n ^ 2)


quelle
meins ist in der Tat falsch - ich habe es jedoch gelöscht, so dass Ihr jetzt ein wenig aus dem Zusammenhang
gerät
3
O (n + m) <= O (n + n) = O (2n), O (2n)! = O (n ^ 2)
Artru
@Artru O (n ^ 2) bei Verwendung der Adjazenzmatrix, O (n + m) bei Verwendung der Adjazenzliste zur Darstellung des Graphen.
0x450
Ähm ... m = O(n^2)da das komplette Diagramm genau m=n^2Kanten hat. Das ist es also O(n+m) = O(n + n^2) = O(n^2).
Alex Reinking
1

Ich weiß, dass dies ein altes Thema ist, aber für zukünftige Suchende ist hier eine C # -Implementierung, die ich erstellt habe (kein Anspruch darauf, dass es am effizientesten ist!). Hierbei wird eine einfache Ganzzahl verwendet, um jeden Knoten zu identifizieren. Sie können das nach Belieben dekorieren, vorausgesetzt, Ihr Knotenobjekt hascht und ist gleich.

Bei sehr tiefen Graphen kann dies einen hohen Overhead verursachen, da an jedem Knoten in der Tiefe ein Hashset erstellt wird (diese werden über die Breite zerstört).

Sie geben den Knoten ein, von dem aus Sie suchen möchten, und geben den Pfad zu diesem Knoten an.

  • Für ein Diagramm mit einem einzelnen Stammknoten senden Sie diesen Knoten und ein leeres Hashset
  • Bei einem Diagramm mit mehreren Stammknoten wickeln Sie dies in einen Foreach über diese Knoten und übergeben für jede Iteration ein neues leeres Hashset
  • Wenn Sie nach Zyklen unterhalb eines bestimmten Knotens suchen, übergeben Sie diesen Knoten einfach zusammen mit einem leeren Hashset

    private bool FindCycle(int node, HashSet<int> path)
    {
    
        if (path.Contains(node))
            return true;
    
        var extendedPath = new HashSet<int>(path) {node};
    
        foreach (var child in GetChildren(node))
        {
            if (FindCycle(child, extendedPath))
                return true;
        }
    
        return false;
    }
    
Matthew
quelle
1

Während der DFS sollte keine Hinterkante vorhanden sein. Während der DFS verfolgen Sie bereits besuchte Knoten. Wenn Sie auf eine Kante zwischen dem aktuellen Knoten und dem vorhandenen Knoten stoßen, hat der Graph einen Zyklus.

Santhosh
quelle
1

Hier ist ein schneller Code, um festzustellen, ob ein Graph Zyklen hat:

func isCyclic(G : Dictionary<Int,Array<Int>>,root : Int , var visited : Array<Bool>,var breadCrumb : Array<Bool>)-> Bool
{

    if(breadCrumb[root] == true)
    {
        return true;
    }

    if(visited[root] == true)
    {
        return false;
    }

    visited[root] = true;

    breadCrumb[root] = true;

    if(G[root] != nil)
    {
        for child : Int in G[root]!
        {
            if(isCyclic(G,root : child,visited : visited,breadCrumb : breadCrumb))
            {
                return true;
            }
        }
    }

    breadCrumb[root] = false;
    return false;
}


let G = [0:[1,2,3],1:[4,5,6],2:[3,7,6],3:[5,7,8],5:[2]];

var visited = [false,false,false,false,false,false,false,false,false];
var breadCrumb = [false,false,false,false,false,false,false,false,false];




var isthereCycles = isCyclic(G,root : 0, visited : visited, breadCrumb : breadCrumb)

Die Idee ist wie folgt: Ein normaler dfs-Algorithmus mit einem Array zur Verfolgung der besuchten Knoten und ein zusätzliches Array, das als Markierung für die Knoten dient, die zum aktuellen Knoten geführt haben, sodass wir jedes Mal ein dfs für einen Knoten ausführen Wir setzen das entsprechende Element im Marker-Array auf true, sodass wir bei jedem Auftreten eines bereits besuchten Knotens prüfen, ob das entsprechende Element im Marker-Array true ist. Wenn es true ist, ist es einer der Knoten, die sich selbst zulassen (daher a Zyklus), und der Trick ist, wenn ein dfs eines Knotens zurückkehrt, setzen wir seinen entsprechenden Marker zurück auf false, damit wir uns nicht täuschen lassen, wenn wir ihn erneut von einer anderen Route aus besuchen.

m.eldehairy
quelle
0

Hier ist meine Ruby-Implementierung des Peel-Off-Leaf-Node-Algorithmus .

def detect_cycles(initial_graph, number_of_iterations=-1)
    # If we keep peeling off leaf nodes, one of two things will happen
    # A) We will eventually peel off all nodes: The graph is acyclic.
    # B) We will get to a point where there is no leaf, yet the graph is not empty: The graph is cyclic.
    graph = initial_graph
    iteration = 0
    loop do
        iteration += 1
        if number_of_iterations > 0 && iteration > number_of_iterations
            raise "prevented infinite loop"
        end

        if graph.nodes.empty?
            #puts "the graph is without cycles"
            return false
        end

        leaf_nodes = graph.nodes.select { |node| node.leaving_edges.empty? }

        if leaf_nodes.empty?
            #puts "the graph contain cycles"
            return true
        end

        nodes2 = graph.nodes.reject { |node| leaf_nodes.member?(node) }
        edges2 = graph.edges.reject { |edge| leaf_nodes.member?(edge.destination) }
        graph = Graph.new(nodes2, edges2)
    end
    raise "should not happen"
end
neoneye
quelle
0

Hatte gerade diese Frage in einem Google-Interview.

Topologische Sortierung

Sie können versuchen, topologisch zu sortieren. Dies ist O (V + E), wobei V die Anzahl der Eckpunkte und E die Anzahl der Kanten ist. Ein gerichteter Graph ist genau dann azyklisch, wenn dies möglich ist.

Rekursive Blattentfernung

Die entfernen rekursiv Blattknoten, bis keine mehr übrig sind. Wenn mehr als ein Knoten übrig ist, haben Sie einen Zyklus. Wenn ich mich nicht irre, ist dies O (V ^ 2 + VE).

DFS-Stil ~ O (n + m)

Ein effizienter DFS-ähnlicher Algorithmus, Worst-Case O (V + E), ist jedoch:

function isAcyclic (root) {
    const previous = new Set();

    function DFS (node) {
        previous.add(node);

        let isAcyclic = true;
        for (let child of children) {
            if (previous.has(node) || DFS(child)) {
                isAcyclic = false;
                break;
            }
        }

        previous.delete(node);

        return isAcyclic;
    }

    return DFS(root);
}
Tom Golden
quelle