用 Prim 算法和 Kruskal 算法构造图的最小生成树，所得到的最小生成树（　　）。

A. 相同 B. 不相同 C. 可能相同，可能不同 D. 无法比较

[tag_link]

正确答案：C

结论

选 C。

推导

两种算法都遵循 MST 的贪心性质。若 MST 唯一，二者必得到同一棵树；若存在等权边导致多个 MST，选边顺序可能不同，结果也可能不同。

易错点

“都是最小生成树”不等于“边集合必相同”；应区分最小代价相同与树形唯一。