prim算法代码详解（prim算法模板）



在一给定的无向图 中，代表连接顶点 与顶点 的边，而 代表此边的权重，若存在 为 的子集且为无循环图，使得 最小，则此 为 的最小生成树，因为是由图产生的。

最小生成树其实是最小权重生成树的简称。我们称求取该生成树的问题成为最小生成树问题。一个连通图可能有多个生成树。当图中的边具有权值时，总会有一个生成树的边的权值之和小于或者等于其它生成树的边的权值之和。广义上而言，对于非连通无向图来说，它的每一连通分量同样有最小生成树，它们的并被称为最小生成森林。以有线电视电缆的架设为例，若只能沿着街道布线，则以街道为边，而路口为顶点，其中必然有一最小生成树能使布线成本最低。

如图，这个是一个平面图，图中黑色线描述的就是最小生成树，它的权值之和小于其他的生成树。

那么，我们如何来求最小生成树呢，由最小生成树的定义我们可以知道构建最小生成树是可以利用贪心算法去实现的，我们接下来介绍的两种算法也都是利用贪心算法去求得的。因为贪心算法的策略就是在每一步尽可能多的选择中选择最优的，在当前看是最好的选择，这种策略虽然一般不能在全局中寻找到最优解，但是对于最小生成树问题来说，它的确可以找到一颗权重最小的树。

普里姆算法（Prim’s algorithm），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点，且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克发现；并在1957年由美国计算机科学家罗伯特·普里姆独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。（来源于维基百科）

Prim算法是利用贪心算法实现的，我们确定根节点，从这个结点出发。普里姆算法按照以下步骤逐步扩大树中所含顶点的数目，直到遍及连通图的所有顶点。下面描述我们假设是连通网，是上最小生成树中边的集合。

​ ① 。

​ ② 在所有的边找到一条权值最小的边并入集合，同时并入集合。

​ ③ 重复②步骤，知道为止。

此时中必有条边，则即为我们求得的的最小生成树。

我们如果对Dijkstra算法很熟悉的话，Prim算法也很好实现了，它们都是利用了一样的思路，但却不相同。我们用利用数组来表示到集合中最近的距离，用数组来表示最小生成树的边。怎么来表示呢？我们用顶点来形容边，也就是说我们要求的就是数组。其中表示的值就是与顶点相邻边的顶点序号。具体看代码（附带打印最小生成树代码）。

对于此算法，我们图中有个顶点，则第一个进行初始化的循环语句的频度为,第二个循环语句的频度为，但其中第二个循环中有两个内循环：第一个是在中求最小值，其频度为，第二个是重新选择具有最小权值的边，频度为，由此我们可知Prim算法的时间复杂度为，与图中的边数无关，故十分适合于稠密图。

我们用示例来测试：

测试结果如图：

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/rfx/42948.html