圖：包含節點的計數週期

我想計算非有向圖中節點所屬的週期數。圖：包含節點的計數週期

這些週期可以共享它們之間的節點。這兩個將計數：

A -> B -> A 
A -> B -> C -> A

我一直在嘗試我的手一段時間了。我目前的實施計數週期兩次：單向行走，然後是另一行程。它可能有其他的錯誤。

這是遞歸函數來找到路徑（從countCycles包裝）：

function countPaths(current, destination, visited: set) -> 
    if visited.contains(current): 
     if current is destination and visited.size > 2: 
      return 1 
     else 
      return 0 

    visited.add(current) 
    count = 0 

    for each neighbor of current: 
     count += countPaths(neighbor, destination) 

    visited.remove(current) 
    return count

如果唯一的問題是，週期計數兩次，我可以減半的結果，但我想走路每個只循環一次。相同的算法可能對其他方面有好處。

來源

2014-06-17 slezica

最後一段是一個真正的WTF。 –

如果是給我的話，我會花上一個小時。我的老闆不會那麼高興。 – slezica

我們不知道哪裏出了問題，向我們展示您當前的（非工作）解決方案。 –

這是一個含糊不清的問題。如果一個圖有循環，它可以有無數的路徑。

一般來說，所有可能的路徑問題都是NP困難的，即使對於小圖也可能有非常多的路徑。

一般策略是將廣度優先搜索與隊列或某種其他機制相結合，該機制僅存儲當前分支的訪問節點。

欲瞭解更多信息，請參閱all possible paths problem

來源

2014-06-17 18:14:52

僞代碼暗示他只考慮沒有重複節點的循環---一個簡單的循環。 – Billiska

對，這就是爲什麼我建議使用像隊列這樣的數據結構來記住當前分支上已訪問過哪些節點。 –

-1

這是我O(VE^2)算法，其中V是頂點的數目和E是邊數。這不是一個遞歸算法。

我將從1到V的頂點編號。其中1將始終是問題中必須出現在計數週期中的頂點。

草圖如下：我將計算所有頂點的較小子集內的循環，並逐漸考慮更多頂點。也就是說，從集{1,2,3}

啓動你需要的東西來維持：

m[x][y]大小V x V記住你是否已通過頂點1發現了一個簡單的路徑的布爾表有x 和y以及路徑的終點。通過簡單的路徑我的意思是路徑不重複頂點。
週期的計數這就是答案

讓我們開始算法。

(1) Initialize table `m` for the base case of set `{1,2,3}`. I'll assume you can do this. 
(2) For each time you add a vertex `A` into consideration, do the following: 

    (2.1) Update the cycle count 

      For every (B,C) pair of vertices that are both adjacent to vertex A 
      [Meaning we have a path (B,A,C)] 
      that the table m has an entry of path (B,...,1,...,C) 

      We can deduce that there is a simple cycle (A,B,...,1,...C,A). 
      count it. 

    (2.2) Update the table m 

      For every vertex X that is adjacent to A and there is a path (X,...,1,...,Y) 
      Remember that there is a path (A,...,1,...,Y) into table m.

算法描述完成。

複雜性分析：外環經過每個頂點，因此乘以因子V。步驟(2.1)經過與A相鄰的每一對邊，因此乘以因子E^2。整體O(VE^2)。

來源

2014-06-17 18:51:47 Billiska

那麼，爲什麼-1？我的回答錯誤或格式不正確？ – Billiska

我無法改進OP中的算法，因此它不會遍歷相同的週期兩次。所以，我給出了一個不同的算法，它不會遍歷同一個循環兩次。我不認爲這是脫離主題。 – Billiska

圖：包含節點的計數週期

回答

相關問題