问题 问答题 简答题

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

答案

参考答案:

一个带权无向图的最小生成树不一定是唯一的。从Kruskal算法构造最小生成树的过程可以看出,当从图中选择当前权值最小的边时,如果存在多条这样的边,并且这些边与已经选取的边构成回路,此时这些边就不可能同时出现在一棵最小生成树中,对这些边的不同选择结果可能会产生不同的最小生成树。

多项选择题