用於循環檢測的代碼未找到在Java中的有向圖中返回正確的循環次數？

我使用DFS編寫了用於計算有向圖中週期數的代碼。檢查循環是否存在的方法工作正常。我現在迭代所有頂點（我在HashMap中），並檢查頂點是否未訪問，然後檢查循環是否存在，如果是這樣，則遞增計數器1.現在代碼中斷，它不會給出正確的數字例如：對於具有以下邊緣的圖：用於循環檢測的代碼未找到在Java中的有向圖中返回正確的循環次數？

(A B),(B C),(C E),(E A),(B E)

這是我的代碼;

public int getTotalCyclesinDir(){ 
    clearAll(); 
    int count=0; 
    for (Vertex v : vertexMap.values()) { 
     if (!v.isVisited && isCyclicDirected(v)) 
      count++; 
    } 
    return count; 
} 

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

來源

2013-11-26 brain storm

您希望得到哪個數字？算法返回什麼？ –

我期望2，因爲有兩個週期，但它只返回一個 –

另外，我看到在我的'isCyclicDirected'方法中有太多的return語句。有沒有簡化它的方法？ –

至少有兩個問題你的算法：

isCyclicDirected只是檢測是否有圖中的任何週期。你不能直接使用它來計算週期。例如，您的算法將計算（A B）（B A）（C A）中的兩個週期，因爲（C A）連接到訪問節點。
如果你想在你的例子中檢測兩個週期，你的檢測需要基於邊緣而不是基於頂點。（B E）形成一個循環，但B和E都被標記爲前一次運行的訪問。

來源

2013-11-26 22:27:46

我明白了你的觀點。 1）你是什麼意思的邊緣爲基礎，你可以詳細說一點2）在'isCyclicDirected'方法中，我有太多的回報，是所有必要或任何簡化空間..謝謝 –

假設有一條河，你想計數橋樑。你從橋的一邊開始，並將岸標記爲已訪問。然後你穿過橋並將另一側標記爲已訪問。然後你得出結論，只有一座橋，因爲你已經訪問過雙方。 –

我對代碼進行了更改，實現方式不同以跟蹤邊緣。仍然有一些問題，我在這裏發佈..http：//stackoverflow.com/questions/20253255/couting-back-edges-to-get-the-number-of-cylces-in-a-directed-graph –

用於循環檢測的代碼未找到在Java中的有向圖中返回正確的循環次數？

回答

相關問題