1. TE=Ф ,U={u0} 2. 当U≠V，重复下列步骤： (1)选取（u0,v0)=min{cost(u,v)|u∈U,v∈V-U}，
保证不形成回路
(2)TE=TE+（u0,v0), 边（u0,v0)并入TE (3)U=U+{v0}，顶点V0 并入U
特点: 以连通为主、选代价最小的邻接边
说明：Prim算法的起始点（可不写，默认为0）
翻译训练1．学生结合课下注释和工具书自行疏通文义，并画出不解之处。【教学提示】节奏划分与明确文意相辅相成，若能以节奏划分引导学生明确文意最好；若学生理解有限，亦可在解读文意后把握节
奏划分。2．以四人小组为单位，组内互助解疑，并尝试用“直译”与“意译”两种方法译读文章。3．教师选择疑难句或值得翻译的句子，请学生用两种翻译方法进行翻译。翻译示例：若夫日出而林霏开，
【练习】请用kruskal算法找出下图最小生成树。
练习
利用克鲁斯卡尔算法构造最小生成树 算出该最小生成树的代价
最
1
10
小
生
成
21 6
树 19
算
法
33
思
想
5
18
二
1
10
6 Prim算法
2
11
5
6
3
14 6
4
2
11
5
6
3
初始条件
点集合={u0}， TE={φ}。
5
18
4
普里姆（Prim）最小生成树算法
1
③
④
3
42
⑤
6
利用Prim演算法找最小生成树
以A点为起始点
L ：A D B C E F T ： h c d e a
A
B
C
9
8
11
8
3
9
5 3
6
11
Weight: 28 D
E
两种生成树算法比较
克鲁斯卡尔算法 ---------适合求边稀疏的网的最小生成树
普利姆算法 ---------适合求边稠密的网的最小生成树
在众多可选边中，如何选择n-1条边，使总代价最 小？这就是求该网络最小生成树问题。
32
A
54
B
36
45
16
C
21
69 47
D
40
E
32 A 16 D
B
36
C
21
E
如何构造图的最小生成树？
1
10
21 6
19
33
5
18
2
1
11
5
6 14
3 最小生成树
6
4 5
10
2
11
5
6
6
3
18
4
最
1
10
小
生
成
第五章 图
5.4 图的最小生成树
难点：生成树概念的理解 重点：普里姆算法、克鲁斯卡尔算法
图的生成树
•设无向连通图G=（V，{E}）， 其子图G’=（V，{T}）满 足： ① V(G’)=V(G) n个顶点 ② G’是连通的 ③ G’中无回路
则G’是G的生成树
•判断是否是生成树：具有n个顶点的无向连通图G （１） 必然包括n个顶点 （２） 含n-1条边 （３） 无回路/连通
本节重点
理解生成树概念 重点掌握prim算法和Kruskal算法构造网络的
的最小生成树 理解最小生成树的现实意义
【练习1】请对下图的无向带权图： （1） 按普里姆算法求其最小生成树； （2）按克鲁斯卡尔算法求其最小生成树； （3）计算最小生成树的权值；
V0
6
6
V1
5
3
无向连通图的生成树举例
举例：有如下无向连通图
A
B
C
图G
D
E
F
思考题：
判断下列说法是否正确
（1）图的生成树是唯一的。
（2）在有n个顶点的无向图中，有n-1 条边的 图一定是生成树。
深度优先生成树和广度优先生成树P81
根据深度和广度优先搜索法进行遍历就可以得 到两种不同的生成树，并分别称为深度优先生 成树和广度优先生成树。
以以VV00为为起起始始点点,,广深度度优优先先遍遍历历
V0
V1
V2
VV00
VV11
VV22
V3
V4
V5
V6
VV33
VV44
VV55
VV66
V7
VV77
深广度度优优先先生生成成树树
5.4.2网络的最小生成树P82
如在果一连个通图图的是每一条个网边络或，弧称上该，网有络时中可所以有标生上成具树 中有权某值种总含和义最的小数的生值成，树这为种最边小或生弧成上树带(也权称的最图 小称代为价网生（成N树e)t。work）。
么不能划分为“山/行六七里”？
明确：“山行”意指“沿着山路走”，“山行”是个状中短语，不能将其割裂。“望之/蔚然而深秀者”为什么不能划分为“望之蔚然/而深秀者”？明确：“蔚然而深秀”是两个并列的词，不宜割裂，“望
之”是总起词语，故应从其后断句。【教学提示】引导学生在反复朗读的过程中划分朗读节奏，在划分节奏的过程中感知文意。对于部分结构复杂的句子，教师可做适当的讲解引导。目标导学三：结合注释，
V0
6
6
V1 1 V3
5 V2 5
3
2
64
V4
6
V5
V0
6
V1
V3
5 V2 5
V4 6 4V5
V0
V1 1 V3
5 V2
3
2
V4 4V5
V0
V1 1 V3
V2
3
V4
6
2
4V5
生成树的实际意义
例如：铺设煤气管道问题（图形结构） 假设要在某个城市的n个居民区之间铺设
煤气管道，则在这n个居民区之间只要铺设n-1 条管道即可。假设任意两个居民区之间都可以 架设管道，管道铺设方案。
练习 ---利用Prim算法构造最小生成树
算出该最小生成树的代价
V0
6
5
V1
5
3
1
V3
5
V2
2
6
4
V4 6 V5
利用Prim算法构造最小生成树步骤
①
6
5
1
② 5 ③5
④
36
42
⑤6 ⑥
初始化： ①
①
第1步： 1
③
①
第2步：
1
③
4
6
①
第3步：
1
③
④
42
6
①
第4步：②
5
1
③
④
42
第5步：
①6
②
5
21 6
树 19
算
法
33

思
想
5
18
一
1
10
Kruskal算法
6
2
11
5
6
3
14
1
10
2
6
起始条件：生成树只
包含图的所有11顶点。5
4
6
2
11
5
5
18
6
3
6 4
5
18
4 最小生成树不一定唯一
Kruskal算法（克鲁斯卡尔）总结
Kruskal算法步骤： 初始时，顶点={图中所有的顶点}，边={φ}。 重复下述操作：在图的边集中按权值自小至大依次选 择边，若选取的边使生成树不形成回路，则将该边加 入到生成树集合中；依次类推，直到将所有顶点都连 通（所有顶点都在同一连通分量上为止），这时产生 的具有n-1条边的一棵最小生成树。
1
V3
2
V2
2
6
4
V4
6
V5
【练习2】 所示的连通图，请分别用Prim 和Kruskal算法构造其最小生成树。
问答题
试着找出下图网G的最小生成树；
12
20
A
B
C
4
8
9
12
15
E
F
6
G
D
10
仙也。名之者/谁？太守/自谓也。太守与客来饮/于此，饮少/辄醉，而/年又最高，故/自号曰/醉翁也。醉翁之意/不在酒，在乎/山水之间也。山水之乐，得之心/而寓之酒也。节奏划分思考“山行/六七里”为什