第1题
使用Prim(普里姆)算法求带权连通图的最小(代价)生成树(MST)。请回答下列问题。
（1）对下列图G，从顶点A开始求G的MST，依次给出按算法选出的边。
（2）图G的MST是唯一的吗？
（3）对任意的带权连通图，满足什么条件时，其MST是唯一的？
答：
（1）Prim算法属于贪心策略。算法从一个任意的顶点开始，一直长大到覆盖图中所有顶点为止。算法每一步在连接树集合S中顶点和其他顶点的边中，选择一条使得树的总权重增加最小的边加入集合S。当算法终止时，S就是最小生成树。
①S中顶点为A，候选边为(A,D)、(A,B)、(A,E)，选择(A,D)加入S。
②S中顶点为A、D，候选边为(A,B)、(A,E)、(D,E)、(C,D)，选择(D,E)，加入S。
③S中顶点为A、D、E，候选边为(A,B)、(C,D)、(C,E)，选择(C,E)加入S。
④S中顶点为A、D、E、C，候选边为(A,B)、(B,C)，选择(B,C)加入S。
⑤S就是最小生成树。
依次选出的边为：
(A，D),(D，E),(C，E),(B，C) （4分）
（2）图G的MST是唯一的。（2分）第一小题的最小生成树包括了图中权值最小的四条边，其他边都比这四条边大，所以此图的MST唯一。
（3）当带权连通图的任意一个环中所包含的边的权值均不相同时，其MST是唯一的。