如何找到图中包含一组节点的环？
给定一个无向图 G = (V,E) 和一组节点 P。我需要找到一个包含这些节点的环（不是最短长度的环）？如何找到这个周期？
Given a graph undirected G = (V,E) and a set of nodes P. I need to find a cycle (not the shortest length cycle) containing these nodes? How do I find this cycle?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（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，我们就无法确定这一点。
关于哈密顿循环的答案，我不知道当前问题中的循环检测如何是NP完全的。是的，我们必须遍历从起点可达的整个图（所有顶点和边），以确定是否存在满足当前问题标准的循环。此外，我们需要知道在与先前访问过的顶点接触时该顶点的“前向路径”是什么，以确定是否存在满足标准的循环。不过，由于我们不关心最短的这样的循环，所以我不确定我们如何必然地试图找到哈密顿循环。介意赐教吗？
I would probably start designing the algorithm by choosing the first node in P (let's call it P[0]), then running a depth-first search from P[0], taking note of anytime P[0] is again reached. You would have to store the path taken to re-reach P[0] (or at least whether the other nodes of P have been reached) so that you know that any cycle you find contains all the nodes in P. Running time should be the same as for depth-first search, which I believe is O(V + E).
Someone may come up with a better solution, and certain heuristics might be applied to help, but that should get you started. (For instance, you may conclude you should start at the node of P with the fewest edges instead of starting at P[0].)
Edit:
One more thing I thought of... When you reach another node in P via your depth-first search, there is no need for the DFS ever to "start over" from the very beginning or to consider paths that do not include this newly-found node. This property could help your algorithm terminate more quickly in the case where no such cycle exists.
Further edit:
Never mind the last edit -- it would only work if it can be ascertained that there is no node in P on a different path between P[0] and the node in P reached that cannot be reached another way, and we wouldn't know that for sure without doing the whole DFS.
Regarding the answer about Hamiltonian cycles, I don't know how the cycle detection in the problem at hand is NP-complete. Yes, we would have to traverse the entire graph (all vertices and edges) reachable from the start point to determine whether a cycle meeting the criteria of the problem at hand exists. Further, we would need to know upon coming in contact with a previously-visited vertex what the "forward path" of the vertex would be to determine whether there is a cycle meeting the criteria. Since we don't care about the shortest such cycle, though, I'm not sure how we are necessarily trying to find a Hamiltonian cycle. Care to enlighten?
包含哈密顿环（对于 P = V），因此决策问题（只需知道是否存在这样的事情）是 NP 完全的。所以除非P = NP，否则不存在有效的算法。
Contains Hamiltonian Cycle (for P = V), hence the decision problem (just knowing if there is such a thing) is NP-complete. So there is no efficient algorithm unless P = NP.