普里姆算法（Prim's algorithm）是图中的一种算法，可在加权连通图中搜索最小生成树。
该算法的作用就是根据图中权值找到连接所有顶点的最短路径，也就是连接所有顶点的最小权值之和，也是这个加权图中的最小生成树。
假如我们有 V 表示图中的顶点个数，E 表示图中的边个数。
通过邻接矩阵图表示的简易实现中，找到所有最小权边共需 的运行时间。
使用简单的二叉堆和邻接表来表示的话，普里姆算法的运行时间则可缩减为 。
如果使用较为复杂的斐波那契堆，则可将运行时间进一步缩短为 ，这在连通图足够密集时，可较显著地提高运行速度。
根据上面加权连通图找到最小生成树。
首先选择顶点 A 作为起点。顶点 D、F、B 与 A 相连，且 AD 之间的权值最小，因此选择这条边。此时 A、D 为已选择顶点，E、F、B 为待选择顶点，H、G 为未选择顶点。
下一个顶点应选择离 A、D 权值最小的顶点，因此选择 AB 这条边。此时 A、D、B 为已选择顶点，E、F、G 为待选择顶点，H 为未选择顶点。
下一个顶点应选择离 A、D、B 权值最小的顶点，因此选择 DE 这条边。此时 A、D、B、E 为已选择顶点，F、G、H 为待选择顶点，没有未选择顶点。
下一个顶点应选择离 A、D、B、E 权值最小的顶点，因此选择 EH 这条边。此时 A、D、B、E、H 为已选择顶点，F、G 为待选择顶点，没有未选择顶点。
下一个顶点应选择离 A、D、B、E、H 权值最小的顶点，因此选择 FH 这条边。此时 A、D、B、E、H、F 为已选择顶点，G 为待选择顶点，没有未选择顶点。
最后，只剩下一个顶点 G，到顶点 G 的权值最小的是 HG。现在图中所有顶点都连接了，红色连接的边就是最小生成树，最小生成树的权值之和为 42。
普里姆算法就是通过一个顶点扩散开找权值最小的边，所经过的顶点和边就是这个图的最小生成树。通过不用的数据结构存储图会导致时间复杂度不一致，用邻接矩阵的时间复杂度是 ，二叉堆和邻接表的时间复杂度是
。
版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/rfx/52806.html