2. 考研
  3. 下列关于最小生成树的叙述中，正确的是_______。 Ⅰ．最小生成树的代价唯一 Ⅱ．所有权值最小的边一定会出现在所有的最小生成树中 Ⅲ．使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同 Ⅳ．使用普里姆算法和克鲁斯卡尔(Kmskal)算法得到

下列关于最小生成树的叙述中，正确的是_______。 Ⅰ．最小生成树的代价唯一 Ⅱ．所有权值最小的边一定会出现在所有的最小生成树中 Ⅲ．使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同 Ⅳ．使用普里姆算法和克鲁斯卡尔(Kmskal)算法得到

admin2015-12-30  44
问题 下列关于最小生成树的叙述中，正确的是_______。
Ⅰ．最小生成树的代价唯一
Ⅱ．所有权值最小的边一定会出现在所有的最小生成树中
Ⅲ．使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同
Ⅳ．使用普里姆算法和克鲁斯卡尔(Kmskal)算法得到的最小生成树总不相同
选项 A、仅Ⅰ
B、仅Ⅱ
C、仅Ⅰ、Ⅲ
D、仅Ⅱ、Ⅳ
答案A
解析 对于Ⅰ，最小生成树的树形可能不唯一(这是因为可能存在权值相同的边)，但是代价一定是唯一的，Ⅰ正确。对于Ⅱ，如果权值最小的边有多条并且构成环状，则总有权值最小的边将不出现在某棵最小生成树中，Ⅱ错误。对于Ⅲ，设N个结点构成环，N-1条边权值相等，则从不同的顶点开始普里姆算法会得到N-1中不同的最小生成树，Ⅲ错误。对于N，当最小生成树唯一时(各边的权值不同)，普里姆算法和克鲁斯卡尔算法得到的最小生成树相同，Ⅳ错误。
转载请注明原文地址:https://www.kaotiyun.com/show/WBRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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