couting back edges得到有向圖中的圓柱數

我一直在編寫代碼以獲得有向圖中所有可能的週期。 Here是一種實現方式，可以跟蹤後沿，並且每當找到一個後沿時，它就會返回檢測到一個週期的結果。我將其擴展到以下內容：計算樹中所有可能的後邊，後邊數應該給出循環數。不知道這是否正確。使用這個，我實現了以下內容：下面的count變量沒有用。最初，我已經給它每個週期的計數。但是這並沒有給出正確的答案。但存儲所有後邊的edgeMap的大小似乎在某些圖中給出正確的週期數，但不是全部。couting back edges得到有向圖中的圓柱數

該代碼適用於圖片中的G2和G3，但G1代碼失敗。（G1只有兩個週期，但我有三個後沿）。在那裏我可以會錯誤的任何建議，將有助於 enter image description here

public int allCyclesDirectedmain(){ 
     clearAll(); 
     int count=0; 
     Map<Vertex, Vertex> edgeMap = new HashMap<>(); 


     for (Vertex v : vertexMap.values()) { 
      if (!v.isVisited && allCyclesDirected(v,edgeMap)) 
       count++; 
     } 
     System.out.println(edgeMap); 
     return count; 

    } 
public boolean allCyclesDirected(Vertex v, Map<Vertex, Vertex> edgeMap){ 
     if (!v.isVisited){ 
      v.setVisited(true); 
      Iterator<Edge> e = v.adj.iterator(); 
      while (e.hasNext()){ 
        Vertex t = e.next().target; 
        if (!t.isVisited && allCyclesDirected(t,edgeMap)){ 
         edgeMap.put(v, t); 
          return true; 
        } 
        else 
          return true; 
        } 
       } 
     return false; 
    }

來源

2013-11-27 eagertoLearn

我想你已經在尋找一些已知解決方案的不平凡的問題。你看過以前的答案嗎？例如：http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph其中的一個答案提到了Java中用於計算循環的算法：http：//normalisiert.de/code/ java/elementaryCycles.zip –

@Ricardo：我看着它。這不是微不足道的，我同意。 Himadri Choudhury提供的鏈接上有一個帖子。這個解決方案看起來很優雅，但不清楚，我在那裏留下了一個便條，但沒有人回答。 –

backedges的數量不是週期數，因爲一個回邊可以參加一個以上的週期。

在你的圖G1中，讓我們追蹤深度優先搜索的進展：A：它訪問A-> B-> C，然後在D和E之間進行選擇。假設它需要D.然後它訪問E，並發現一個backedge轉到B.事情是，EB邊緣參與BCE循環和BCDE循環！

下面是另一個例子：考慮四個節點上的完整有向圖。有12個邊，但

6兩頂點週期
8三頂點週期
6四頂點週期

總共20個循環的 - 超過有圖中的邊緣！實際上，圖中可能存在指數週期數，並計算它們的問題，稱爲#CYCLE，is not computable in polynomial time if P != NP。

來源

2013-11-28 04:50:34

couting back edges得到有向圖中的圓柱數

回答

相關問題