是否有任何有效的算法可以找到无向图中最长循环的长度？
Is there any efficient algorithm to find the length of the longest cycle in a undirected graph?
我想知道有没有什么高效的算法可以求图中最长环的长度？
该图是无向图。
算法不必告诉循环中的顶点是什么，只需要知道长度。
寻找图中最长循环的问题是 NP-hard，因为解决这个问题可以回答“这个图是哈密尔顿图吗？ ”（它是否具有哈密尔顿循环），这本身就是一个 NP 完全问题。
所以，确实，没有有效的算法可以做到这一点。
有一些基于矩阵乘法的方法可以在图中找到长度为 k 的循环。
您可以在 this quesion 中找到有关使用矩阵乘法查找循环的说明。但请注意，矩阵乘法方法允许检测 2 个顶点之间给定长度的 walks，并且允许重复顶点。
我想知道有没有什么高效的算法可以求图中最长环的长度？
该图是无向图。
算法不必告诉循环中的顶点是什么，只需要知道长度。
寻找图中最长循环的问题是 NP-hard，因为解决这个问题可以回答“这个图是哈密尔顿图吗？ ”（它是否具有哈密尔顿循环），这本身就是一个 NP 完全问题。
所以，确实，没有有效的算法可以做到这一点。
有一些基于矩阵乘法的方法可以在图中找到长度为 k 的循环。
您可以在 this quesion 中找到有关使用矩阵乘法查找循环的说明。但请注意，矩阵乘法方法允许检测 2 个顶点之间给定长度的 walks，并且允许重复顶点。