习题一解答
1.求图1所示网络的最小生成树。
(1) 用Kruskal算法； (2) 用Prim算法； (3) 用破圈法。
解： 设
，即为连接点
的边。
(1)按各边的权非减次序将网络中的边排列为
。
则求解过程如下表所示：
|
步骤 |
考虑边及其权 |
取 舍 |
结果 |
|
(1) |
|
取 |
|
|
(2) |
|
取 |
|
|
(3) |
|
有圈 |
|
|
(4) |
|
取 |
|
|
(5) |
|
有圈 |
|
|
(6) |
|
取 |
|
|
(7) |
|
有圈 |
|
|
(8) |
|
取 |
|
|
停止 |
步骤(8)所得的 |
||
(2)根据Prim算法的一般过程，可用列表形式表示整个解题过程(见下表，表中【
】表示在该步所取边的权)。
即为所求最小生成树(如图1.2)。由此可见，最小生成树并不唯一，但总权是相同的，均为15。
|
步骤 |
|
|
|
|
|
|
|
|
|
|
(1) |
1 |
|
|
|
5 |
|
|
7 |
【4】 |
|
(2) |
6 |
|
|
|
【3】 |
4 |
|
5 |
|
|
(3) |
2 |
|
|
|
|
2 |
【1】 |
5 |
|
|
(4) |
4 |
|
|
|
|
【2】 |
|
5 |
|
|
(5) |
3 |
|
|
|
|
|
|
【5】 |
|
|
(6) |
5 |
|
|
|
|
|
|
|
|
(3)用破圈法求所示网络的最小生成树
|
步骤 |
讨论对象 |
考虑一个圈 |
舍去圈中最大边 |
结果 |
|
(1) |
图1 |
|
|
图1.3(a) |
|
(2) |
图1.3(a) |
|
|
图1.3(b) |
|
(3) |
图1.3(b) |
|
|
图1.3(c) |
|
(4) |
图1.3(c) |
|
|
图1.3(d) |
|
(5) |
图1.3(d) |
|
|
图1.3(e) |
|
停止 |
图1.3(e)中已经没有圈，故算法到此终止，图1.3(e)就是一个最小生成树，总权为15，树由边 |
|||
【关闭】
，舍去
，舍去
，舍去
中包含图1所给网络的所有顶点，故算法到此结束。
即为所求的最小生成树(如图1.1)，总权为15。
，
，
，
，
组成。