普林姆算法

April 15, 2018

普林姆算法也是用来求最小生成树的，与克鲁斯卡尔算法遍历边不同，普林姆遍历的是点。

普林姆算法同样基于贪心，以任意点为初始点，每次选取与已选点相连的边中权值最小的边，并把与这条边相连的点加入已选点集合。

算法实现 #

1. 维护一个数组 minEdge[i]

含义为已选点集合中到第i个点 最小权值的边的终点，没有边则为无穷大。

2. 每次选minEdge中最小的点加入已选点集合，并更新minEdge数组。
3. 重复操作，直到所有点加入已选点集合。

优化 #

1. 使用优先队列维护minEdge

每往已选点集合加入点时，就把与该点相连的所有边都加入优先队列。而当取边时，需要判断一下边的终点是否在已选点集合中（可以使用一个标记数组）。

时间复杂度分析 #

1. 非优先队列法

• 在minEdge中找最小的时间复杂度为O(n)。
• 更新数组时间复杂度总和为O(e) —— 每个点都会更新与它相连的边，所有边加起来为e。
• 一共要进行n次在minEdge中找最小的操作。

故总的时间复杂度为O(n^2+e)。

2. 优先队列法

优先队列加边出边的时间复杂度都是O(loge)。

• 所有边都会进入优先队列至少一次，至多两次。时间复杂度为O(eloge)。
• 出边次数最少为n次，最多为e次，时间复杂度也是O(eloge)。

故总的时间复杂度为O(eloge)。

分析： 当边数达到cn^2或以上时，用非优先队列法要好，反之可以使用优先队列法。

当e = n^2 , O(eloge) = O(n^2logn) , O(n^2+e) = O(n^2) 。