找到圖的最大長度

我需要你的幫助來解決問題。這是編碼練習的一部分，我無法完全解決。找到圖的最大長度

假設我們有如下圖：

enter image description here

我需要建立一個計算路徑的最大長度的類。我沒有根，不得不用每個頂點作爲起點。該方法有一個最大重複次數的參數，所以如果這個1，我們可以通過每個邊一次，如果它是2，我們可以通過一個每條邊最多2次。

在這種情況下，如果重複= 1，最大路徑應該是（B，A，C）。它重複= 2，那麼最大路徑應該是（B，A，B，A，C，C）。

爲了不重複地解決問題，我想構建一個鄰接表並運行DFS來查找圖中的所有路徑並提取最大值。我認爲這應該適用於更簡單的情況。

但我不知道該怎麼辦，當我們可以重複邊緣。我可以用什麼樣的算法來解決這個問題。你也可以想到一個更有效的方法來解決這個問題嗎？

感謝

來源

2013-05-29 rmorais

當然，如果每一個邊緣可以訪問一次（大概每一個節點都可以造訪的任何數量的），你應該得到BABCC？ BAC甚至不是你繪製的圖形的有效路徑。 – Sysyphus

可以使用深度優先搜索的修改版本。

在這種情況下，你作爲訪問但一些衛星數據添加到他們不僅標誌着一個節點：次訪問，當它到達repeats您將它們標記爲訪問。

從維基百科的修改後的僞代碼：

procedure DFS(G,v): 
    increment v.timesVisited 
    for all edges e in G.adjacentEdges(v) do 
     if edge e.timesVisited < repeats then 
      w ← G.adjacentVertex(v,e) 
      if vertex w.timesVisited < repeats then 
       e.timesVisited++ 
       recursively call DFS(G,w) 
      else 
       label e as a back edge

我希望它的作品我沒有測試的修改。

來源

2013-05-29 08:58:29

我認爲您需要重置一個節點在其子樹中旅行完成後的訪問次數。 –

我確實實現了這個版本，它按預期工作。感謝大家的幫助 – rmorais

如果我理解正確，解決方案是類似的兩種情況。

對於沒有重複的解決方案：您將每個節點作爲根，並在其子節點上啓動DFS。節點的有效子節點是尚未訪問過的節點。

對於N重複問題：有效的孩子是一個被訪問少於N次的節點。在DFS中的每次訪問中，都需要更新該節點的訪問計數器。另外，當您完成探索特定節點的子節點時，您需要將其訪問計數器歸零。

來源

2013-05-29 09:00:54

我可以看到一個天真的方法。它不是效率，但它的工作原理。

兩個元素：

一個HashMap與每個邊緣設置爲0
的條目使用DFS抓取的曲線圖（增量和減量的散列映射知道你的擷取）

作爲你沒有root權限，我想你必須爲每個節點執行此操作。

您是否需要找到所有解決方案或者您是否在尋找即將解決的解決方案？

你不能找到在維基百科有關這類問題的更多的解釋： http://en.wikipedia.org/wiki/Longest_path_problem

來源

2013-05-29 09:03:01 FArcellier

找到圖的最大長度

回答

相關問題