Y
T←T+ {ek},
k←k+1 w←w+wk,
t←t+1,k←k+1
2020/12/13
Prim法求最小支撑树
Kruskal法盯住边,而Prim法更注意顶点: 从任一顶点开始都可以,逐个把最近的顶点找进来(找过的不找,
就不会成圈)。 算法如下: S1:T←{v1}, S←V\{v1}, w←0
否则转S5 S5: T←T∪{ek},w←w+wk,
t←t+1, k←k+1,转S3 S6:输出T及w，结束。 T为最小树，w为T的权。这个算
法叫Kruskal算法(避圈法)
START
E的权排序w1≤w2≤…≤wm w←0,T←φ,k←1,t←0
t=n-1?
Y
N
T’←T∪{ek}
T’成圈? N
பைடு நூலகம்
END
S2:若S=φ转S5,否则转S3
设 S3::m vvij STin{w(vivj)}w(vlvk)
S4:T←T∪{vk},S←S\{vk},w←w+w(vlvk),转S2 S5:输出T及w,停止.
2020/12/13
用Prim算法(就近法)求赋权连通图G的最小树
TTTT=={={=vv{{11vv,,1v1v2},2,v,v,v2v233,},v,vv355},,,vvv566,}v7},v4}
最小生成树问题
2020/12/13
赋权连通图的最小支撑树
边的权:G=(V,E)对每边ei∈E规定一个非负的实数w(ei)叫“权”； 带权图:每边都有权的图叫赋权图或带权图； 树:其特点之一是边数比顶点数少一； 图G的支撑树T:E(T)E(G),V(T)=V(G),即由G找T，顶点一个不能少，
边可能删去几条，但T必须是树[当然如G不是连通图，则没有支撑树]。 最小树:赋权的连通图G的众多支撑树中必至少有一，其各边权之和为
最小的，它就叫G的一棵最小支撑树或最小生成树；简称最小树或最短 树[管线铺设]。 最小树的存在性：赋权的连通图G =(V,E),记m=|E|, n=|V|,支撑树T的 边数|E(T)|=n-1,E(T)必为V的n-1元子集，显然这种子集合最多 个，所以支撑树是有限的，其权组成有限集，必有最小的[但可能C mn不1 唯 一]。
2020/12/13
求最小树的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 S4:若T∪{ek}有圈则k←k+1转S4，
S={v2,v3,v4,v5,v6,v7}
V2
5
V6
4
2
9
12
V1
3
8
V3
6
4
5
6
V5
V7
10 7
7
11
2020/12/13
V4
∴最小树的权为24，最小树为 Tree={v1v2,v1v3,v2v5,v5v6,v6v7,v6v4}