prime演算法

㈠ [圖] 最小生成樹-Prime演算法和Kruskal演算法

普里姆演算法（Prim演算法），圖論中的一種演算法，可在加權連通圖里搜索最小生成樹。意即由此演算法搜索到的邊子集所構成的樹中，不但包括了連通圖里的所有頂點（英語：Vertex (graph theory)），且其所有邊的權值之和亦為最小。該演算法於1930年由捷克數學家沃伊捷赫·亞爾尼克（英語：Vojtěch Jarník）發現；並在1957年由美國計算機科學家羅伯特·普里姆（英語：Robert C. Prim）獨立發現；1959年，艾茲格·迪科斯徹再次發現了該演算法。因此，在某些場合，普里姆演算法又被稱為DJP演算法、亞爾尼克演算法或普里姆－亞爾尼克演算法。

4 .輸出：使用集合 V _new 和 E _new 來描述所得到的最小生成樹。

下面對演算法的圖例描述

反證法：假設prim生成的不是最小生成樹

這里記頂點數v，邊數e

鄰接矩陣:O(v ² )
鄰接表:O(e * log ₂ v)

Kruskal演算法是一種用來尋找最小生成樹的演算法，由Joseph Kruskal在1956年發表。用來解決同樣問題的還有 Prime 演算法和 Boruvka 演算法等。三種演算法都是貪婪演算法的應用。和 Boruvka 演算法不同的地方是，Kruskal 演算法在圖中存在相同權值的邊時也有效。

圖例描述：

對圖的頂點數 n 做歸納，證明 Kruskal 演算法對任意 n 階圖適用。

歸納基礎：

n = 1，顯然能夠找到最小生成樹。

歸納過程：

假設 Kruskal 演算法對 n ≤ k 階圖適用，那麼，在 k + 1 階圖 G 中，我們把最短邊的兩個端點 a 和 b 做一個合並操作，即把 u 與 v 合為一個點 v'，把原來接在 u 和 v 的邊都接到 v' 上去，這樣就能夠得到一個 k階圖 G'(u ,v 的合並是 k + 1 少一條邊)，G' 最小生成樹 T' 可以用Kruskal 演算法得到。

我們證明 T' + {<u,v>} 是 G 的最小生成樹。

用反證法，如果 T' + {<u,v>} 不是最小生成樹，最小生成樹是 T，即W(T) < W(T' + {<u,v>})。顯然 T 應該包含 <u,v>，否則，可以用<u,v> 加入到 T 中，形成一個環，刪除環上原有的任意一條邊，形成一棵更小權值的生成樹。而T - {<u,v>}，是 G' 的生成樹。所以 W(T-{<u,v>}) <= W(T')，也就是 W(T) <= W(T') + W(<u,v>) = W(T'+{<u,v>})，產生了矛盾。於是假設不成立，T' + {<u,v>}是 G 的最小生成樹，Kruskal 演算法對 k+1 階圖也適用。

由數學歸納法，Kruskal 演算法得證。

e * log ₂ e (e為圖中的邊數)