如何檢測有向圖是循環的？

Question

我們如何檢測有向圖是循環的？我想過使用廣度優先搜索，但我不確定。有任何想法嗎？

Answer 1

通常使用深度優先搜索來代替。 我不知道BFS是否適用。

在DFS中，根據訪問順序構建生成樹。如果樹中的一個節點的祖先被訪問（即創建了一個後沿），那麼我們檢測到一個循環。

有關更詳細的解釋，請參閱http://www.cs.nyu.edu/courses/summer04/G22.1170-001/6a-Graphs-More.pdf。

Answer 2

另一個簡單的解決方案是標記和掃描方法。基本上，對於樹中的每個節點，將其標記爲「已訪問」，然後轉到其子節點。如果你看到一個設置了「visted」標誌的節點，你就知道有一個循環。

如果修改圖形以包含「訪問」位是不可能的，則可以使用一組節點指針。要將節點標記爲已訪問，請在該集​​中放置一個指向它的指針。如果指針已經在集合中，就有一個循環。

Answer 3

你真正需要的是什麼，我相信，在這裏所描述的一樣一個一個拓撲排序算法：

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

如果有向圖有一個週期，則算法將失敗。

的意見/回答說，我到目前爲止看到似乎缺少一個事實，即在定向圖可能有不止一種方法從節點X獲得，而不存在以節點Y的任何（導演）圖中的週期。

Answer 4

方法：1
如何檢測一個週期級別沒有分配。例如：考慮下面的圖表。 （B，C）B-> D D - >（E，F）E，F - >（G）E-> D當您執行DFS開始時，爲您訪問的節點分配一個級別no = 0）。級別no =父節點+ 1。所以A = 0，B = 1，D = 2，F = 3，G = 4，則遞歸達到D，所以E = 3。不要標記G的等級（G已經是一個沒有被分配的等級比E更高的等級）現在E也具有對D的邊緣。因此，等級化將會說D應該得到4的等級no。但是D已經具有分配的「較低等級」到它2.因此，任何時候你試圖級別數分配到一個節點，而這樣做已經有設置爲它一個較低的水平數DFS，你知道有向圖有一個週期..

approach2：
使用3種顏色。白色，灰色，黑色。只有白色節點纔會着色，當您沿DFS走向時，白色節點變爲灰色，當遞歸展開時（處理所有子節點），將灰色節點變爲黑色。如果不是所有的孩子都處理完畢，並且你打了一個灰色節點，那就是一個循環。 例如：全部白色以直接上圖開始。顏色A，B，D，F，G顏色爲白色灰色。 G是葉子，所以所有的孩子都把它染成灰色變成黑色。遞歸到F（所有處理過的孩子）將它染成黑色。現在你到達D，D有未加工的孩子，所以顏色E灰色，G已經着黑色，所以不要進一步下去。 E也有邊緣到D，所以在仍然處理D（D仍然是灰色）的時候，你會發現一個邊緣回到D（一個灰色節點），就會檢測到一個週期。

Answer 5

對給定圖形的拓撲排序測試將引導您找到解決方案。如果topsort的算法，即邊緣總是以一種方式定向失敗，那麼這意味着圖形包含循環。

Answer 6

使用DFS搜索如有路徑循環

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; 
    } 

的