首页 > 试题广场 >

下列关于最小生成树的说法中，正确的是（）。

[单选题]

Ⅰ．最小生成树的代价唯一
Ⅱ．所有权值最小的边一定会出现在所有的最小生成树中
Ⅲ．使用普里姆（ Prim）算法从不同顶点开始得到的最小生成树一定相同
Ⅳ．使用普里姆算法和克鲁斯卡尔（ Kruskal）算法得到的最小生成树总不相同

查看答案及解析

philian

A、既然是最小生成树，那么代价一定是唯一确定的最小值，但是树形可能不一样
B、设想所有边权值都相同，那么当边数>顶点数-1时，自然有某些边不会出现在最小生成树里
C、情况如B
D、不一定，情况如B

发表于 2016-12-16 17:42:51 回复(1)

rppp

A选项，最小生成树的代价是唯一确定且最小，但树形可能不一样

B、C或D选项，说的太一定了

发表于 2017-07-22 20:16:52 回复(0)

期年之后✅已认证💯

当所有的最小边都被包含在最小生成树中，才唯一

发表于 2019-10-26 17:14:38 回复(0)

Ari1

Prim 算法是将点分开，选靠近结点的非相同树，可以形容为小树苗长大；

Kruskal算法是将边分开，选最小代价的边，排除连接在一棵树上的边，可以形容为，树枝各长各的最后合成一棵完整的树

发表于 2019-05-31 16:24:22 回复(0)

YoJay

II权值相等的边构成回路

IV各边权值不同，生成的最小生成树唯一

发表于 2018-07-17 21:55:43 回复(0)

提交观点

问题信息

树

上传者：城市里的养猫者

难度：

5条回答 204收藏 16379浏览

扫一扫，把题目装进口袋