我想知道是否有任何有效的算法可以找到图中最长循环的长度?
该图是一个无向图。
该算法不必告诉循环中的顶点是什么,只需告诉长度即可。
最佳答案
寻找图中最长循环的问题是NP-hard,因为解决这个问题可以回答“这个图是哈密尔顿图吗?”(是否它具有哈密尔顿循环),这本身就是一个 NP 完全问题。
所以,确实,没有高效的算法可以做到这一点。
有一些基于矩阵乘法的方法可以在图中找到长度为 k
的循环。
您可以在 this quesion 中找到有关使用矩阵乘法查找循环的说明。 .但请注意,矩阵乘法方法允许检测 2 个顶点之间给定长度的 walks
,并且允许在 walk 中重复顶点。
关于algorithm - 是否有任何有效的算法可以找到无向图中最长循环的长度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55625479/