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

Question

Wie kann ich überprüfen, ob ein gerichteter Graph azyklisch ist? Und wie wird der Algorithmus genannt? Ich würde eine Referenz zu schätzen wissen.

Answer 1

Ich würde versuchen, href="https://stackoverflow.com/questions/4168/graph-serialization/4577#4577"> sortieren Sie die Grafik topologisch

Answer 2

Doing eine einfache depth-first-Suche ist nicht gut genug, um einen Zyklus zu finden. Es ist möglich, vorhandene ein Knoten mehrfach in einer DFS ohne Zyklus zu besuchen. Je nachdem, wo Sie beginnen, könnten Sie auch das Diagramm nicht besuchen.

Sie können in einer angeschlossenen Komponente eines Graphen für Zyklen wie folgt überprüfen. Finden Sie einen Knoten, der nur ausgehende Kanten hat. Wenn es keinen solchen Knoten ist, dann gibt es einen Zyklus. Starten Sie eine DFS an diesem Knoten. Wenn jede Kante durchlaufen, überprüfen, ob die Kante bereits auf dem Stapel zu einem Knoten zurückweist. Dies zeigt die Existenz eines Zyklus. Wenn Sie keine solche Kanten zu finden, gibt es keine Zyklen in dieser verbundenen Komponente.

Wie Rutger Prins weist darauf hin, wenn Ihr Diagramm nicht angeschlossen ist, müssen Sie die Suche auf jeder verbundenen Komponente wiederholen.

Als Referenz Tarjan der stark Komponente Algorithmus verbunden eng verwandt ist . Es wird Ihnen auch helfen, die Zyklen zu finden, nicht nur berichten, ob sie existieren.

Answer 3

Lemma 22.11 auf dem Buch Introduction to Algorithms (Second Edition) heißt es:

  

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

Answer 4

Solution1 : Kahn Algorithmus überprüfen Zyklus . Grundidee: eine Warteschlange beizubehalten, in dem Knoten, der mit Null-Grad-in-Warteschlange hinzugefügt werden. abzuschälen dann Knoten nacheinander bis Warteschlange leer ist. Prüfen, ob Knotens in Kanten vorhanden sind.

Solution2 . Tarjan Algorithmus Starke verbundene Komponente überprüfen

Solution3 : DFS . Verwenden Integer-Array aktuellen Zustand des Knotens zu markieren: das heißt 0 --means hat dieser Knoten nicht vor besucht.      -1 - bedeutet dieser Knoten besucht wurde, und seine Kinder Knoten besucht werden.      1 - bedeutet dieser Knoten besucht wurde, und es ist getan. Also, wenn der Status des Knotens wird -1 während DFS tun, bedeutet dies, dass ein Zyklus existiert sein muss.

Answer 5

Die Lösung von ShuggyCoUk gegeben ist unvollständig, da sie möglicherweise nicht alle Knoten überprüfen.

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

Answer 6

Ich weiß, dies ist ein altes Thema, aber für künftige Forscher hier ist eine C # -Implementierung ich erstellt (keinen Anspruch, dass es am effizientesten!). Dies ist für eine einfache ganze Zahl zu verwenden, die jeden Knoten zu identifizieren. Sie können dekorieren, dass aber Sie Ihr Knotenobjekt Hashes bereitgestellt mögen und gleich richtig.

Sehr tiefe Graphen kann dies hohe Overhead, da sie einen Hashset an jedem Knoten in der Tiefe erzeugt (sie über Breite zerstört werden).

Sie Eingang der Knoten, von dem Sie zu diesem Knoten suchen und den Weg nehmen wollen.

• Für eine grafische Darstellung mit einem einzigen Wurzelknoten Sie, dass der Knoten und eine leere Hashset senden
• Für eine grafische Darstellung mehr Stammknoten Sie diese über den Knoten in einer foreach wickeln und eine neue leere Hashset für jede Iteration passieren

• Wenn für Zyklen unter einem bestimmten Knoten überprüft, so dass der Knoten passiert 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;
  }
  

Answer 7

Es sollte keine Hinterkante, während DFS.Keep Spur von bereits besuchten Knoten tun, während DFS tun, wenn Sie eine Kante zwischen dem aktuellen Knoten und vorhandenen Knoten auftreten, dann Graph Zyklus hat.

Answer 8

Hier ist ein SWIFT-Code zu finden, wenn ein Graph Zyklus 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 einer Reihe Spur von besuchten Knoten zu halten, und eine zusätzliche Anordnung, die für den Knoten als Marker dient, die auf die aktuellen Knoten geführt, so dass, wann immer wir eine dfs ausführen für einen Knoten setzten wir seinen entsprechenden Eintrag in der Markeranordnung als wahr, so dass, wenn überhaupt ein bereits besuchten Knoten wir überprüfen, ob sein entsprechendes Element in der Markeranordnung wahr angetroffen, das wenn sie wahr ist, dann sein eines des Knoten, die ihnen lassen (Daher ein Zyklus), und der Trick ist, wenn ein dfs eines Knotens kehrt ich seine entsprechende Markierung zurückwerfen auf false, so dass, wenn wir sie besuchten wieder von einer anderen Route, die wir getäuscht werden nicht.

Answer 9

Hier ist meine Ruby-Implementierung des abschälen Blatt Knoten-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

Answer 10

Gerade hatte diese Frage in einem Google-Interview.

topologische Sortierung

Sie können versuchen, sortieren topologisch, die O (V + E), wobei V die Anzahl der Ecken ist, und E ist die Anzahl der Kanten. Ein gerichteter Graph ist azyklisch, wenn und nur wenn dies getan werden kann.

rekursive Blatt Entfernen

Der entfernen rekursiv Blattknoten, bis keine mehr übrig sind, und wenn es mehr als ein einziger Knoten verlassen Sie einen Zyklus haben. Es sei denn, ich irre, ist dies O (V ^ 2 + VE).

DFS-style ~ O (n + m)

Allerdings ist ein effizienter DFS-esque Algorithmus, worst case O (V + E), ist:

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);
}