Prim算法的正确性证明

令无向图为$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算法得到的某棵最小生成树$G$中，节点度数最小的两个节点对应的字符为$a$和$b$，将两个节点进行合并操作得到一个新的节点，对应字符记为$c$，同时新的最小生成树为G1G_1G1​，需要证明G1G_1G1​为最小生成树。

假设其最小生成树不是G1G_1G1​，则另外一棵最小生成树G2G_2G2​, s.t. W(G2)<W(G1)W(G_2) < W(G_1)W(G2​)<W(G1​)，将的$c$节点重新扩展成为$a$，$b$两个节点，且以边$e=(a,b)$相连，易得此使最小生成树无环，且是一个有$n-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为最小生成树的假设矛盾，因此得证。