證明演算法正確性

① 請教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 中全部元素合並排序了， 從雹旦念而證明了演算法的正確性。