2. 公务员
  3. 下列关于最小生成树的叙述，错误的有( )。

下列关于最小生成树的叙述，错误的有( )。

admin2020-01-17  54
问题 下列关于最小生成树的叙述，错误的有(    )。
选项 A、最小生成树的代价唯一
B、所有权值最小的边一定会出现在所有的最小生成树中
C、使用普里姆算法，从不同顶点开始得到的最小生成树一定相同
D、使用普里姆算法和克鲁斯卡尔算法得到的最小生成树总是不同的
答案B,C,D
解析 由于连通图中可能会存在权值相同的边，因此最小生成树是不唯一的，但是构造最小生成树的代价是唯一的。在任一带权图中，权值最小的边一定会被至少一棵最小生成树采用，权值次小的边也会被至少一棵最小生成树采用，但是所有权值最小的边不一定会被全部最小生成树采用。使用普里姆算法从不同顶点开始得到的最小生成树可能不相同，比如在连通图中存在n个顶点构成环，n—1条边权值相等，则从不同顶点开始得到的最小生成树有n—1种。使用普里姆算法和克鲁斯卡尔算法得到的最小生成树可能相同，比如连通图的各条边的权值都各不相同时，最小生成树是相同的。
转载请注明原文地址:https://jikaoti.com/ti/4su9FFFM
本试题收录于： 专业知识题库国家电网招聘分类
0

专业知识

国家电网招聘

相关试题推荐
随机试题
最新回复(0)