我如何在无向图中获得最长的循环(没有回溯，它需要很长时间)。
例子:
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。
最佳答案
如果你能找到最长的环，你就可以检测到图是否有哈密顿环，这是一个 NP 完全问题，从而使你的问题成为 NP-hard。
这意味着除非 P=NP，否则没有任何解决方案从根本上优于回溯。
关于c++ - 无向图中的最长循环，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/35650783/