证明算法正确性

① 请教prim算法正确性的证明

为了减少不必要的麻烦，可以不妨设图中所有边的权重都不同，这样最小生成树是唯一的
然后直接用反证法就行了
如果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算法生成的树具有最小权重）

② 算法的正确性证明方法一: 循环不变量

在之前的一篇文章里写到 算法的正确性 的概念以及它的作用，下面就来写写循环不变量在算法的正确性证明中的用法。

在使用循环的算法里，可以通过循环不变量证明其正确性。
所谓循环不变量是指一种在整个循环过程中保持不变的性质，它必须在以下3种情况下均保持不变，且该性质源困在循环终止后能证明算法的正确性。

接下来就 归并排序（Merge sort） 中的 merge 函数来说明一下循环不变量

先解释一下这个函数的作用，sld 和 srd 为已排序数组，大小分别为 lc 和 rc，循环 tc (lc + rc) 次把它们的元素进行比较并复制到新分配的数组 md 中，那要怎么证明这个算法的正确性呢。

让我们先设定循环不变量，然后看8-18行的循环能否在以上3种情况都满足这个循环不变量。

结束时循环不变量给了我们一个有用信息，此迟氏时 md 已经把 sld 和 srd 中全部元素合并排序了， 从雹旦念而证明了算法的正确性。