第7章 图 7.5 普里姆算法《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）
2023-08-30
|
22页
|
114人阅读
|
0人下载
普通
内容正文：
第7章 图
7.1 图的基本概念
7.2 图的存贮结构
7.3 图的遍历
7.4 图的连通性问题
7.5 有向无环图及其应用
7.6 最短路径
下面将介绍求最小生成树的两种方法：普里姆算法和克鲁斯卡尔算法。
7.4.2 普里姆算法
1． 普里姆(prim)算法思想
下面仅讨论无向网的最小生成树问题。
普里姆方法的基本思想是：在图中任取一个顶点K作为开始点，令U={k}，W=V-U，其中V为图中所有顶点集，然后找一个顶点在U中，另一个顶点在W中的边中最短的一条，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删去这些顶点，然后重新调整U中顶点到W中顶点的距离, 使之保持最小，再重复此过程，直到W为空集止。
例
1
6
5
4
3
2
6
5
1
3
5
6
6
4
2
5
1
3
1
1
6
3
1
4
1
6
4
3
1
4
2
1
1
6
4
3
2
1
4
2
5
1
6
5
4
3
2
1
4
2
5
3
Prim算法构造最小生成树演示
假设开始顶点就选为顶点1，故首先有U={1}，W={2，3，4，5，6}
(a ) 无向网
(b) u={1} w={2,3,4,5,6}
6
4
1
2
4
3
6
2
1
3
5
7
6
5
5
5
1
2
3
4
5
6
6
5
1
3
1
2
4
5
6
1
4
5
5
5
3
1
2
4
5
6
4
2
1
5
5
(c ) u={1,3} w={2,4,5,6}
(d) u={1,3,6} w={2,4,5}
(e) u={1,3,6,4} w={2,5}
(f) u={1,3,6,4,2} w={5}
3
1
2
4
5
6
4
2
1
5
5
1
2
4
3
5
6
4
2
1
5
3
(g) u={1,3,6,4,2,5} w={ }
5
4
2
1
3
1
2
4
3
5
6
图8-20 prim方法构造最小生成树的过程
7.4.3 克鲁斯卡尔（kruskal）算法
1． 克鲁斯卡尔算法基本思想
克鲁斯卡尔算法的基本思想是：将图中所有边按权值递增顺序排列，依次选定取权值较小的边，但要求后面选取的边不能与前面选取的边构成回路，若构成回路，则放弃该条边，再去选后面权值较大的边，n个顶点的图中，选够n-1条边即可。
例如，对图7-20（a） 中无向网，用克鲁斯卡尔算法求最小生成树的过程见图7-22。
2
4
5
6
1
3
1
2
5
1
3
1
4
2
6
(a) 选第1条边
(b) 选第2条边
(c )
选第
3
条边
(d)
选第
4
条边
2
3
5
1
3
1
4
2
6
4
2
1
2
3
5
1
4
3
6
(e )选第5条边不能选(1,4)边，会构成回路，但可选(2,3)或(5,3)中之一
资源预览图
1
2
3
4
5
6
由于学科网是一个信息分享及获取的平台，不确保部分用户上传资料的 来源及知识产权归属。如您发现相关资料侵犯您的合法权益，请联系学科网，我们核实后将及时进行处理。