Jak wykryć, czy ukierunkowany wykres jest cykliczny?

Question

Jak możemy wykryć, czy ukierunkowany wykres jest cykliczny? Myślałem, że najpierw skorzystam z szerokości, ale nie jestem pewien. Jakieś pomysły?

Answer 1

Zwykle używane jest wyszukiwanie z dokładnością do początku. Nie wiem, czy BFS można łatwo zastosować.

W DFS, drzewo opinające jest budowane w kolejności odwiedzin. Jeśli przodek węzła w drzewie jest odwiedzany (tzn. Tworzony jest back-edge), wówczas wykrywamy cykl.

Aby uzyskać bardziej szczegółowe wyjaśnienie, patrz: http://www.cs.nyu.edu/courses/summer04/G22.1170-001/6a-Graphs-More.pdf.

Answer 2

Innym prostym rozwiązaniem byłoby podejście "mark-and-sweep". Zasadniczo dla każdego węzła w drzewie oznaczamy go jako "odwiedzany", a następnie przechodzimy do jego dzieci. Jeśli kiedykolwiek zobaczysz węzeł z ustawionym flagą "visted", wiesz, że istnieje cykl.

Jeśli modyfikowanie wykresu w celu włączenia "odwiedzonego" bitu nie jest możliwe, można użyć zestawu wskaźników węzła. Aby oznaczyć węzeł jako odwiedzany, umieszczasz w nim wskaźnik. Jeśli wskaźnik jest już w zestawie, istnieje cykl.

Answer 3

Co naprawdę trzeba, moim zdaniem, jest to algorytm sortowania topologiczna jak ten opisany tutaj:

http://en.wikipedia.org/wiki/Topological_sorting

Jeśli graf skierowany ma cykl następnie algorytm zakończy się niepowodzeniem.

W komentarzach/odpowiedziach, które dotychczas widziałem, brakuje informacji o tym, że na wykresie skierowanym może istnieć więcej niż jeden sposób przejścia z węzła X do węzła Y bez żadnego (skierowanego) cykle na wykresie.

Answer 4

Podejście: 1 o poziomie bez przydziału do wykrycia cyklu. np .: rozważ poniższy wykres. A -> (B, C) B-> D D -> (E, F) E, F -> (G) E-> D Podczas wykonywania DFS start przypisanie poziomu no do odwiedzanego węzła (root A = 0). poziom no węzła = nadrzędny + 1. Zatem A = 0, B = 1, D = 2, F = 3, G = 4, rekurencja osiąga D, więc E = 3. Nie oznaczaj poziomu dla G (G już nie ma przypisanego poziomu, który jest większy niż E) Teraz E również ma przewagę do D. Tak więc levelizacja oznaczałaby, że D powinien uzyskać poziom no 4. Ale D ma już przypisany "niższy poziom" aby to od 2. Tak więc za każdym razem próbując przypisać numer poziomu do węzła robiąc DFS, który już wiele niższy poziom ustawiony na nim wiesz skierowany graf ma cykl ..

approach2:
użyj 3 kolorów. biały, szary, czarny. kolor tylko białe węzły, białe węzły szarzeją, jak przejść DFS, kolor szary węzłów do czarnego, gdy rekurencja rozwija (wszystkie dzieci są przetwarzane). jeśli nie wszystkie dzieci są jeszcze przetworzone i uderzysz w szary węzeł, który jest cyklem. np .: wszystkie białe, aby rozpocząć w powyżej bezpośredniego wykresu. kolory A, B, D, F, G mają kolor biało-szary. G to liść, więc wszystkie dzieci przetwarzają kolor od szarego do czarnego. rekursja rozwija się do F (wszystkie dzieci przetwarzane) kolor czarny to. teraz osiągasz D, D ma nieprzetworzonych dzieci, więc kolor E szary, G już kolorowy czarny, więc nie idź dalej w dół. E ma również krawędź do D, więc podczas przetwarzania D (D nadal szary), znajdujesz krawędź z powrotem do D (szary węzeł), wykrywany jest cykl.

Answer 5

Testowanie topologicznej rodzaju na danym wykresie doprowadzi Cię do roztworu. Jeśli algorytm topsortu, tzn. Krawędzie zawsze powinny być skierowane w jedną stronę, nie udaje się, oznacza to, że wykres zawiera cykle.

Answer 6

Zastosowanie DFS szukać jeśli ścieżka jest cykliczny

class Node<T> { T value; List<Node<T>> adjacent; } 

class Graph<T>{ 

    List<Node<T>> nodes; 

    public boolean isCyclicRec() 
    { 

     for (Node<T> node : nodes) 
     { 
      Set<Node<T>> initPath = new HashSet<>(); 
      if (isCyclicRec(node, initPath)) 
      { 
       return true; 
      } 
     } 
     return false; 
    } 

    private boolean isCyclicRec(Node<T> currNode, Set<Node<T>> path) 
    { 
     if (path.contains(currNode)) 
     { 
     return true; 
     } 
     else 
     { 
     path.add(currNode); 
     for (Node<T> node : currNode.adjacent) 
     { 
      if (isCyclicRec(node, path)) 
      { 
       return true; 
      } 
      else 
      { 
       path.remove(node); 
      } 
     } 
     } 
     return false; 
    }