数据结构

一个带权无向图的最小生成树是否一定唯一？在什么情况下构造出的最小生成树可能不唯一？

题目

一个带权无向图的最小生成树是否一定唯一？在什么情况下构造出的最小生成树可能不唯一？

参考答案和解析
正确答案: 一个带权无向图的最小生成树不一定是唯一的。从Kruskal算法构造最小生成树的过程可以看出，当从图中选择当前权值最小的边时，如果存在多条这样的边，并且这些边与已经选取的边构成回路，此时这些边就不可能同时出现在一棵最小生成树中，对这些边的不同选择结果可能会产生不同的最小生成树。
如果没有搜索结果，请直接 联系老师 获取答案。
相似问题和答案

第1题：

连通图的各边权值均不相同，则该图的最小生成树是唯一的。()


参考答案：正确

第2题：

图的生成树是不唯一的,一个连通图的生成树是一个最小连通子图,n个顶点的生成树有n－1条边,最小代价生成树是唯一的。( )

此题为判断题(对，错)。


正确答案:正确

第3题：

如下所示是一个带权连通无向图，其最小生成树各边权的总和为

A． 24

B．25

C．26

D．27


正确答案：C

第4题：

带权无向图的最小生成树是唯一的。

此题为判断题(对，错)。


正确答案：×

第5题：

任何一个带权的无向连通图的最小生成树()。

A.只有一棵

B.有一棵或多棵

C.一定有多棵

D.n+2


正确答案：B

第6题：

图的最小生成树一定唯一。()

此题为判断题(对，错)。


正确答案：×

第7题：

一栈连通图的最小生成树可能不唯一,但是该最小生成树边上的总长度是唯一的()

此题为判断题(对，错)。


参考答案：对

第8题：

带权的连通无向图的最小(代价)生成树必是唯一的。()


参考答案：错误

第9题：

如图所示的带权无向图的最小生成树的权为 ( )

A．51

B．52

C．54

D．56


正确答案：C
解析：根据最小生成树的构造过程，可知在构造本题中无向图的最少生成树时，将选取权值分别为10、14、12、18的边，所以此最小生成树的权即各边权值之和即54。

第10题：

如下所示是一个带权连通无向图，其最小生成树各边权的总和为

A．24

B．25

C．26

D．27


正确答案：C

更多相关问题
相关内容