请教prim算法正确性的证明

答案:1 悬赏:80

解决时间 2021-01-18 09:50

提问者网友：最美的风景
2021-01-17 23:55

请教prim算法正确性的证明

最佳答案

二级知识专家网友：神也偏爱
2021-01-18 01:24

为了减少不必要的麻烦，可以不妨设图中所有边的权重都不同，这样最小生成树是唯一的
然后直接用反证法就行了
如果Prim算法得到G，而最小生成树是T
设在生成G的过程中第一次产生的不在T中的边是e，而在G中去掉e得到的两个连通分支记为V1和V2，那么e连接了V1和V2

把e加入T之后会出现环，在这个环里面V1的顶点和V2的顶点至少还被另一条边f连接（否则T本身就不连通了），由Prim算法的贪心策略可知e比f权重低，那么在T里面把f换成e可得一个总权重更小的生成树，与T的最小性矛盾

（因为最小生成树的总权重的边的权重的连续函数，对于有权重重复出现的情况可以利用连续性取极限，这样即使最小生成树不唯一仍然可以保证Prim算法生成的树具有最小权重）

我要举报

如以上问答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！