42.（8分）使用Prim（普里姆）算法求带权连通图的最小（代价）生成树（MST）。请回答下列问题。 （1）对下列图G，从顶点A开始求G的MST，依次给出按算法选出的边。 （2）图G的MST是唯一的吗? （3）对任意的带权连通图，满足什么条件时，其MST是唯一的?
【参考答案及解析】
（1）Prim算法属于贪心策略。算法从一个任意的顶点开始，一直长大到覆盖图中所有顶点为。算法每一一步在连接树集合 S中顶点和其他J顶点的边中，选择一条使得树的总权重增加最小的边加入集合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是唯一的。
正在整理中,欢迎在文下评论区提供答案解析,谢谢！
（1）Prim算法属于贪心策略。算法从一个任意的顶点开始，一直长大到覆盖图中所有顶点为。算法每一一步在连接树集合 S中顶点和其他J顶点的边中，选择一条使得树的总权重增加最小的边加入集合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是唯一的。
正在整理中,欢迎在文下评论区提供答案解析,谢谢！