這個問題，以及它為何不是最短路徑
這整個階段我們都圍著一個加權圖的問題打轉——如何便宜地從一個起點抵達其他所有地方。最小生成樹問的是一個聽起來相似、實則真正不同的姊妹問題：給定一個連通、無向、每條邊都有權重的圖，挑出一組邊把「所有」頂點都連在一起，同時讓總權重盡可能地小。想像幾座必須共用同一個供水網的小鎮，而每條邊的權重是在兩鎮之間鋪管的成本。你不是想快速抵達某一座鎮；你是想用最少的總管線把每座鎮都接上。
答案是一棵樹，而這是被逼出來的、不是選出來的。要連接 n 個頂點至少需要 n-1 條邊，而恰好有 n-1 條邊的連通圖沒有環——它是一棵樹，稱為生成樹，因為它觸及（生成）了每一個頂點。任何多出來的邊都會閉合一個環，而一個環裡總有一條我們可以拿掉、卻仍保持連通的邊。所以連起所有東西最便宜的方式必然是無環的。這是 MST 與單源最短路徑分道揚鑣的第一處：在那裡輸出是一棵以某個起點為根的最短路徑樹，最佳化的是「從那個根算起」的距離；而在這裡沒有根、也沒有起點，我們最佳化的是一個全域的數字——所選邊權的總和。
兩條決定每條邊去留的事實
在任何演算法之前，先學會讓 MST 運轉的那兩條事實，因為它們合起來會告訴你：對每一條邊，拿它是否安全、丟它是否安全。先看切性質。一個「切」把頂點分成兩個非空的群組；若一條邊的兩個端點落在不同群組，就說它「橫跨」這個切。主張是：對任何一個切，橫跨它的最便宜那條邊都屬於某棵 MST。為什麼？假設某棵最小生成樹避開了那條最輕的橫跨邊 e，這棵樹仍然必須在某處橫跨這個切——就說是用一條較重的邊 f。把 f 換出、把 e 換入。兩者都連接這個切的兩側，所以結果仍是一棵生成樹，而且重量不會更大（e 不比 f 重）。這個交換正是教科書式的交換論證：它說明，拒絕那條最輕的橫跨邊從來沒有好處。
現在看它的鏡像，環性質：在任何一個環裡，「最重」的那條邊不屬於任何 MST（假設它是嚴格最重的）。論證就是把同一個交換倒著跑。若某棵 MST 含有那條最重的環邊，刪掉它會把樹斷成兩塊——但環的其餘部分仍然跨過那道斷口，所以環上某條別的、較輕的邊可以用更低的代價把兩塊重新接起來。環中最重的邊永遠是可丟棄的。把這兩條事實並排放好，你就有了一套完整的決策程序：切性質告訴你哪些邊可以安全地「加入」，環性質告訴你哪些邊可以安全地「拒絕」。每一個 MST 演算法，都只是套用這兩條規則的不同排程而已。
Kruskal：把邊排序，挑出便宜又安全的
Kruskal 演算法是把切性質從全域的角度來讀。先暫時忘掉結構，單純把每一條邊從最便宜到最貴排序。沿著這份清單往下走，一條邊「當且僅當」它接起了兩塊尚未連通的片段時才採用它；若兩個端點早已坐在同一塊片段裡，就跳過。你從 n 個孤零零的頂點（n 塊各自獨立的碎片）開始，當你接受了 n-1 條邊之後就以一棵樹收場。整個方法一句話就能裝下：貪婪地抓取那條不會製造出環的最便宜的邊。
- 為何每一條被接受的邊都安全：當你取用那條「接起兩塊不同碎片」的最便宜剩餘邊時，考慮一個把其中一塊碎片放在一側、其餘一切放在另一側的切。你正要加入的這條邊橫跨那個切，而既然你是按權重遞增掃描，它就是你尚未拒絕、且橫跨該切的最輕邊——切性質說它屬於某棵 MST。
- 為何每一條被跳過的邊都安全：若兩個端點早已連通，加入這條邊會閉合一個環，而因為你是按遞增順序掃描，這條邊就是那個環上最重的。環性質說它不屬於任何 MST。所以跳過它毫無損失。
- 唯一棘手的部分，是要「快速地、上百萬次地」測試『這兩個端點是否已在同一塊碎片裡？』。這正是並查集結構在做的事：find(x) 回傳 x 所在的碎片，union(x,y) 合併兩塊碎片。恰當一條邊兩端的 find 不同時就接受它，然後把它們 union 起來。
代價由排序主導：對 m 條邊是 O(m log m)，而既然 m 至多大約是 n^2，log m 就是 O(log n)，所以人們通常寫成 O(m log n)。相較之下並查集的工作幾乎是免費的——配上按秩合併與路徑壓縮，每次操作實際上是個微小的常數，所以那 2m 次 find/union 呼叫只多加 O(m * alpha(n))，其中 alpha 是反阿克曼函數，在實務上從不超過約 4。誠實的註腳：那個並查集代價是攤還的——它是整串操作序列上的平均，而非對每一次操作的保證。單獨一次 union 偶爾仍可能多做點工；這個界保證的是「總量」維持在近乎線性。
Prim：讓一棵樹向外生長，最便宜的邊優先
Prim 演算法套用的是完全相同的切性質，只是用一個會生長的固定切。任選一個起點，把它叫做「樹」。反覆加入那條「恰好一個端點在樹內、一個在樹外」的最便宜邊，把那個樹外頂點拉進來。這裡的切永遠是「已在樹內的頂點」對「尚未進來的頂點」，而你加入的那條邊，依其構造就是橫跨該切最輕的那條——每一步都因切性質而安全。經過 n-1 次這樣的加入，每個頂點都進來了，你就得到一棵 MST。如果這個形狀讓你覺得眼熟，那是應該的：它和Dijkstra是同一副向外生長、不斷擴張前緣的骨架。
但這份與 Dijkstra 的相似掩蓋了一個關鍵差異，而搞錯它是個經典的失誤。Dijkstra 用每個前緣頂點「離起點的距離」——整段累積的路徑長度——作為它的鍵值，因為它最小化的是離單一個根的距離。Prim 則用「連到當前樹的那條最便宜的單一邊」的權重，作為每個前緣頂點的鍵值，因為它最小化的是整組所選邊，而非任何路徑。同一具引擎，不同的鍵。把這兩者搞混，Prim 就找不到最小生成樹了。
key[v] = lightest edge from v into the current tree (Prim)
key[v] = best known distance from the source to v (Dijkstra)
same loop: pop the min-key frontier vertex, then relax
its neighbors' keys. Only the key formula differs.因為內層步驟總是想要最小的鍵值，Prim 跑在和 Dijkstra 相同的優先結構上。配上二元堆積，那 n 次取最小操作、以及至多 m 次的鍵值下調，每次花 O(log n)，總計 O(m log n)——和 Kruskal 一樣的頭條數字。實務上的分工是老樣子：用鄰接串列加堆積的 Prim 在稠密圖、以及邊隨頂點一起到來時很自然，而當邊已經排好序、或存在一份扁平清單裡時，Kruskal 很自然。兩者都正確；兩者都是 O(m log n)；依你手上的資料來選，而不是依「某一個普遍更快」的信念。
貪婪為何在此奏效——以及誠實的界線
值得停下來品味一個真正的驚奇：貪婪在這裡是「對的」工具，儘管它在許多其他地方都失敗。挑那條「在地最便宜的安全邊」、且永不回頭重新考慮，恰恰好給出全域最優解——沒有回溯、沒有事後懷疑。這很罕見。貪婪對區間排程和霍夫曼編碼給出最優解，卻對 0/1 背包問題徹底失敗，在那裡「在地最佳的物品比值」會把你帶偏。「看起來在地最佳」從來不是全域最優的證明。MST 之所以可信，不是因為貪婪「感覺對」，而是因為切性質與環性質「證明」了每個在地選擇都與某個全域最優解相容。
MST 之所以這麼乖，還有一個更深的理由，而它把整個貪婪的故事繫在一起。圖中「不含環的邊集合」（也就是這個圖的森林）構成一個叫做擬陣的結構，而擬陣貪婪定理說：按權重遞增順序挑元素，凡是能讓你留在結構內的都拿，你就保證得到最優解。Kruskal 字面上就是這個定理套用在圖擬陣上。所以Prim 與 Kruskal 的貪婪觀點既非巧合、也非走運撞上的規律——它是一條乾淨的通則的實例，那條通則精確地說出貪婪何時可信。
帶兩個誠實的提醒出門。第一，這兩個演算法都假設無向圖；有向的對應版本（最小「樹形圖」arborescence）需要一套不同、更精細的方法，所以別在有向圖上抓 Kruskal 或 Prim 來用。第二，那個 O(m log n) 數字是一個關於「規模增長」的漸進陳述——它藏起了常數、也假設輸入很大。正如這個階段更廣的提醒，漸進描述的是代價如何增長，而不是在某個特定大小下哪段程式碼勝出；對一個很小的圖，最樸素的實作可能贏過最聰明的那個。知道這個界，但在大小真的要緊時去實測。