prim算法证明

算法过程

本文只将证明；过程参见：https://blog.csdn.net/luoshixian099/article/details/51908175

算法证明

有用推论

九层之台，起于累土；为了证明prim算法，可以先将一些理论证明，然后再以此为基础证明prim。

论据1 最小生成树可能不只一种
论据2 树做为无环图，若树中任意两点u v没有直接连接边，u v连接成边后树则变成了有环图。证明 树的uv 有是连通的，再uv 直接相连后 u到v有两条路径，所以 成环
论据3 所有的最小生成树 都会包含至少一个 权重值最小的边。 证明 采用反证法： 如果最小生成树不包含权重最小的边，则将一个权重最小的边cd添加到树上变成有环图（依据论据2）。则此环中肯定至少一个边ab 大于 权重最小边cd，删除此边ab后，生成树总权值变小，如果这样那么 此树不是最小生成树。
论据4 每个权重最小的边都有至少一种最小生成树包含。证明 依据论据3 ，那么最小生成树一定至少一个 权重值最小的边。假设 最小权重边有 ab cd ，最小生成树包含ab ，添加 cd变成环，去除此环中的另一个最小边，生成新的最小生成树

算法证明

上述图片来源于算法过程指向的链接

先找到最小权重边，此边一定是某个最小生成树的边，根据上述论据一定存在过ac的最小生成树。 此时 ac 是一个图 bdef是一个图，又因为这个场景下必有最小生成树存在（根据论据4），选择cf作为 ac 与bdef一定在一个最小生成树之中。因为如果此场景下最小生成树不包含cf，将cf连接成环 cf的距离小于等于所有别的点到ac的距离，因此可以替换，替换相等权重的边，说明此场景存在多个最小生成树，但至少有一个过cf的最小生成树，替换的边权值更大则不是最小生成树,与假设矛盾。因此cf一定是一个最小生成树的边。以此类推 prim算法则最后产生的树就是一种最小生成树。