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

Question

给定图形无方向的g =（v，e）和一组节点。我需要找到一个包含这些节点的循环（不是最短的长度循环）？我如何找到这个周期？

Answer 1

包含汉密尔顿周期（对于p = V），因此决策问题（仅知道是否有这样的事情）是NP完整的。因此，除非p = np，否则没有有效的算法。

Answer 2

我可能会通过选择P中的第一个节点来开始设计算法（我们称其为p [0]），然后从P [0]中运行深度优先搜索，并再次达到任何时间P [0]。您必须存储重新启动P [0]所需的路径（或至少是否已经达到了P的其他节点），以便您知道您发现的任何周期都包含P。运行时间中的所有节点与深度优先搜索相同，我认为这是O（v + e）。

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

编辑：

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

进一步编辑：

不要介意最后的编辑 - 只有可以确定P [0]和P到达的节点之间的不同路径上的p中没有节点，并且无法通过其他方式到达，我们不会知道这一点，而无需完成整个DFS。

关于有关汉密尔顿周期的答案，我不知道手头问题中的周期检测是如何完成的。是的，我们必须从起点遍历整个图（所有顶点和边缘），以确定是否存在符合手动问题标准的周期。此外，我们需要知道，与先前访问的顶点接触后，顶点的“前进路径”是什么，以确定是否有一个符合标准的周期。但是，由于我们不在乎最短的周期，因此我不确定我们如何试图找到一个哈密顿周期。关心启发吗？