尋找地鐵方案的環路

我有一個問題，我一直在想這個問題。尋找地鐵方案的環路

例如：

1-2 
3-4 
6-4 
2-3 
1-3 
3-5

注：「A-B」的意思是 'A' 連接到 'B' 和 'b' 連接到 'A'

我如何才能找到一個最長的環形路;
它是1-2-3從例子中導致1-2,1-3,2-3。

我在想回合使用蠻力，但是，這並不似乎工作原因無法計算高達3000組合

我在想可能更快的算法，但似乎沒有得到很好的主意

2011-11-25 zeulb

你的蠻力法是什麼？ –

哈哈！比賽仍在繼續。如果您現在無法解決問題，請等待社論。 –

3000組合應該不成問題。我懷疑，如果你只有6個頂點，蠻力就是要走的路。 –

從理論的角度來看，很難有一個有效的算法。

如果您有發現最長的循環，而不在同一個邊緣去兩次的算法，你能解決Halmitonian路徑問題http://en.wikipedia.org/wiki/Hamiltonian_path

所以，你必須取消NP完全算法。所以有一個多項式算法很少機會。

真的暴力是3000站的問題嗎？我會在每個節點上做一個bfs，每次你點擊離開節點時，我會把它存儲爲最長的環。

2011-11-25 16:27:40

不是真的，因爲他沒有約束他必須訪問每個節點。 –

問題非常嚴重。只有一個循環。 –

沒問題，就像你在帖子中說的那樣讓事情變得更容易 –

問題說只有一條環道。所以，你看到的任何圖形都是如圖所示的形式。問題還表明，您可以從一個頂點到另一個頂點，也就是說，圖形已連接。

 _ _ _ _ 
    _ _ _/  \ 
     |   |_ _ _ 
     \_ _ _ _/

所以，如果你從任何頂點應用DFS，那麼你將在環道中。你可以做一個散列，並在你訪問它們時不斷標記它們。當你再次訪問同一個頂點時，你在環行路上。

編輯：正如@Saeed指出的那樣，在O（n）中可以很容易找到頂點距鐵路的距離。你可以繞着環形道行駛，移動到更新距離的邊緣，然後繼續在環道上行駛。

我會建議你等待教程。

2011-11-25 16:48:42

沒有必要從任何不在環形道路上的vertext啓動BFS，首先可以從環形路徑頂點移除連接，然後從環形道路的任何頂點開始，找到相關的頂點及其距離，即O（n）。（因爲剩下的圖是叢林）。 –

你有一個「叢林」條款的裁判？注意，刪除環路頂點後剩餘的圖形是[森林]（http://en.wikipedia.org/wiki/Tree_%28graph_theory%29）。任何具有n個邊和n個頂點的連通無向圖是環和森林的聯合。 –

@ jwpat7我對叢林說你說森林，這是因爲它接近我們的波斯語，我猜每個人都可以猜到我在說什麼，我是你想要的參考:) –

回答