這篇文章由 最小生成樹-Prim算法和Kruskal算法 整理而來, 感謝這篇文章的作者

Prime算法

1. 概述

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

2. 算法簡(jiǎn)單描述

1. 輸入：一個(gè)加權(quán)連通圖，其中頂點(diǎn)集合為 V，邊集合為 E；

2. 初始化：V_new = {x}，其中 x 為集合 V 中的任一節(jié)點(diǎn)（起始點(diǎn)），E_new = {},為空；

3. 重復(fù)下列操作，直到 V_new = V：

   1. 在集合 E 中選取權(quán)值最小的邊 <u, v>，其中 u 為集合 V_new 中的元素，而v不在 V_new 集合當(dāng)中，并且 v∈V（如果存在有多條滿足前述條件即具有相同權(quán)值的邊，則可任意選取其中之一）；

   2. 將v加入集合 V_new中，將 <u, v> 邊加入集合 E_new 中；

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

下面對(duì)算法的圖例描述

3. 簡(jiǎn)單證明prim算法

反證法：假設(shè)prim生成的不是最小生成樹

1. 設(shè)prime生成的樹為 G₀

2. 假設(shè)存在 G_min 使得cost(G_min) < cost(G₀) 則在 G_min 中存在 <u,v> 不屬于G₀

3. 將<u,v>加入 G₀ 中可得一個(gè)環(huán)，且 <u,v> 不是該環(huán)的最長(zhǎng)邊(這是因?yàn)?<u,v> ∈ G_min)

4. 這與prime每次生成最短邊矛盾

5. 故假設(shè)不成立，命題得證.

4. 代碼實(shí)現(xiàn)

// to be done ...

5. 時(shí)間復(fù)雜度

Prime算法主要用于邊比較多, 點(diǎn)比較少的時(shí)候

這里記頂點(diǎn)數(shù)v，邊數(shù)e

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

Kruskal算法

1. 概覽

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

2. 算法簡(jiǎn)單描述

1. 記 Graph 中有v個(gè)頂點(diǎn)，e個(gè)邊

2. 新建圖 Graph_new，Graph_new中擁有原圖中相同的e個(gè)頂點(diǎn)，但沒有邊

3. 將原圖 Graph_new 中所有e個(gè)邊按權(quán)值從小到大排序

4. 循環(huán)：從權(quán)值最小的邊開始遍歷每條邊 直至圖 Graph_new 中所有的節(jié)點(diǎn)都在同一個(gè)連通分量中
   如果這條邊連接的兩個(gè)節(jié)點(diǎn)于圖 Graph_new 中不在同一個(gè)連通分量中
   添加這條邊到圖 Graph_new 中

圖例描述：

3. 簡(jiǎn)單證明Kruskal算法

對(duì)圖的頂點(diǎn)數(shù) n 做歸納，證明 Kruskal 算法對(duì)任意 n 階圖適用。

歸納基礎(chǔ)：

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

歸納過程：

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

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

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

由數(shù)學(xué)歸納法，Kruskal 算法得證。

4. 代碼實(shí)現(xiàn)

// to be done ...

5. 時(shí)間復(fù)雜度

Kruskal算法主要用于邊比較少, 點(diǎn)比較多的時(shí)候

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