Comment vérifier si un graphe orienté est acyclique?

Question

Comment vérifier si un graphe orienté est acyclique? Et comment s'appelle l'algorithme? J'apprécierais une référence.

Answer 1

Je voudrais essayer de sort the graph topologically, et si vous ne pouvez pas, alors il a des cycles.

Answer 2

La solution donnée par ShuggyCoUk est incomplète, car il pourrait ne pas vérifier tous les nœuds.

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

Cela a timecomplexity O (n + m) ou O (n^2)

Answer 3

Faire simple profondeur la première recherche est pas assez bon pour trouver un cycle. Il est possible de visiter un nœud plusieurs fois dans un DFS sans qu'un cycle existe. Selon l'endroit où vous commencez, vous pourriez également ne pas visiter le graphique entier.

Vous pouvez vérifier les cycles d'un composant connecté d'un graphique comme suit. Trouver un nœud qui n'a que des bords sortants. S'il n'y a pas de noeud, il y a un cycle. Démarrer un DFS sur ce noeud. Lorsque vous traversez chaque arête, vérifiez si le bord pointe vers un noeud déjà présent sur votre pile. Cela indique l'existence d'un cycle. Si vous ne trouvez pas un tel bord, il n'y a pas de cycles dans ce composant connecté.

Comme Rutger Prins souligne, si votre graphique est pas connecté, vous devez répéter la recherche sur chaque composant connecté.

En tant que référence, Tarjan's strongly connected component algorithm est étroitement liée. Il vous aidera également à trouver les cycles, et pas seulement signaler s'ils existent.

Answer 4

Lemme 22.11 sur le livre Introduction to Algorithms (deuxième édition) stipule que:

Un graphe orienté G est acyclique si et seulement si une recherche en profondeur d'abord de G donne des bords sans retour

Answer 5

Je sais que c'est un vieux sujet mais pour les futurs chercheurs, voici une implémentation en C# que j'ai créée (pas de prétention que c'est le plus efficace!). Ceci est conçu pour utiliser un entier simple pour identifier chaque noeud. Vous pouvez décorer ce que vous voulez, à condition que votre objet de noeud hashes et égalise correctement.

Pour les graphiques très profonds cela peut avoir des frais généraux élevés, car il crée un HashSet à chaque noeud en profondeur (ils sont détruits sur la largeur).

entrée Vous le noeud à partir duquel vous souhaitez rechercher et le chemin à prendre ce nœud.

• Pour un graphique avec un seul nœud racine vous envoyer ce noeud et un HashSet
• vide Pour un graphique ayant plusieurs nœuds racine vous enveloppent cela dans un foreach sur ces noeuds et passer une nouvelle HashSet vide pour chaque itération

• Lors de la vérification des cycles ci-dessous un nœud donné, il suffit de passer ce nœud avec un HashSet vide

  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 6

Voici mon œuvre rubis tion du peel off leaf node algorithm.

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 7

Solution1: algorithme Kahn pour vérifier le cycle. Idée principale: Maintenir une file d'attente où le noeud avec zéro au degré sera ajouté dans la file d'attente. Décollez ensuite le nœud un par un jusqu'à ce que la file d'attente soit vide. Vérifiez si les in-edges d'un nœud existent.

Solution2: Tarjan algorithme pour vérifier Composant connecté fort.

Solution3: DFS. Utilisez un tableau d'entiers pour marquer l'état actuel du noeud: , c'est-à-dire 0 - signifie que ce noeud n'a pas été visité auparavant. -1 - signifie que ce nœud a été visité et que ses nœuds enfants sont visités. 1 - signifie que ce noeud a été visité, et c'est fait. Donc, si l'état d'un nœud est de -1 alors que DFS est en cours, cela signifie qu'il doit exister un cycle.

Answer 8

Il ne devrait pas y avoir de bord arrière pendant que vous faites DFS. Gardez la trace des nœuds déjà visités en faisant DFS, si vous rencontrez une arête entre le nœud actuel et le nœud existant, alors le graphique a un cycle.

Answer 9

est ici un code rapide pour trouver si un graphe a des cycles:

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) 

L'idée est comme ceci: un algorithme de DSF normale avec un tableau pour garder une trace des noeuds visités, et un tableau supplémentaire qui sert comme un marqueur pour les nœuds qui ont conduit au nœud actuel, de sorte que lorsque nous exécutons un dfs pour un nœud, nous définissons son élément correspondant dans le tableau des marqueurs comme vrai, de sorte que chaque fois qu'un nœud déjà visité rencontré, nous vérifions item dans le tableau des marqueurs est vrai, si c'est vrai alors c'est l'un des nœuds qui se laisse à (d'où un cycle), et l'astuce c'est quand un dfs d'un nœud retourne on met son marqueur correspondant à faux, de sorte que si nous l'avons visité d'une autre route, nous ne sommes pas dupes.