最小生成樹算法有：Kruskal 算法和 Prim 算法。

首先明確關(guān)于圖的幾個(gè)概念：

• 連通圖：在無(wú)向圖中，若任意兩個(gè)頂點(diǎn) v_i 與 v_j 都有路徑相通，則稱該無(wú)向圖為連通圖。
• 強(qiáng)連通圖：在有向圖中，若任意兩個(gè)頂點(diǎn) v_i 與 v_j 都有路徑相通，則稱該有向圖為強(qiáng)連通圖。
• 連通網(wǎng)：在連通圖中，若圖的邊具有一定的意義，每一條邊都對(duì)應(yīng)著一個(gè)數(shù)，稱為權(quán)；權(quán)代表著連接兩個(gè)頂點(diǎn)的代價(jià)，稱這種連通圖叫做連通網(wǎng)。
• 生成樹：一個(gè)連通圖的生成樹是指一個(gè)連通子圖，它含有圖中全部 n 個(gè)頂點(diǎn)，但只有足以構(gòu)成一棵樹的 n-1 條邊。（一顆有 n 個(gè)頂點(diǎn)的生成樹有且僅有 n-1 條邊，如果生成樹中再添加一條邊，則必定成環(huán)。）
• 最小生成樹：在連通網(wǎng)的所有生成樹中，所有邊的代價(jià)和最小的生成樹，稱為最小生成樹。

Kruskal 算法

也可以稱為加邊法，初始最小生成樹邊數(shù)為 0，每迭代一次就選擇一條滿足條件的最小代價(jià)邊，加入到最小生成樹的邊集合里：

1. 把圖中的所有邊按代價(jià)從小到大排序；
2. 把 n 個(gè)頂點(diǎn)的圖看成獨(dú)立的 n 棵樹組成的森林；
3. 按權(quán)值從小到大選擇邊，所選的邊連接的兩個(gè)頂點(diǎn) u_i、v_i 應(yīng)屬于兩顆不同的樹，則成為最小生成樹的一條邊，并將這兩顆樹合并作為一顆樹。
4. 重復(fù)步驟 3，直到所有頂點(diǎn)都在一顆樹內(nèi)或者有 n-1 條邊為止。

Kruskal 算法

時(shí)間復(fù)雜度（邊數(shù) e）：O(e*log₂e)

Prim 算法

也可以稱為加點(diǎn)法，每次迭代選擇代價(jià)最小的邊對(duì)應(yīng)的點(diǎn)，加入到最小生成樹中。算法從某一個(gè)頂點(diǎn) s 開始，逐漸長(zhǎng)大覆蓋整個(gè)連通網(wǎng)的所有頂點(diǎn)。

1. 圖的所有頂點(diǎn)集合為 V；初始令集合 u = {s}, v = V?u;
2. 在兩個(gè)集合 u、v 能夠組成的邊中，選擇一條代價(jià)最小的邊 (u₀, v₀)，加入到最小生成樹中，并把 v₀ 并入到集合 u 中。
3. 重復(fù)上述步驟，直到最小生成樹有 n-1 條邊或者 n 個(gè)頂點(diǎn)為止。

Prim 算法

由于不斷向集合 u 中加點(diǎn)，所以最小代價(jià)邊必須同步更新；需要建立一個(gè)輔助數(shù)組 edge[]，用來(lái)維護(hù)集合 v 中每個(gè)頂點(diǎn)與集合 u 中最小代價(jià)邊信息。每次 u 新加入一個(gè)點(diǎn)后，掃描它能到的點(diǎn)，假設(shè)它到某個(gè)點(diǎn) i 的代價(jià)更小，就替換掉原先的 edge[i] 的代價(jià)值。

時(shí)間復(fù)雜度（節(jié)點(diǎn)數(shù) v，邊數(shù) e）：
鄰接矩陣 O(v²)
鄰接表 O(e*log₂v)