题33

题33

题目

【2015 统考真题】求下面的带权图的最小（代价）生成树时, 可能是 Kruskal 算法 第 2 次选中但不是 Prim 算法 (从 开始) 第 2 次选中的边是 ( ).

A.
B.
C.
D.

分析

kruskal是每个结点独立为一个单独的集合，每次检查权重最小的，合并集合，直到所有的结点都在一个集合中
prim算法每次贪心选还未抵达，同时可达的结点中，权重最小的
prim选择了，然后选1，1和4就不应该出现在集合中，A和D直接排除了

解

C
从 开始,Kruskal 算法选中的第一条边一定是权值最小的 ,选项 错误。
由于 和 已经可达,因此含有 和 的权值为 8 的第二条边一定符合 Prim 算法,排除 A、D。