请求验证Prim定理应用练习题的解答正确性

提交的解答 #

• 选中边序列：B-C, B-H, H-A, A-I, I-F, F-G, G-E, E-D
• 总代价：2+3+7+4+5+1+9+17 = 48

验证结论 #

结合Prim算法的执行规则（从任意起始顶点出发，每次选取连接已访问顶点集合与未访问顶点集合的最小权值边，直至所有顶点被纳入），针对题目中的9顶点无向带权图，逐步骤验证如下：

1. 从B出发，优先选取权值最小的邻边B-C（权值2），符合规则，此时已访问顶点：{B,C}
2. 从已访问集合中找连接未访问顶点的最小边，B-H（权值3）是当前最优选择，正确，已访问顶点：{B,C,H}
3. 此时可选的跨集合边中，H-A（权值7）比H-I（权值8）更小，选取H-A，正确，已访问顶点：{B,C,H,A}
4. 已访问集合连接未访问顶点的最小边为A-I（权值4），比A-F（权值10）更优，选取正确，已访问顶点：{B,C,H,A,I}
5. 跨集合的最小边为I-F（权值5），优于I-G（权值6），选取正确，已访问顶点：{B,C,H,A,I,F}
6. 此时最小跨集合边是F-G（权值1），这是当前全局最小的有效边，选取正确，已访问顶点：{B,C,H,A,I,F,G}
7. 跨集合的最小边为G-E（权值9），比F-E（权值15）更优，选取正确，已访问顶点：{B,C,H,A,I,F,G,E}
8. 最后仅剩顶点D，只能选取E-D（权值17），符合规则

总代价计算无误，你的解答完全符合Prim算法的执行逻辑，结果正确。

内容的提问来源于stack exchange，提问作者Student123