Jak sprawdzić, czy skierowany wykres jest acykliczny?

Question

Jak sprawdzić, czy skierowany wykres jest acykliczny? A jak nazywa się ten algorytm? Byłbym wdzięczny za odniesienie.

Answer 1

Chciałbym spróbować sort the graph topologically, a jeśli nie, to ma cykle.

Answer 2

Rozwiązanie podane przez ShuggyCoUk jest niekompletne, ponieważ może nie sprawdzić wszystkich węzłów.

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

Ma timecomplexity O (N + M) lub O (N^2)

Answer 3

wykonanie prostego głębokość pierwszej wyszukiwania jest nie wystarczająco dobre, aby znaleźć cyklu. Możliwe jest wielokrotne odwiedzanie węzła w systemie plików DFS bez istniejącego cyklu. W zależności od tego, od czego zaczynasz, możesz również nie odwiedzać całego wykresu.

Można sprawdzić cykle w podłączonym komponencie wykresu w następujący sposób. Znajdź węzeł, który ma tylko wychodzące krawędzie. Jeśli nie ma takiego węzła, to jest cykl. Uruchom system DFS w tym węźle. Podczas przechodzenia przez każdą krawędź sprawdź, czy krawędź wskazuje na węzeł znajdujący się już na stosie. Wskazuje to na istnienie cyklu. Jeśli nie znajdziesz takiej krawędzi, w podłączonym komponencie nie ma cykli.

Jak zauważa Protein Rutger, jeśli wykres nie jest podłączony, należy powtórzyć wyszukiwanie na każdym podłączonym komponencie.

Jako odniesienie, Tarjan's strongly connected component algorithm jest blisko spokrewniona. Pomoże Ci również znaleźć cykle, a nie tylko zgłosić, czy istnieją.

Answer 4

Lemat 22.11 na książce Introduction to Algorithms (Second Edition) stwierdza, że:

graf skierowany G jest acykliczny wtedy i tylko wtedy, gdy przeszukiwanie w głąb G daje brak tylnych krawędziach

Answer 5

Wiem, że jest to stary temat, ale dla przyszłych poszukiwaczy jest stworzona przeze mnie implementacja C# (nie twierdzę, że jest najbardziej wydajna!). Jest zaprojektowany do używania prostej liczby całkowitej do identyfikacji każdego węzła. Możesz udekorować to, co lubisz, pod warunkiem, że twoje obiekty węzłów są odpowiednio wartościowane i równe.

W przypadku bardzo głębokich wykresów może to mieć duży narzut, ponieważ tworzy hasz w każdym węźle dogłębnym (są one niszczone na całej szerokości).

Wprowadzasz węzeł, z którego chcesz szukać, a ścieżka do tego węzła.

• Na wykresie z pojedynczego węzła głównego wysłaniu tego węzła i pusty hashset
• Dla wykresu mającej wiele węzłów korzeniowych owinąć to w foreach nad tymi węzłami i przekazać nowy pusty hashset dla każdej iteracji

• Podczas sprawdzania cykli poniżej danym węźle, po prostu przekazać ten węzeł wraz z pustym 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 6

Oto mój rubin reali tacji 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

Porada1: algorytm Kahn, by sprawdzić cykl. Główna idea: Utrzymanie kolejki, w której węzeł o zerowym stopniu dokładności zostanie dodany do kolejki. Następnie odklejaj węzeł jeden po drugim, aż kolejka będzie pusta. Sprawdź, czy istnieją wewnętrzne krawędzie węzła.

Solution2: Algorytm Tarjana do sprawdzenia Silnie połączony komponent.

Rozwiązanie3: DFS. Użyj tablicy liczb całkowitych, aby oznaczyć aktualny status węzła: , tj. 0 - oznacza, że ​​ten węzeł nie był wcześniej odwiedzany. -1 - oznacza, że ​​ten węzeł został odwiedzony, a jego węzły podrzędne są odwiedzane. 1 - oznacza, że ​​ten węzeł został odwiedzony i zakończył działanie. Więc jeśli status węzła wynosi -1 podczas wykonywania DFS, oznacza to, że musi istnieć cykl.

Answer 8

Nie powinno być żadnej tylnej krawędzi podczas wykonywania ścieżki DFS.Keep już odwiedzonych węzłów podczas wykonywania DFS, jeśli wystąpi krawędź między bieżącym węzłem a istniejącym węzłem, wówczas wykres ma cykl.

Answer 9

tutaj jest SWIFT CODE znaleźć jeśli wykres ma cykle:

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) 

Pomysł jest tak: normalny DFS Algorytm z tablicą do śledzenia odwiedzanych węzłów oraz dodatkową tablicę, która służy jako znacznik dla węzłów, które doprowadziły do ​​bieżącego węzła, tak, że gdy kiedykolwiek wykonamy dfs dla węzła, ustawiamy jego odpowiedni element w tablicy znaczników jako true, tak że gdy kiedykolwiek napotkany już węzeł napotka, sprawdzamy, czy odpowiadający mu węzeł pozycja w tablicy znaczników ma wartość true, jeśli jest prawdziwa, to jest to jeden z węzłów, które dałyby sobie (stąd cykl), a sztuczka jest taka, że ​​gdy dfs węzła powraca, ustawiamy odpowiedni znacznik z powrotem do fałszywego, więc jeśli odwiedzimy go ponownie z innej trasy, nie damy się oszukać.