Prim算法的正确性证明
Prim算法的正确性证明
令无向图为G=(V,E)G = ( V, E)G=(V,E)，其中V={v1,v2,...,vn}V=\\left \\{ v_{1} ,v_{2},...,v_{n} \\right \\}V={v1,v2,...,vn}，其生成树为G′=(V,E′)G^{'}=\\left ( V,E^{'} \\right )G′=(V,E′)，其中E′={et1,et2,...,etn−1}E^{'}=\\left \\{e _{t_{1}},e _{t_{2}},...,e _{t_{n-1}} \\right \\}E′={et1,et2,...,etn−1}，且G′G^{'}G′为联通无环图。
1. 贪心选择性质
不失一般性，令起始节点为v1v_1v1，贪心选择测略就是找到与v1v_1v1连接边最短的节点，以及相应的边，记该点为vav_ava，相应的边为eb=(v1,va)e_b=(v_1, v_a)eb=(v1,va)。现证明包括在某个最优解中。
令G′G^{'}G′为一棵最小生成树，其中不包括ebe_beb，则将ebe_beb加入中，形成一个环，不考虑该环之外的节点，每个节点的度刚好为2，令该环中与v1v_1v1相关的另一条边为ece_cec，则删除后，获得另外一棵生成树G′′G^{''}G′′。由于w(eb)<=w(ec)w(e_b) <= w(e_c)w(eb)<=w(ec),G′′G^{''}G′′也一定为一棵最小生成树。
2. 最优子结构
不失一般性，令通过prim算法得到的某棵最小生成树GGG中，节点度数最小的两个节点对应的字符为aaa和bbb，将两个节点进行合并操作得到一个新的节点，对应字符记为ccc，同时新的最小生成树为G1G_1G1，需要证明G1G_1G1为最小生成树。
假设其最小生成树不是G1G_1G1，则另外一棵最小生成树G2G_2G2, s.t. W(G2)<W(G1)W(G_2) < W(G_1)W(G2)<W(G1)，将的ccc节点重新扩展成为aaa，bbb两个节点，且以边e=(a,b)e = (a, b)e=(a,b)相连，易得此使最小生成树无环，且是一个有n−1n-1n−1条边的连通图，获得G3G_3G3,可以得到：G3=G2+w(e)<G1+w(e)=GG_3 = G_2 + w(e) < G_1 + w(e) = GG3=G2+w(e)<G1+w(e)=G
这与假设中的G为最小生成树的假设矛盾，因此得证。