Come posso verificare se un grafico diretto è aciclico?

Question

Come si verifica se un grafico diretto è aciclico? E come viene chiamato l'algoritmo? Gradirei un riferimento.

Answer 1

Proverei a sort the graph topologically, e se non è possibile, allora ha cicli.

Answer 2

La soluzione fornita da ShuggyCoUk è incompleta perché potrebbe non controllare tutti i nodi.

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

Questo ha timecomplexity O (n + m) o O (n^2)

Answer 3

Facendo una semplice in profondità-ricerca è non abbastanza buono per trovare un ciclo. È possibile visitare un nodo più volte in un DFS senza un ciclo esistente. A seconda di dove inizi, potresti anche non visitare l'intero grafico.

È possibile verificare i cicli in un componente collegato di un grafico come segue. Trova un nodo che ha solo bordi in uscita. Se non esiste un tale nodo, allora c'è un ciclo. Avvia un DFS su quel nodo. Quando attraversi ciascun lato, controlla se il bordo punta a un nodo già presente nello stack. Questo indica l'esistenza di un ciclo. Se non trovi tale margine, non ci sono cicli in quel componente collegato.

Come Rutger Prins indica, se il grafico non è connesso, è necessario ripetere la ricerca su ciascun componente collegato.

Come riferimento, Tarjan's strongly connected component algorithm è strettamente correlato. Ti aiuterà anche a trovare i cicli, non solo a segnalare se esistono.

Answer 4

Lemma 22.11 sul Libro Introduction to Algorithms (Second Edition) afferma che:

un grafo orientato G è aciclico se e solo se una ricerca in profondità di G produce no Torna bordi

Answer 5

So che questo è un vecchio argomento, ma per i futuri ricercatori qui è una implementazione C# che ho creato (nessuna affermazione che sia più efficiente!). Questo è progettato per utilizzare un numero intero semplice per identificare ciascun nodo. Puoi decorare ciò che ti piace, a condizione che il tuo nodo abbia gli hash degli oggetti ed è uguale a quello giusto.

Per grafici molto profondi questo può avere un sovraccarico elevato, in quanto crea un hashset su ciascun nodo in profondità (vengono distrutti per larghezza).

Si immette il nodo da cui si desidera effettuare la ricerca e il percorso deve essere eseguito su quel nodo.

• Per un grafico con un singolo nodo radice si invia tale nodo e un hashset vuoto
• Per un grafico avente più nodi radice si avvolgono questo in un foreach su tali nodi e passare un nuovo hashset vuota per ciascuna iterazione

• controllando per cicli di sotto di qualsiasi dato nodo, basta passare quel nodo insieme a un hashset vuoto

  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

Ecco il mio rubino implemen zione dello 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

Soluzione1: Kahn algoritmo per controllare il ciclo. Idea principale: Mantieni una coda in cui il nodo con zero in-degree sarà aggiunto alla coda. Quindi rimuovere il nodo uno ad uno finché la coda non è vuota. Verifica se esistono in-edge di qualsiasi nodo.

Solution2: algoritmo Tarjan per verificare la forte componente collegato.

Soluzione3: DFS. Utilizzare l'array intero per taggare lo stato corrente del nodo: , ad esempio 0, significa che questo nodo non è stato visitato prima. -1 - significa che questo nodo è stato visitato e i suoi nodi figli vengono visitati. 1 - significa che questo nodo è stato visitato ed è fatto. Quindi se lo stato di un nodo è -1 durante l'esecuzione di DFS, significa che deve esserci un ciclo esistente.

Answer 8

Non ci dovrebbe essere alcun bordo posteriore mentre si fa DFS. Tenere traccia dei nodi già visitati mentre si fa DFS, se si incontra un margine tra nodo corrente e nodo esistente, allora il ciclo del grafico.

Answer 9

ecco un codice swift per trovare se un grafico ha cicli:

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'idea è simile a questo: un algoritmo di DFS normale con una matrice per tenere traccia dei nodi visitati, e una serie aggiuntiva che serve come marker per i nodi che hanno portato al nodo corrente, in modo tale che quando eseguiamo un dfs per un nodo impostiamo il suo elemento corrispondente nell'array marker come vero, in modo che quando mai un nodo già visitato venga rilevato controlliamo se il suo corrispondente l'elemento nell'array marker è vero, se è vero allora è uno dei nodi che lascia a se stesso (quindi un ciclo), e il trucco è ogni volta che viene restituito un dfs di un nodo impostiamo il corrispondente marker indietro a falso, così che se lo visitassimo di nuovo da un'altra rotta non ci prendiamo in giro.