最小(代价)生成树
标签: 数据结构
学习人数: 17183


全屏播放
赞赏支持

关于图的几个概念定义:

 

 

什么是最小生成树?

现在假设有一个很实际的问题:我们要在n个城市中建立一个通信网络,则连通这n个城市需要布置n-1一条通信线路,这个时候我们需要考虑如何在成本最低的情况下建立这个通信网?
于是我们就可以引入连通图来解决我们遇到的问题,n个城市就是图上的n个顶点,然后,边表示两个城市的...

登录查看完整内容


课后作业

课后习题

 

【2012年真题】下列关于最小生成树的叙述中,正确的是()。 
Ⅰ.最小生成树的代价唯一 
Ⅱ.所有权值最小的边一定会出现在所有的最小生成树中2 
Ⅲ.使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同 
Ⅳ.使用普里姆算法和克鲁斯卡尔(Kruskal)算法得到的最小生成树总不相同 
A.仅Ⅰ 
B.仅Ⅱ 
C.仅Ⅰ、Ⅲ 
D.仅Ⅱ、Ⅳ 

参考答案:A
答案解析:考查最小生成树、及最小生成树算法的性质。 
对于 I,最小生成树的树形可能不唯一(这是因为可能存在权值相同的边),但是代价一定是唯一的,I 正确。对于 II,如果权值最小的边有多条并且构成环状,则总有权值最小的边将不出现在某棵最小生成树中,II 错误。对于 III,设 N 个结点构成环,N-1 条边权值相等,则从不同的顶点开始普里姆算法会得到 N-1 中不同的最小生成树,III 错误。对于 IV,当最小生成树唯一时(各边的权值不同),普里姆算法和克鲁斯卡尔算法得到的最小生成树相同,IV 错误。 


【2015年真题】求下面带权图的最小(代价)生成树时,可能是克鲁斯卡(Kruskal)算法第 2 次选中但不是普里姆(Prim)算法(从 V4 开始)第 2 次选中的边是()。

A.(V1,V3)    B.(V1,V4)    C.(V2,V3)    D.(V3,V4)

参考答案:C

 

【2018年真题】拟建设一个光通信骨干网络连通BJ、CS、XA、QD、JN、NJ、TL和WH等8个城市,图中无向边上的权值表示两个城市间备选光缆的铺设费用。

请回答下列问题。
(1)仅从铺设费用角度出发,给出所有可能的最经济的光缆铺设方案(用带权图表示),并计算相应方案的总费用。
(2)题目图中可采用图的哪一种存储结构?给出求解问题(1)所使用的算法名称。
(3)假设每个城市采用一个路由器按(1)中得到的最经济方案组网,主机H1直接连接在TL的路由器书上,主机H2直接连接在BJ的路由器上。若H1向H2发送一个TTL=5的IP分组,则H2是否可以收到该IP分组?

参考答案:
(1)为了求解最经济的方案,可以把问题抽象为求无向带权图的最小生成树。可以采用手动prim算法或kruskal算法作图。注意本题最小生成树有两种构造,如下图所示。

方案的总费用为16.
(2)存储题中的图可以采用邻接矩阵(或邻接表)。构造最小生成树采用Prim算法(或Kruskal算法)。
(3)TTL=5,即IP分组的生存时间(最大传递距离)为5,方案1中TL和BJ距离过远,TTL=5不足以让IP分组从H1传送到H2,因此H2不能收到IP分组。而方案2中TL和BJ邻近,H2可以收到IP分组。

 

【2017年真题】使用Prim(普里姆)算法求带权连通图的最小(代价)生成树(MST)。请回答下列问题。
(1)对下列图G,从顶点A开始求G的MST,依次给出按算法选出的边。
(2)图G的MST是唯一的吗?

(3)对任意的带权连通图,满足什么条件时,其MST是唯一的?

参考答案:
(1)依次选出的边为:
(A,D),(D,E),(C,E),(B,C)
(2)图G的MST是唯一的。
(3)当带权连通图的任意一个环中所包含的边的权值均不相同时,其MST是唯一的。


登录后发布评论

1 条评论
朱庇特
2021年8月23日 20:45

【2012年真题】下列关于最小生成树的叙述中,正确的是()。 
Ⅰ.最小生成树的代价唯一 
Ⅱ.所有权值最小的边一定会出现在所有的最小生成树中2 
Ⅲ.使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同 
Ⅳ.使用普里姆算法和克鲁斯卡尔(Kruskal)算法得到的最小生成树总不相同 
A.仅Ⅰ 
B.仅Ⅱ 
C.仅Ⅰ、Ⅲ 
D.仅Ⅱ、Ⅳ 

参考答案:A
答案解析:考查最小生成树、及最小生成树算法的性质。 
对于 I,最小生成树的树形可能不唯一(这是因为可能存在权值相同的边),但是代价一定是唯一的,I 正确。对于 II,如果权值最小的边有多条并且构成环状,则总有权值最小的边将不出现在某棵最小生成树中,II 错误。对于 III,设 N 个结点构成环,N-1 条边权值相等,则从不同的顶点开始普里姆算法会得到 N-1 中不同的最小生成树,III 错误。对于 IV,当最小生成树唯一时(各边的权值不同),普里姆算法和克鲁斯卡尔算法得到的最小生成树相同,IV 错误。