無向圖解決方案中最長路徑（邊權重= 1）？

Question

我有一個無向圖，每條邊的權重爲1.該圖可能有循環。我需要在圖中找到最長的路徑（每個節點出現一次）。路徑的長度是節點的數量。任何簡單/有效的解決方案謝謝！

Answer 1

根據http://en.wikipedia.org/wiki/Longest_path_problem，找到最長的路徑是NP-hard。所以除非P = NP被認爲是一個很難解決大案例的問題。與找到最短路徑相反，BFS算法是線性的。