克魯斯卡演算法（Kruskal's algorithm）

克魯斯卡演算法建造最小生成樹的方式，就像一個節儉的承包商：總是買仍買得到最便宜的電纜，除非那會浪費。把所有電纜由便宜到昂貴排序，然後逐條往下看清單。若一條電纜連接網路中尚未相連的兩部分，就加入它；若它的兩端已在同一個連通塊中，就跳過，因為加它只會造出一個多餘的迴圈。當一切相連，就完成了。

逐步：把全部 E 條邊按權重遞增排序。維護一組連通分量，初始每個頂點自成一塊。掃過排序後的邊；對邊 (u, v)，若 u 與 v 在不同分量，就把邊加入樹並合併它們的分量；若已在同一分量，就丟棄它。加滿 V-1 條邊後停止。為何正確？每條被接受的邊都是跨越它所連兩個分量之間切割的最便宜邊（每條更便宜的邊都已掃過，本會更早合併那些分量），故切割性質說它安全。每條被拒絕的邊都是它會封閉的那個環上最重的，故環性質說它被安全略過。快速的分量測試是並查集；有了它，執行時間由排序主導：O(E log E) = O(E log V)。

克魯斯卡在稀疏圖上、以及邊已排序好或排序成本低時最出色。它是一個可證明正確的貪婪演算法的教科書範例——證明不是揮手帶過，而是切割性質與環性質的直接應用（更深層地說，是擬陣理論，圖擬陣正是 MST 這個情形）。一個值得陳述的效率提醒：並查集資料結構正是讓「這兩個頂點已相連嗎？」的檢查接近 O(1) 的關鍵；天真的連通性檢查會使克魯斯卡遠慢於它 O(E log E) 的標題。