¿Cómo puedo verificar si un gráfico dirigido es acíclico?

Question

¿Cómo puedo verificar si un gráfico dirigido es acíclico? ¿Y cómo se llama el algoritmo? Agradecería una referencia.

Answer 1

Me gustaría intentar sort the graph topologically, y si no puede, entonces tiene ciclos.

Answer 2

La solución dada por ShuggyCoUk es incompleta porque podría no verificar todos los nodos.

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

Esto tiene timecomplexity O (n + m) u O (n^2)

Answer 3

haciendo una simple profundidad de primera búsqueda se no lo suficientemente bueno para encontrar un ciclo. Es posible visitar un nodo varias veces en un DFS sin un ciclo existente. Dependiendo de dónde empiece, es posible que no visite todo el gráfico.

Puede verificar los ciclos en un componente conectado de un gráfico de la siguiente manera. Encuentra un nodo que solo tenga bordes salientes. Si no hay tal nodo, entonces hay un ciclo. Comience un DFS en ese nodo. Al atravesar cada borde, compruebe si el borde apunta a un nodo que ya está en su pila. Esto indica la existencia de un ciclo. Si no encuentra ese borde, no hay ciclos en ese componente conectado.

Como señala Rutger Prins, si su gráfico no está conectado, necesita repetir la búsqueda en cada componente conectado.

Como referencia, Tarjan's strongly connected component algorithm está estrechamente relacionado. También lo ayudará a encontrar los ciclos, no solo a informar si existen.

Answer 4

Lemma 22.11 en el libro Introduction to Algorithms (Segunda Edición) establece que:

un grafo dirigido G es acíclico si y sólo si una búsqueda en profundidad de G no da la espalda bordes

Answer 5

Sé que este es un tema antiguo, pero para los buscadores del futuro aquí hay una implementación de C# que he creado (¡ningún reclamo de que sea más eficiente!). Esto está diseñado para usar un número entero simple para identificar cada nodo. Puedes decorar eso como desees siempre que los hashes de objetos de tu nodo sean iguales.

Para gráficos muy profundos esto puede tener una sobrecarga elevada, ya que crea un hashset en cada nodo en profundidad (se destruyen a lo ancho).

Ingrese el nodo desde el que desea buscar y la ruta de acceso a ese nodo.

• Para un gráfico con un único nodo raíz que envíe ese nodo y un hashset vacío
• Para un gráfico que tiene múltiples nodos raíz que envuelven esta en un foreach sobre esos nodos y aprobar una nueva hashset vacío para cada iteración

• Cuando la comprobación de ciclos por debajo de cualquier nodo dado, sólo tiene que pasar a lo largo de ese nodo con un hashset vacío

  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

Aquí es mi rubí implemen tación del 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

Solución 1: algoritmo de Kahn para verificar ciclo. Idea principal: mantener una cola donde el nodo con grado cero se agregará a la cola. A continuación, despegue el nodo uno por uno hasta que la cola esté vacía. Verifique si los bordes internos de cualquier nodo existen.

Solución 2: algoritmo Tarjan para verificar componente conectado Strong.

Solución3: DFS. Utilice la matriz de enteros para etiquetar el estado actual del nodo: , es decir, 0 - significa que este nodo no se ha visitado anteriormente. -1 - significa que se ha visitado este nodo y se están visitando sus nodos secundarios. 1 - significa que este nodo ha sido visitado y listo. Entonces, si el estado de un nodo es -1 mientras se realiza el DFS, significa que debe existir un ciclo.

Answer 8

No debe haber ningún borde posterior mientras se hace DFS. Mantenga la pista de los nodos ya visitados mientras hace DFS, si encuentra un borde entre el nodo actual y el nodo existente, entonces el gráfico tiene ciclo.

Answer 9

aquí es un código rápida de encontrar si un gráfico tiene ciclos:

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) 

La idea es la siguiente: un algoritmo DFS normal con una matriz para realizar un seguimiento de los nodos visitados, y una serie adicional que sirve como un marcador para los nodos que conducen al nodo actual, de modo que cada vez que ejecutemos un dfs para un nodo, establecemos su elemento correspondiente en el conjunto de marcadores como verdadero, de modo que cuando se encuentre un nodo ya visitado, verifiquemos si su correspondiente el elemento en la matriz de marcadores es verdadero, si es verdadero, entonces es uno de los nodos que se permite a sí mismo (por lo tanto, un ciclo), y el truco es cada vez que devuelve un dfs de un nodo, establecemos su marcador correspondiente a falso, por lo que si lo visitamos nuevamente desde otra ruta no nos engañen.