【例6-5】 一个带权无向图的最小生成树是否一定唯一？在什么情况下构造出的最小生成树可能不唯一？
A: 解：一个带权无向图的最小生成树不一定是唯一的。从Kruskal算法构造最小生成树的过程可以看出，当从图中选择当前权值最小的边时，如果存在多条这样的边，并且这些边与已经选取的边构成回路，此时这些边就不可能同时出现在一棵最小生成树中，对这些边的不同选择结果可能会产生不同的最小生成树。
B: 111
C: 111
D: 111
A: 解：一个带权无向图的最小生成树不一定是唯一的。从Kruskal算法构造最小生成树的过程可以看出，当从图中选择当前权值最小的边时，如果存在多条这样的边，并且这些边与已经选取的边构成回路，此时这些边就不可能同时出现在一棵最小生成树中，对这些边的不同选择结果可能会产生不同的最小生成树。
B: 111
C: 111
D: 111
举一反三
- 以下关于最小生成树说法正确的是(). A: 最小生成树是指边数最少的生成树 B: 从n个顶点的连通图中选取n-1条权值最小的边，即可构成最小生成树。 C: 只要带权无向图没有权值相同的边，其最小生成树就唯一。 D: 只要带权无向图中有权值相同的边，其最小生成树就不可能是唯一的。
- 对某个带权连通图构造最小生成树,以下说法中正确的是() I.该图的所有最小生成树的总代价一定是唯一的 Ⅱ.其所有权值最小的边一定会出现在所有的最小生成树中 Ⅲ.用Prim算法从不同顶点开始构造的所有最小生成树一定相同 Ⅳ.使用Prim算法和 Kruskal算法得到的最小生成树总不相同
- 一个带权无向图的最小生成树是否一定唯一？在什么情况下构造出的最小生成树可能不唯一？
- 利用Kruskal 算法，构造图G1的最小生成树，按并入最小生成树中边的顺序，写出最小生成树的各条边，求最小生成树的权。5d23a24ace1ea3b8e52c829b2ddcff22.jpg
- 【单选题】给定有权无向图如下。关于其最小生成树,下列哪句是对的? A. 最小生成树不唯一，其总权重为 23 B. 最小生成树唯一，其总权重为 20 C. 边 (B, F) 一定在树中，树的总权重为 23 D. 边 (H, G) 一定在树中，树的总权重为 20