無向圖中最長的週期

Question

我如何得到無向圖中最長的週期（沒有後向跟蹤，需要太長的時間）。

實施例：

0 3 0 1 0 
3 0 0 1 0 
0 0 0 0 0 
1 1 0 0 0 
0 0 0 0 0 

解決：3 + 3 + 1 =>輸出：1 - 2 - 3 - 1。

Answer 1

如果能找到最長的週期，則可以檢測是否該圖有一個哈密爾頓週期，這是一個NP完全問題，因此使你的問題NP難。

這意味着沒有解決方案將基本上比回溯更好，除非P = NP。