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


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


75
2018-02-24 22:19


Ursprung


Antworten:


Ich würde es versuchen sortiere das Diagramm topologischund wenn du nicht kannst, dann hat es Zyklen.


83
2018-02-25 02:16



Eine einfache Tiefensuche zu machen ist nicht gut genug, um einen Zyklus zu finden. Es ist möglich, einen Knoten mehrmals in einem DFS zu besuchen, ohne dass ein Zyklus existiert. Je nachdem, wo Sie anfangen, werden Sie möglicherweise auch nicht den gesamten Graphen sehen.

Sie können Zyklen in einer verbundenen Komponente eines Graphen wie folgt prüfen. Suchen Sie einen Knoten, der nur ausgehende Kanten hat. Wenn es keinen solchen Knoten gibt, dann gibt es einen Zyklus. Starten Sie ein DFS an diesem Knoten. Überprüfen Sie beim Überqueren jeder Kante, ob die Kante auf einen Knoten verweist, der sich bereits auf Ihrem Stapel befindet. Dies zeigt die Existenz eines Zyklus an. Wenn Sie keine solche Kante finden, sind in dieser verbundenen Komponente keine Zyklen vorhanden.

Wenn Rutger Prins darauf hinweist, dass der Graph nicht verbunden ist, müssen Sie die Suche für jede verbundene Komponente wiederholen.

Als Referenz, Tarjans stark verbundener Komponentenalgorithmus ist eng verwandt. Es wird Ihnen auch helfen, die Zyklen zu finden und nicht nur zu melden, ob sie existieren.


32
2018-02-25 02:08



Lemma 22.11 über das Buch Introduction to Algorithms (Zweite Ausgabe) heißt es:

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


12
2018-05-30 10:45



Lösung1: Kahn-Algorithmus zur Überprüfung des Zyklus. Hauptidee: Pflegen Sie eine Warteschlange, in der Knoten mit null Grad in die Warteschlange hinzugefügt 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ösung2: Tarjan-Algorithmus Überprüfen Sie die starke verbundene Komponente.

Lösung3: DFS. Verwenden Sie das Ganzzahl-Array, um den aktuellen Status des Knotens zu kennzeichnen: d. h. 0 - bedeutet, dass dieser Knoten vorher nicht besucht wurde.      -1 - bedeutet, dass dieser Knoten besucht wurde und seine untergeordneten Knoten besucht werden.      1 - bedeutet, dass dieser Knoten besucht wurde, und es ist fertig. Wenn der Status eines Knotens also -1 ist, während er DFS ausführt, bedeutet dies, dass ein Zyklus existieren muss.


5
2017-09-19 19:49



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 Zeitkomplexität O (n + m) oder O (n ^ 2)


1
2018-02-25 01:29



Ich weiß, dass dies ein altes Thema ist, aber für zukünftige Suchende hier ist eine C # Implementierung, die ich erstellt habe (keine Behauptung, dass es am effizientesten ist!). Dies dient dazu, eine einfache Ganzzahl zum Identifizieren jedes Knotens zu verwenden. Sie können dekorieren, wie Sie möchten, vorausgesetzt, Ihr Node-Objekt hat Hashes und ist gleichwertig.

Für sehr tiefe Graphen kann dies einen hohen Overhead haben, da es bei jedem Knoten in der Tiefe ein Hash-Set erzeugt (sie werden über die Breite hinweg zerstört).

Sie geben den Knoten ein, von dem Sie suchen möchten, und den Pfad, der zu diesem Knoten führt.

  • Für ein Diagramm mit einem einzelnen Stammknoten senden Sie diesen Knoten und ein leeres Hashset
  • Bei einem Graphen mit mehreren Wurzelknoten wickeln Sie diesen in eine foreach über diese Knoten und übergeben ein neues leeres hashset für jede Iteration
  • Wenn Sie nach Zyklen unter einem bestimmten Knoten 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;
    }
    

1
2017-10-24 17:47



Während der Ausführung von DFS sollte keine Rückflanke vorhanden sein. Verfolgen Sie die bereits besuchten Knoten während der Ausführung von DFS. Wenn Sie auf eine Kante zwischen dem aktuellen Knoten und dem vorhandenen Knoten stoßen, hat das Diagramm einen Zyklus.


1
2017-10-28 05:14



Hier ist ein schneller Code um herauszufinden 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, um besuchte Knoten zu verfolgen, und ein zusätzliches Array, das als Markierung für die Knoten dient, die zum aktuellen Knoten führten, so dass wir immer einen dfs für einen Knoten ausführen Wir setzen das entsprechende Element im Marker-Array auf true, so dass wir, wenn ein bereits besuchter Knoten gefunden wird, prüfen, ob das entsprechende Element im Marker-Array wahr ist, ob es wahr ist und dann einer der Knoten, die sich selbst überlassen (daher ein Zyklus), und der Trick ist immer, wenn ein dfs eines Knotens zurückkehrt, setzen wir seinen entsprechenden Marker zurück auf false, so dass, wenn wir ihn von einer anderen Route wieder besuchen, wir nicht getäuscht werden.


1
2018-01-10 14:59



Hier ist meine Ruby - Implementierung der Blattknoten-Algorithmus abziehen.

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

0
2018-06-27 19:45