graph - 我可以在无向图中遍历每个节点恰好一次的最大节点数是多少？

Question

所以我有一个无向无权图。它包含循环。我想找到访问最多节点而不重复访问任何节点的路径。由于这是一个图遍历，你可以在任何你喜欢的节点开始和结束。

背景研究： 我看过旅行商问题（TSP）；这个问题是不同的，不允许你从你开始的地方完成并且没有重量。我查看了其他几种算法，但没有发现适合这个问题的算法。

Graph Size：图中有100个节点；有 10 个断开连接的节点。

score 1 · Accepted Answer

1

Look for the Hamiltonian Cycle problem

于 2012-11-23T22:07:50.383 回答

score 0 · Accepted Answer

您应该查看具有非循环图算法的维基百科条目。您的图表有循环，这使您的问题 NP-hard。

我会尝试创建一个 DAG，其中的节点代表强连接的组件。然后你至少可以找到访问最强连接组件的路径。然后，您可以通过用每个子图中最长的路径替换单个（强连接组件）节点来扩展该路径。

在子图中找到最长的路径现在与您的原始问题相同，但至少您的图更小。如果你幸运的话，子问题很容易并且你完成了。在一般情况下，它们可能不会那么小，您可以使用一些高级启发式方法。也许看看这篇论文或这个问题（你可以使用那里的答案来完全解决你的问题，但我不确定）

2 回答 2