给定一个无向图 G = (V,E) 和一组节点 P。我需要找到一个包含这些节点的环(不是最短长度的环)？如何找到这个周期？
最佳答案
我可能会通过选择 P 中的第一个节点(我们称之为 P[0])开始设计算法，然后从 P[0] 运行深度优先搜索，并记下 P[0] 再次出现的任何时间到达。您必须存储重新到达 P[0] 所采取的路径(或者至少是否已到达 P 的其他节点)，以便您知道找到的任何循环都包含 P 中的所有节点。运行时间应该是与深度优先搜索相同，我认为是 O(V + E)。
有人可能会提出更好的解决方案，并且可能会应用某些启发式方法来提供帮助，但这应该可以帮助您开始。 (例如，您可能会得出结论，您应该从 P 中边数最少的节点开始，而不是从 P[0] 开始。)
编辑:
我想到的另一件事...当您通过深度优先搜索到达 P 中的另一个节点时，DFS 不需要从头开始“重新开始”或考虑不存在的路径包括这个新发现的节点。在不存在此类循环的情况下，此属性可以帮助您的算法更快地终止。
进一步编辑:
不要介意最后一次编辑——只有当可以确定 P[0] 和 P 中到达的节点之间的不同路径上不存在无法通过其他方式到达的节点时，它才会起作用，并且我们如果不进行整个 DFS，就无法确定这一点。
关于哈密顿循环的答案，我不知道当前问题中的循环检测如何是NP完全的。是的，我们必须遍历从起点可达的整个图(所有顶点和边)，以确定是否存在满足当前问题标准的循环。此外，我们需要知道在与先前访问过的顶点接触时该顶点的“前向路径”是什么，以确定是否存在满足标准的循环。不过，由于我们不关心最短的这样的循环，所以我不确定我们如何必然地试图找到哈密顿循环。愿意赐教吗？
关于algorithm - 如何找到图中包含一组节点的环？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3908371/