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

给定一个图无向G =（V，E）和一组节点P.我需要找到一个包含这些节点的周期（不是最短长度周期）？我如何找到这个循环？如何在图中找到包含一组节点的循环？

来源

2010-10-11 Bruce

你有任何条件在所需的周期？ – Frank 2010-10-11 17:11:30

循环中没有条件 – Bruce 2010-10-11 17:14:12

您是否在寻找欧拉循环？ – mattbasta 2010-10-11 17:27:38

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

来源

2010-10-11 18:46:08 piccolbo

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

有人可能会想出更好的解决方案，并且某些启发式技术可能会用于帮助，但这应该让您开始。（例如，你可以得出结论，你应该在P的节点与边缘，而不是为P开始[0]最少的开始。）

编辑：我认为

一件事...当通过深度优先搜索到达P中的另一个节点时，不需要从头开始“重新开始”，或者考虑不包含这个新找到的节点的路径。在没有这种循环的情况下，该属性可以帮助您更快地终止算法。

进一步编辑：

没关系最后一次编辑 - 它只会工作，如果它能够确定有属于P P [0]和P中的节点之间的不同路径上没有节点达不到另一种方式无法达到的程度，而且我们不知道如果没有整个DFS的话。

关于哈密尔顿周期的答案，我不知道在手边的问题中的周期检测是如何完成的。是的，我们必须遍历从起始点到达的整个图（所有顶点和边），以确定是否存在符合问题标准的周期。此外，我们需要知道在与先前访问的顶点接触时，顶点的“前进路径”将确定是否存在满足标准的循环。因为我们不关心最短的这种循环，但我不确定我们是如何找到哈密尔顿循环的。照顾开导？

来源

2010-10-11 17:17:52 Andrew

哈密顿循环遍历所有节点，因此不会更短或更长。让我一步一步来。考虑这个问题的特殊情况（如果特例是NP-hard，一般情况也是NP-hard）：图G =（V，E）和节点集P = V（这就是它的特殊之处案件）。现在，通过所有节点V的最短和最长周期同样长，| V |。问题变得只是发现是否存在这样的事情，而这正是哈密尔顿周期，它是NP完全的。所以我只是发现HC在这个问题的“内部”。问题不在于HC，而是包含它。说得通？ – piccolbo 2010-10-14 17:59:05

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

回答

相关问题