在一個特殊的有向圖中找到權重> 0的所有周期

Question

我正在尋找一種算法來查找所有周期的總重量大於零的所有邊。我聽說這個問題是NP完全的，但因爲我想解決這個問題，總是看起來差不多一樣，所以我希望有一個更簡單的方法。

My圖表看起來是這樣的：

它始終是所有horizo​​nzally和垂直相鄰頂點之間的N * N的頂點和邊的sqaure。只有兩種可能的權重，黑邊-1和綠色+1。

在這個例子中我正在尋找的週期將是：

---

• 7; 12; 17; 18; 19; 14; 13; 8; 7 =>體重：+1
• 7; 12; 13; 8; 7 =>體重：+1
• 7; 8; 7 =>體重：+2
• 18; 23; 24; 19; 18 =>體重：+1
• 7; 12; 17; 18; 23; 24; 19; 14; 13; 8; 7重：=> +2

---

什麼是承擔這一任務的高效算法？它應該是非常快的，因爲我也想爲n = 25 => 625個頂點的圖做到這一點。

感謝您的幫助！

Answer 1

爲什麼不使用帶有DFS一個基本週期檢測，而一些修改，以使其：

• 當你遇到一個節點，如果你已經訪問這個相同的節點，你知道你的是循環，以便檢查重量是否爲正數，如果是這樣，只需再次循環以將路徑保留在內存中。
• 如果你正在訪問的節點已經被看到就在這裏停下來。
• 然後遞歸訪問該節點的鄰居。

的僞代碼可能是這樣的：

dfs(node, weight): 
    if state[node] is "in progress" AND weight > 0 
     // This is a cycle we want 
     Keep in memory the path (just go throught the cycle once more) 
    if state[node] is "visited" 
     Stop 

    state[node] = "in progress" 
    For each neighbour 
     dfs(neighbour, weight + edge_weight) 
    state[node] = "visited" 

如果你這樣做，對於各開始節點，你應該在大約O（N * M）時得到一個複雜與數N頂點的數量和M的邊數量。

希望這會有所幫助！

編輯：忘了更新狀態