GESP 八级 · GESP202609 C++ 八级 第 9 题

关于最小生成树（MST）算法，下列说法正确的是（　　）。

看到 MST 算法对比题，先锁定两个核心差异：Prim 按顶点扩展，Kruskal 按边排序。再警惕绝对化表述（"一定""必须""只能"）——这类选项 99% 是陷阱。

B 项错在"一定完全相同"，当存在多条等权边时 MST 不唯一；C 项错在"必须使用邻接矩阵"，Kruskal 只需边集即可；D 项错在"只能处理有向图"，Prim 本质是处理无向图。

A 项正确：Prim 算法每次选取当前未访问顶点中距离最近的，适合稠密图（边数多时 O(V²) 或 O(E+V log V) 仍高效）；Kruskal 算法按边权排序后贪心加边，适合稀疏图（边数少时 O(E log E) 更优）。

B 项错误：最小生成树不唯一。当图中存在多条权重相同的边时，不同算法可能选择不同的边集，只要总权重相同即可。例如三角形图三条边权重均为 1，Prim 可能选两条，Kruskal 可能选另外两条。

C 项错误：Kruskal 算法只需维护边集和并查集，无需邻接矩阵。邻接矩阵适合 Prim 算法（便于快速找最小边），但 Kruskal 完全可以用边列表实现。

D 项错误：Prim 算法处理的是无向图。虽然可以扩展到有向图（如最小生成树 arborescence），但标准 Prim 算法定义在无向图上，且题目未说明是有向图。