概述
prim算法又称普利姆算法，目的是在加权连通图中搜索最小生成树。特点是由顶点出发选边，依次选取两个顶点集合之间权值最小的边，两个顶点集合随之变化，最终形成最小生成树。
- 一个加权连通图，其中顶点集合为V，边集合为E；
- 标记访问过的顶点集合为Vnew，选取的边集合为Enew，初始化都为空
- 假设从V中的任一顶点x开始，则Vnew = {x}
- 重复下列操作，直到Vnew = V。如果顶点有n个，则下面循环为n-1次，因为一次选出一条边，共需n-1条边。
- 在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
- 将v加入集合Vnew中，将<u, v>边加入集合Enew中；
- 使用集合Vnew和Enew来描述所得到的最小生成树。
kruskal算法又称克鲁斯卡尔算法，和prim算法一样，都是用来查找最小生成树的算法。其特点是依次选取最小权值的边，在不形成环路的情况下，将其纳入选取的边集合中，最终形成最小生成树。
最后
以上就是高贵朋友为你收集整理的最小生成树算法：prim算法和kruskal算法的全部内容，希望文章能够帮你解决最小生成树算法：prim算法和kruskal算法所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![[matlab] 22.matlab图论实例 最短路问题与最小生成树 (转载)最短路问题之 Floyd 最短路问题之 dijkstra 算法最小生成树问题之prim最小生成树问题之kruskal (待补充)](/uploads/reation/bcimg6.png)
发表评论 取消回复