哈密顿路径与ST的区别
我正在阅读用于查找最小生成树（在加权图的情况下）和查找图是否具有哈密尔顿路径（这取决于哈密尔顿循环的存在）的算法。我把一切都搞乱了。那么哈密顿路径和生成树有什么区别呢？两者都覆盖了图中的所有顶点。虽然我们可以有有效的算法来找到生成树（也许是最小生成树），但为什么我们不能有算法来找到哈密顿电路？我们可以继续一次添加和删除一条边，直到达到一个循环，也许我们可以找到一个哈密顿循环？
I was reading up algorithms for finding the minimum spanning tree(in case of weighted graphs) and for finding if a graph has a hamiltonian path(which depends on the presence of a hamiltonian cycle). I got everything messed up. So whats the difference between a hamiltonian path and a spanning tree? Both cover all the vertices in the graph. While we can have efficient algorithms to find a spanning tree(perhaps a minimum spanning tree), why cant we have algorithms for finding a hamiltonian circuit?? We can keep on adding and removing one edge at a time till we reach a cycle and perhaps, we could find a hamiltonian cycle??
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
这两个问题都希望将所有顶点相互连接。
对于最小生成树，您不关心顶点a连接到哪个顶点，因此您可以将a连接到最近的顶点。
由于您只连接尚未连接的顶点，因此这给出了一棵树，并且您有了自己的算法。
然而，对于哈密尔顿路径，您确实关心连接顶点 a 的哪个顶点（例如 b），因为您不能再次使用 b （否则就不再是路径了）。因此，为了确定应该连接到哪个顶点，您必须尝试所有可能性并看看会发生什么。
也就是说，还没有人找到一种有效的方法，当然这并不意味着不存在。
Both problems want to connect all vertices to each other.
For a minimum spanning tree you don't care to which vertex a vertex a is connected, so you can just connect a to the closest vertex.
Since you only connect vertices that are not connected yet, this gives a tree, and you have your algorithm.
For a hamiltonian path however, you do care to which vertex (say b) you connect a vertex a, as you cannot use b again (otherwise it's no path anymore). So in order to determine to what vertex you should connect a, you have to try all possibilities and see what happends.
That is, no one has found an efficient way yet, that of course does not automatically means there is none.
在哈密顿路径中，除源点和汇点之外的所有顶点的度数均为 2。MST（或 ST，如果您需要的话）不一定是这种情况。
In hamiltonian path, all vertices except source and sink have a degree of 2. That is not necessarily the case with MST (or ST, if you want it).
哈密顿路径，尤其是最小哈密顿循环对于解决旅行推销员问题（即最短行程）很有用。快速解决方案看起来像希尔伯特曲线，一种特殊的空间填充曲线，也用于降低空间复杂度和有效寻址。 MST 就像以最便宜的连接成本（即行程）将所有顶点连接在一起，无论顺序或交叉如何。它对于解决诸如寻找道路、寻找水渠、寻找互联网电缆等问题很有用。
A hamiltonian path and especially a minimum hamiltonian cycle is useful to solve a travel-salesman-problem i.e. a shortest trip. A fast solution is looking like a hilbert curve a special kind of a space-filling-curve also uses to reduce the space complexity and for efficient addressing. A mst is like connecting all vertices together with cheapest cost to connect (i.e. travel) no matter of the order or crossing. It's useful to solve a problem like finding roads, finding water-canal, finding internet-cable.
生成树和哈密顿路径都跨越图中的所有顶点。生成树可能是也可能不是从
s到t的路径。图片上的生成树不是路径。正如上面有人提到的，有一些后果，例如，在路径中，所有度数都是 1 或 2。在上面的树中，您可能会看到一些度数为 3 的顶点。
如果您感兴趣，为什么没有已知的多项式时间算法
HAMPATH我推荐 Tim Roughgarden 的 书，第 4 部分。他称之为“MST 与 TSP：算法之谜”。标准答案是
HAMPATH是一个 NP 完全问题。这并不意味着没有多重时间算法，但这是最现实的场景。针对此类问题的已知算法在某些情况下可能相当合理，只是不是多项式。Both Spanning Tree and Hamiltonian path spans all the vertices in a Graph. A Spanning Tree may or may not be a path from
stot. The Spanning Tree on the picture is not a path.As someone mentioned above there are some consequences, for example, in a path all degrees are 1 or 2. In the tree above you may see some vertices with degree 3.
If you are interested why there are no known polynomial time algorithm for
HAMPATHI'd recommend Tim Roughgarden's book, Part 4. He calls it "MST vs. TSP: An Algorithmic Mystery".The standard answer is that
HAMPATHis an NP-complete problem. This doesn't mean there're no poly-time algorithms, but it's the most realistic scenario. Algorithms that are known for these type of problems can be quite reasonable for some instances, just not polynomial.哈密顿路径是生成树（只有2个叶子的特殊生成树），但生成树（可以有2个以上的叶子）可能不是哈密顿环。由于定义的差异，您可能会看到它们的一些不同用途。
Hamiltonian path is a spanning tree (a special spanning tree with only 2 leave), but a spanning tree (which can have more than 2 leaves) may not be a hamiltonian cycle. With the definition differencess, you may see some different use of them.
这两个问题是完全不同的。将最小生成树视为连接地点的问题，您只需支付一次修建道路的费用，但可以根据需要多次使用它。很容易想出最便宜的道路配置（例如通过克鲁斯卡尔算法），使您可以从任何地方旅行到任何其他地方。
另一方面，哈密顿循环希望您最小化实际行驶距离，即从一个地方到另一个地方的每次移动都很重要。 （它还要求你永远不要访问一个地方两次，但这是一个小细节。）这个问题从根本上来说是非本地的，从某种意义上说，你无法仅通过本地探索该地点的选项来判断你是否在做正确的事情。下一步。相比之下，贪婪 MST 算法保证在每一步都会选择正确的下一条边添加到树中。
顺便说一句，没有人说“我们不能为惠普提供高效的算法”。可能我们只是还没有找到一个:-)
The two problems are quite different. Think of the minimum spanning tree as the problem of connecting places where you only have to pay once to build the road, but you can use it as many times as you like. It's easy to come up with the cheapest configuration of roads (e.g. by Kruskal's algorithm) that allows you to travel from any place to any other.
The Hamiltonian cycle, on the other hand, wants you to minimize the actual travel distance, i.e. every move from one place to another counts. (It also asks you never to visit a place twice, but that's a minor detail.) This problem is fundamentally non-local, in the sense that you cannot tell whether you're doing the right thing just by locally exploring the options for the next step. By comparison, the greedy MST algorithm is guaranteed to pick the right next edge to add to the tree at every step.
By the way, nobody says that "we cannot have efficient algorithms for HP". It might be that we just haven't found one yet :-)