圖
最小生成樹
給定一個連通的、帶權的無向圖，最小生成樹（MST）就是把所有頂點連成一體的最省辦法。設想你要鋪設電纜，讓鎮上每戶人家都接入同一個網路，而你希望電纜總長度最小。答案就是一棵 MST：它觸及每一個頂點，用的邊一根都不多，構成一棵樹（V 個頂點恰由 V-1 條邊相連、沒有環），且總權重盡可能小。
有兩種經典的貪婪演算法能求出它。Kruskal 演算法把所有邊從便宜到貴排序，只要某條邊不會造成環就把它加入，直到全部連通為止。Prim 演算法從一個起始頂點開始讓樹生長，反覆加入「能接到尚未在樹中的頂點」的最便宜那條邊。兩者都依賴同一個洞見：從「已建好的部分」跨向「其餘部分」的最小那條邊，總是可以安全地選取。
它們的開銷相近：Kruskal 約為 O(E log E)（主要花在給邊排序上），用優先佇列實作的 Prim 約為 O((V + E) log V)。注意 MST 最小化的是「連接總成本」，這和最短路徑是不同的目標——MST 一般並不是「讓每一對頂點各自取得最短距離」的那種路線。
sort(edges.begin(), edges.end()); // by weight
for (auto [w, u, v] : edges) {
if (find(u) != find(v)) { // no cycle
unite(u, v);
total += w; // edge in MST
}
}並查集能廉價地判斷兩個端點是否已經連通。
只有連通圖才有 MST；對非連通圖，得到的是最小生成森林，每個連通分量一棵樹。
又稱
另見