如何使用堆来优化Prim的最小生成树算法？

Question

我必须解决一个类似这样的问题：
我给了一个数字N来表示我拥有的点数。每个点具有两个坐标：X和Y

我能找到用下列公式两个点之间的距离：
ABS（X2-X1）+ ABS（Y2-Y1），
（ x1，y1）为第一点的坐标，（x2，y2）为第二点的坐标，绝对值为abs()。

我必须找到最小生成树，这意味着我必须让所有的点与边的总和最小。 Prim的算法很好，但它太慢了。我读到，我可以使用heap使其更快，但我没有找到解释如何做到这一点的任何文章。

任何人都可以解释一下Prim的算法是如何处理堆的（一些示例代码会很好，但不是必须的），请问？

Answer 1

可以有效地解决这个问题（在O(n log n)时间），但并不那么容易。仅仅使用Prim算法和堆并不能帮助（它实际上使得它更慢），因为它的时间复杂度是O(E log V)，在这种情况下是O(n^2 * log n)。

但是，您可以使用Delaunay三角剖分来减少图形中的边数。 Delaunay三角剖分图是平面的，因此它具有线性数量的边缘。这就是为什么运行带有堆的Prim算法时间复杂性（有O(n)边和n顶点）。你可以在这里阅读更多关于它的信息（详细说明这个算法并证明它的正确性会让我的回答方式太长）：http://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree。请注意，尽管文章是关于欧几里得mst，但您的案例的方法基本相同（也可以有效地为曼哈顿距离构建Delaunay三角剖分）。

Prim的算法与堆本身的描述已经出现在你的问题的其他两个答案中。

Answer 2

从维基百科的文章上Prim's algorithm：

[S] toring顶点，而不是边缘可以进一步改善它。堆应该用最小的边权重来排序顶点，这个最小的边权重将它们连接到部分构建的最小生成树（MST）中的任何顶点（或者如果没有这样的边存在，则为无穷大）。每次选择顶点并将其添加到MST时，在部分MST外部的所有顶点和上执行减键操作，使得v连接到w，将键设置为其先前值的最小值和边缘成本（v，w）。