目的:领会克鲁斯卡尔算法去带权连通图中最小生成树的过程和相关算法设计。内容:编写一个程序,实现求带权连通图最小生成树的克鲁斯卡尔算法。对于下图所示的带权连通图G,输出从顶点1出发的一棵最小生成树。
举一反三
- 如下图所示的带权图：(1)按照普里姆算法，从顶点v1出发，生成最小生成树，按生成次序依次写出各条边；(2)按照克鲁期卡尔算法，生成最小生成树，按生成次序依次写出各条边；(3)画出该图最小生成树，并求出它的权值之和。[img=387x175]17e44a231db4817.jpg[/img]
- 给定一个带权无向图，用克鲁斯卡尔算法和普里姆算法得到的最小代价生成树相同。
- 对于如下图所示的带权无向图,给出利用普里姆算法(从顶点0开始构造)和克鲁斯卡尔算法构造出的最小生成树的结果(依次给出按算法求出的最小生成树的各个边)。
- 对________，用克鲁斯卡尔算法求最小生成树较为合适。 A: 非连通图 B: 连通图 C: 稀疏图 D: 稠密图
- 给定带权无向图，用普里姆和克鲁斯卡尔算法得到的最小代价生成树不一定是同一棵。