prime

zjhdyn

大佬们，求教最小生成树的prime算法

oos1111

其实和dijstra最短路径算法是差不多的。
dijstra最短路径算法就是从起点开始，每次寻找一个离已经访问过的所有点中距离最近的一个，我们称新访问到的点为V_。
然后由于点V_也被访问到了，我们可能又有一些新的点可以访问到（和点V_直接相邻）。所以此时未访问点中的最近点可能发生改变。
就此一直循环这个过程，直到终点被访问到。
为了能时刻维护当前未访问的点中距离最近，并且在每次有新的点能够被访问时刷新，需要用到优先队列。这样刷新时复杂度是O(lgV)，获取最近点的复杂是O(1)。
由于循环中每个点都是此时能访问到的最近距离，因此最后的终点也一定是最近距离。这可以通过数学归纳法很容易证明。

现在来说Prime算法。Prime算法其实就是，在任意起点，但不存在终点，一直到所有点都被访问到的情况下，把dijstra最短路径算法跑一遍。
证明略困难，这里就不展开了。最后的边之和就是最终结果。