最小生成树之 prim 算法
边赋以权值的图称为网或带权图,带权图的生成树也是带权的,生成树 T 各
边的权值总和称为该树的权。
最小生成树(MST):权值最小的生成树。
生成树和最小生成树的应用:要连通 n 个城市需要 n-1条边线路。可以把边
上的权值解释为线路的造价。则最小生成树表示使其造价最小的生成树。
构造网的最小生成树必须解决下面两个问题:
1、尽可能选取权值小的边,但不能构成回路;
2、选取 n-1条恰当的边以连通 n 个顶点;
MST 性质:假设 G=(V,E)是一个连通网,U 是顶点 V 的一个非空子集。若(u,v)
是一条具有最小权值的边,其中 u∈U,v∈V-U,则必存在一棵包含边(u,v)的
最小生成树。
1.prim 算法
基本思想:假设 G=(V,E)是连通的,TE 是 G 上最小生成树中边的集合。算法
从 U={u0}(u0∈V)、TE={}开始。重复执行下列操作:
在所有 u∈U,v∈V-U 的边(u,v)∈E 中找一条权值最小的边(u0,v0)并入集
合 TE 中,同时 v0并入 U,直到 V=U 为止。
此时,TE 中必有 n-1条边,T=(V,TE)为 G 的最小生成树。
Prim 算法的核心:始终保持 TE 中的边集构成一棵生成树。
注意:prim 算法适合稠密图,其时间复杂度为 O(n^2),其时间复杂度与边得数
目无关,而 kruskal算法的时间复杂度为O(eloge)跟边的数目有关,适合稀疏图。
看了上面一大段文字是不是感觉有点晕啊,为了更好理解我在这里举一个例
子,示例如下: