algorithm - 如何在图中找到包含一组节点的循环？

Question

给定一个无向图 G = (V,E) 和一组节点 P。我需要找到一个包含这些节点的循环（不是最短长度循环）吗？我如何找到这个循环？

Answer 1

我可能会通过选择 P 中的第一个节点（我们称之为 P[0]）开始设计算法，然后从 P[0] 运行深度优先搜索，并记下任何时候再次到达 P[0]。您必须存储重新到达 P[0] 所采用的路径（或者至少是否已到达 P 的其他节点），以便您知道您找到的任何循环都包含 P 中的所有节点。运行时间应该是与深度优先搜索相同，我认为是 O(V + E)。

有人可能会提出更好的解决方案，并且可能会应用某些启发式方法来提供帮助，但这应该可以帮助您入门。（例如，您可能会得出结论，您应该从 P 的具有最少边的节点开始，而不是从 P[0] 开始。）

编辑：

我想到的另一件事...当您通过深度优先搜索到达 P 中的另一个节点时，DFS 无需从一开始就“重新开始”或考虑不包括新的路径-找到的节点。在不存在此类循环的情况下，此属性可以帮助您的算法更快地终止。

进一步编辑：

没关系最后一次编辑 - 只有当可以确定 P [0] 和 P 中到达的节点之间的不同路径上没有节点 P 中没有节点无法通过其他方式到达时，它才会起作用，我们不会在不做整个 DFS 的情况下肯定知道这一点。

关于哈密顿循环的答案，我不知道手头问题中的循环检测如何是 NP 完全的。是的，我们必须遍历从起点可到达的整个图（所有顶点和边），以确定是否存在满足手头问题标准的循环。此外，我们需要在与先前访问过的顶点接触时知道该顶点的“前向路径”是什么，以确定是否存在满足标准的循环。但是，由于我们不关心最短的这样的循环，我不确定我们如何必然地试图找到一个哈密顿循环。关心开导？

Answer 2

包含哈密顿循环（对于 P = V），因此决策问题（只知道是否存在这样的事情）是 NP 完全的。因此，除非 P = NP，否则没有有效的算法。