首页 > 试题广场 >

任何一个带权的无向连通图的最小生成树（）

[单选题]

推荐

clear_rain

选B

【分析】

本题考查无向连通图的性质

树是e=v-1边数最少的无向连通图，故必有树（至少一棵）。

也可以有多棵最小生成树，例如图(i-j k :点i到j间有边且权为k)：
1-2 1
2-3 1
1-3 1
选边1-2，2-3是边权和为2的最小生成树；
选边1-3，2-3也是边权和为2的最小生成树。
所以选B

编辑于 2019-03-22 16:52:07 回复(0)

白驹之过隙

选B。

对于连通图而言从图中不同顶点出发或从同一顶点出发按照不同的优先搜索过程可以得到不同的生成树。

发表于 2019-03-22 10:32:52 回复(0)

牛客网ID：681413702

1.可以有多棵最小生成树
例如图(i-j k :点i到j间有边且权为k)
1-2 1
2-3 1
1-3 1
选边1-2，2-3是边权和为2的最小生成树
选边1-3，2-3也是边权和为2的最小生成树
2.树是e=v-1边数最少的无向连通图，故必有树

故选B

发表于 2019-03-21 17:40:55 回复(1)

牛客688777445号

是否有多颗是取决于权值是否有重复。有重复才存在多棵树的可能。

发表于 2021-12-20 18:11:52 回复(0)

天尊墨宇

选B

【分析】

本题考查无向连通图的性质

树是e=v-1边数最少的无向连通图，故必有树（至少一棵）。

编辑于 2020-07-05 08:51:43 回复(0)

提交观点

问题信息

树图

上传者：阿奻_

难度：

5条回答 192收藏 12646浏览

扫一扫，把题目装进口袋