最小生成树算法详解(课堂PPT)

本章小结
1 深刻理解基本回路、基本回路系统、基本割集、基本割集系统，并且对给定的生成树能 熟练地求出它们。
2 熟练地应用Kruskal算法求最小生成树。关于生成树的思维形式注记图如图所示。
W（TG）=1+3+4+8+9+23=48
算法13.3 （破圈法）
1）令E’=E; 2 选取E’中的一条简单回路C，设C 中权最大的边为e，令E’=E’-{e}； 3 重复步骤2），直到|E’|=|V|-1为止。 不停地选取图G 中的一条简单回路，从回路中删去权值最大的一条边，直 到图中无简单的回路为止。
1）按权值升序将图G 的边排序，得到表L；
2）令S=∅；
3 在表L中依次选取下一条边e，如果e ∉S ，且S ∪{e}构成的 子图是无圈图，则令S=S ∪{e}；
4 若|S|=n−1，则算法停止，输出集合S即为所求。否则，转3）， 继续遍历表L。 可以证明，算法13.1求得的是图G 的最小生成树。
例13.7
3 若|E(T)|=n−1，算法停止，输出E(T)。否则，转2），继续向树中增加新 结点。
例.8
右左图所示的赋权图G表 示七个城市a，b，c，d， e，f，g及架起城市间直 接通讯线路的预测造价。 试给出一个设计方案使 得各城市间能够通讯并 且总造价最小，并计算 出最小造价。
a
20
b
a
b
23
1
因为它们的加入会形成圈。
（4）此时S中有6条边，满足|S| =n - 1 ，所以算法结束。
得到的最小生成树如图（b）所示，树权为10。
算法13.2 （Prim算法）
设图G有n个结点，按以下步骤可以求得图G的最小生成树。

proc Union(i,j,c:longint); /*合并i和j所在集合 */
Var x,y:longint;
{ x←top(i); y←top(j); 点j所在子树的根*/
/*分别取出顶点i和顶
if x<>y Then { inc(ans,c);f[y]←x;}; /*若i 和j分属于两棵子树，则该边权计入最小生成树的权和， 两棵子树合并*/
Writeln(ans);
显然, Kruskal算法的效率取决于边数m,因此适用与
稀疏图。
.
②、Prim算法
集合A中的边总是只形成单棵树，每次添加到 树中的边都是使树的权尽可能小的边。
.
设 d[i]—顶点i与生成树相连的最短边长； ba[i]—顶点i在生成树的标志； w[i,j]—（i,j）的边长。若图中不存在边 （i,j），则w[i,j]=∞ min—所有未在生成树的顶点的最小距离 值
top←f[i]; /*返回顶点i所在并查集的代表 顶点*/ };/*top*/
.
通过过程Union(i,j,c)合并顶点i和顶点j所 在的两棵树
现有边权为c的边（i，j）。若该边的两个端点 分属于两棵树，顶点i和顶点j所在子树的根分别 为x和v，则(i,j) 加入最小生成树，合并两棵树 （即顶点i和顶点j所在的并查集）。
for j←1 to n do
if not ba[j]and(d[j]<min) then { k←j；min←d[j] }； /*then*/
if min= maxint then { ans←-1；break；}；/*若这样的顶点不存 在，则无解退出*/
ans←ans+min；ba[k]←true；/*最小距离值min计入生成树的权和, 顶点k进入生成树*/

个，所以支撑树是有不唯一]。
C n1 m
求最小树的Kruskal算法
赋权的连通图G=(V,E)中m=|E|,n=|V|,
S1:对E中各边的权排序，设 w1≤w2≤…≤wm,wi=w(ei)
S2:初始化： w←0,T←φ,k←1,t←0
S3:若t=n-1则转S6，否则转S4
Y
N
T’←T∪{ek}
T’成圈? N END
Y
T←T+ {ek},
k←k+1 w←w+wk,
t←t+1,k←k+1
用Kruskal算法求最小树
用Kruskal算法(避圈法)求赋权连通图G的最小树
V2
5
V6
Kruskal法盯住边,而Prim法更注意顶点:
T为最小树，w为T的权。
4
T={v1,v2,v3,v5}
Prim法求最小支撑树 E的权排序w1≤w2≤…≤wm w←0,T←φ,k←1,t←0
对要m让条程边序的读边懂长“图排”，序S程3，:序m如个何元判素断排是序否较成好“的圈算”？法谈是何基容于易分，治时策间略、的空快间速复排杂序性(Q绝u不ick应S小or看ting)，其时间复杂性是O(m㏒m)。
min S2:初始化：w←0,T←φ,k←1,t←0 设: {w(vv )}w(vv ) 简对称m条最边小的树边或长最排短序树，[管vvm线ij个 铺ST 元设素]。排序较好的i算法j是基于分治策略的快l速排k序(Quick Sorting)，其时间复杂性是O(m㏒m)。
S4:若T∪{ek}有圈则k←k+1转S4，否则 转S5
S5: T←T∪{ek},w←w+wk, t←t+1, k←k+1,转S3

(2,5) 添加
{1,3},{4, 6},{2,5}
(3,6) 添加
{1,3,4, 6},{2,5}
(1,4) 放弃
因构成回路
(3,4) 放弃
因构成回路
(2,3) 添加
{1,3,4,5,6,2}
9
算法难点及解决方案
• 如何从所有边中选择代价最小的边：
– 用一个优先级队列来实现。将所有的边放入一个优先级 队列，边的优先级就是它的权值。权值越小，优先级越 高。
数据结构 Data Structure 第十三章 最小生成树
1
第13章 最小生成树
• 生成树与最小生成树 • Kruskal算法 • Prim算法 • 算法的正确性
2
生成树
• 生成树是无向连通图的极小连通子图。包含图的 所有 n 个结点，但只含图的 n-1 条边。在生成树 中添加一条边之后，必定会形成回路或环。
23
定理的证明
• 用反证法证明。 • 假定在图G = {V，E } 中，存在一棵不包括代价
• 在一个连通图中，一般边数总比结点数大，所以， Kruskal算法的时间复杂度是O(E|log|E|)。
14
第13章 最小生成树
• 生成树与最小生成树 • Kruskal算法 • Prim算法 • 算法的正确性
15
Prim算法
• 从顶点的角度出发。初始时，顶点集U为空，然 后逐个加入顶点，直到包含所有顶点。
• 如何判断加入一条边后会不会形成回路：
– 用并查集来实现。将一个连通分量表示为并查集中的一 个子集，检查一条边加入后会不会形成回路可以通过对 边的两个端点分别执行Find操作。如果两个Find的结果相 同，则表示两个端点已连通，加入这条边会形成回路， 否则将这条边加入生成树。添加边的操作就是一个Union 操作，将两个端点所属的子集归并起来，表示其中的所 有顶点都已连通。