在考研中，图的应用所包含的一个重要部分被称为最小生成树，其中教材中给出了两个算法，Prime算法和kruskal算法。这是两个思想完全不同的算法，下面即为关于这两个算法中的Prime算法的总结。

本来以为这部分模拟起来很容易，算法实现起来比较麻烦，所以估计不会考大题，最多就是考一个模拟过程。但是！！！去年的考题中就出现了这个算法的题目，说来惭愧，我一直以为那道题考的是Dijkstra算法。我抱着押它不考大题的心态去见我导师，导师说这个算法很简单的，你怎么会不会？然后听完老师的讲解，豁然开朗，突然感觉对其进行算法实现也不是问题了。

目录

《数据结构与算法》——图的最小生成树之普利姆算法（Prime）总结

定义

伪代码实现

性能分析及应用

性能分析

应用

参考文献

什么是Prime算法？它的核心思想是什么？

在此，我要引入一个小故事，一个在Dijkstra算法中引用过的小例子。

在一片广袤无垠的大海上，一艘名为泰坦尼克号的游轮在航行，而你恰巧就在这船上，很不幸船突然撞倒了冰山上，所有的人都在逃生。幸运的是，你现在跳到了一艘救生艇上，现在救生艇下面漂着100个人，你和这100个人之间或多或少的都有些联系，救生艇能将你们所有人救出来，但救生艇每次只能上一个人，在忽略人员性别等问题，单纯从和你相关关系的角度出发的情况下，请问怎么救人？

在题目中“你”是一个只看私人感情的人，毋庸置疑，得先救出和自己关系最好的人小A，然后救生艇上就变成了你们两个再管理了，下一个救谁？通过商量决定救起下一个和俩人关系相对较好的人，即从｛自己与水中人的关系，小A与水中人的关系｝中进行比较选出最好关系对，于是你们救起了小B，此时变成了你们三个人一起管理救生艇，类似的从｛自己与水中人的关系，小A与水中人的关系，小B与水中人的关系｝中进行比较选出最好的关系对，并由其救起小C，以此类推，直至将所有落水者救出为止。（注：本例子只用作辅助理解，并无其他意思。）

在救人的过程中，我们需要两个名单作为记录，一个用于记录各个落水者与“你（们）”的关系程度，一个用于记录救起各个落水者的人员。

        即核心思想为：存在两个集合一个空集U和一个满集A，首先从A中取出一个元素作为起始点添加入U中，从A中寻找和集合U中所有点最近的一个点添加入集合U中，记录导致该点加入U的关系边，直至将A中所有的点添加入U中，最终得到的所有的关系边所构成的树型结构即为最小生成树。

用算法的语言来描述如下：

arcs[][]：记录各个顶点到其它顶点的直接长度。（包括“你”在内的各个落水者的直接关系）

path[]：记录源点到各个节点的最短路径的前驱节点（救起各个落水者的人员），初始值为arcs[v0][i]（和“你”的关系）。

lowcost[]：记录源点到各个节点的最短路径长度。（关系）

假设从v0出发，初始化：U=｛v0｝，lowcost [i]=arcs[v0][i]，path[i] = v0，i为集合v剩余节点，v=v-s（在集合v中去掉初始点）

while(v集合不为空)｛

从集合v中选出一个顶点vj，它满足Min{ lowcost [vi]其中,vi属于v}，此点即为此时到集合U的一条最短路径的终点U = U +{vj}  v=v-{vj}

修改lowcost[vj] = Min{ lowcost [vj],arcs[vi][ vj]},若lowcost发生变化，则path[vj] = vi

｝

输出所有的所构成的树形结构即为所求。