我正在阅读用于查找最小生成树的算法（在加权图的情况下）以及查找图是否具有哈密顿路径（这取决于哈密顿循环的存在）。我把一切搞砸了。那么哈密顿路径和生成树之间的区别是什么？两者都覆盖图中的所有顶点。虽然我们可以使用有效的算法来查找生成树（可能是最小的生成树），但为什么我们不能找到哈密尔顿电路的算法？我们可以继续一次添加和删除一条边，直到我们达到一个周期，也许，我们可以找到一个哈密顿周期？
我正在阅读用于查找最小生成树的算法（在加权图的情况下）以及查找图是否具有哈密顿路径（这取决于哈密顿循环的存在）。我把一切搞砸了。那么哈密顿路径和生成树之间的区别是什么？两者都覆盖图中的所有顶点。虽然我们可以使用有效的算法来查找生成树（可能是最小的生成树），但为什么我们不能找到哈密尔顿电路的算法？我们可以继续一次添加和删除一条边，直到我们达到一个周期，也许，我们可以找到一个哈密顿周期？
这两个问题完全不同。将最小生成树视为连接您只需支付一次以构建道路的地方的问题，但您可以根据需要多次使用它。很容易想出最便宜的道路配置（例如通过Kruskal的算法），它允许您从任何地方旅行到任何其他地方。
另一方面，汉密尔顿循环要求您最小化实际行进距离，即从一个地方到另一个地方的每次移动都很重要。 （它还要求你永远不要两次访问一个地方，但这是一个小细节。）这个问题基本上是非本地的，从某种意义上说，你无法通过本地探索选项来判断你是否正在做正确的事情。下一步。相比之下，贪婪的MST算法保证选择正确的下一个边缘，以便在每一步添加到树中。
顺便说一句，没有人说“我们不能为HP提供有效的算法”。可能是我们还没有找到一个:-)
这两个问题完全不同。将最小生成树视为连接您只需支付一次以构建道路的地方的问题，但您可以根据需要多次使用它。很容易想出最便宜的道路配置（例如通过Kruskal的算法），它允许您从任何地方旅行到任何其他地方。
另一方面，汉密尔顿循环要求您最小化实际行进距离，即从一个地方到另一个地方的每次移动都很重要。 （它还要求你永远不要两次访问一个地方，但这是一个小细节。）这个问题基本上是非本地的，从某种意义上说，你无法通过本地探索选项来判断你是否正在做正确的事情。下一步。相比之下，贪婪的MST算法保证选择正确的下一个边缘，以便在每一步添加到树中。
顺便说一句，没有人说“我们不能为HP提供有效的算法”。可能是我们还没有找到一个:-)
这两个问题都希望将所有顶点相互连接起来。
对于最小生成树，您不关心哪个顶点是顶点 一个 是连接的，所以你可以连接 一个 到最近的顶点。 由于您只连接尚未连接的顶点，因此会提供一棵树，并且您拥有算法。
然而，对于哈密尔顿路径，你关心哪个顶点（比如说 b）你连接一个顶点 一个，因为你不能使用 b 再次（否则它不再是路径）。所以为了确定你应该连接什么顶点 一个，你必须尝试所有可能性，看看发生了什么。 也就是说，没有人找到一种有效的方法，当然这并不意味着没有。
哈密顿路径，特别是最小哈密顿循环对于解决旅行商问题即最短旅行是有用的。快速解决方案看起来像希尔伯特曲线，一种特殊的空间填充曲线也用于降低空间复杂度和有效寻址。 mst就像连接所有顶点一起以最便宜的成本连接（即旅行）无论顺序还是交叉。解决诸如寻找道路，寻找水渠，寻找互联网电缆等问题是非常有用的。
在哈密顿路径中，除源和接收器之外的所有顶点都具有2度。对于MST（或ST，如果你想要它）不一定是这种情况。