c++ - 无向图中的最长循环

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-hard。

这意味着除非 P=NP，否则没有任何解决方案从根本上优于回溯。