数据结构
2017-42
使用 Prim（普里姆）算法求带权连通图的最小（代价）生成树（MST）。请回答下列问题。
（1）对下列图 G，从顶点 A 开始求 G 的 MST，依次给出按算法选出的边。
（2）图 G 的 MST 是唯一的吗？
（3）对任意的带权连通图，满足什么条件时，其 MST 是唯一的？
答案
【答案】
（1）依次选出的边为：(A, D), (D, E), (C, E), (B, C)。
（2）是唯一的。
（3）当带权连通图中任意环的所有边权值均不相同时，其MST是唯一的。（或：当图中所有边的权值互不相同时，其MST是唯一的。）