这两个问题有很大的不同。把最小生成树看作是连接地点的问题，您只需要支付一次建造道路的费用，但可以无限次使用它。通过 Kruskal 算法等方式，很容易得出允许您从任何地方到达任何其他地方的最便宜的道路配置。
另一方面，Hamiltonian Cycle 旨在最小化实际旅行距离，即每次移动都算入其中。（它还要求您不要重复访问某个地方，但这只是一个细节问题。）这个问题在本质上是非局部的，也就是说，您不能仅通过局部探索下一步的选项来确定您正在做正确的事情。相比之下，贪心的最小生成树算法保证在每一步选择要添加到树中的正确下一条边。
顺便说一句，“我们不能为 HP 找到有效的算法”是没有人说过的。可能只是我们还没有找到而已 :-)