- 【用途】從一張有權無向圖中 (N個頂點)，選出一些邊，形成一棵包含所有頂點的樹，條件是所選的邊的權值總和要最小。
- 【原理】
- 利用並查集的特性，當選擇一條邊後，對應兩個頂點的集合即可合併成同一個集合。
- 當最後只剩下一個集合或已經使用N-1條邊時，便構成一棵樹。
- 【實作】
- 排序：先把所有邊依照權值由小到大排序。
- 疊代：依序疊代每條邊，若該邊的兩個頂點屬於不同集合，即採用這條邊，並合併兩點所屬集合。
- Union-Find algorithm同並查集。
- 最後把所有被選到的邊的權值加起來，即為構成最小生成樹的成本。
- 【範例】ZeroJudge d909: 公路局長好煩惱！？
//定義一結構存放每一條邊的資料
//x, y為兩個頂點，c為這條邊的權值
struct Edge {
int x, y;
int cost;
};
vector <Edge> v; //存放邊的資料
int todo = n-1; //n個節點的樹，有n-1條邊
int mst_cost = 0;
//針對cost排序，由小排到大
sort(v.begin(), v.end(), cmp);
//disjoint sets, Union-Find algorithm
for (Edge edge:v){
int g1 = find(edge.x);
int g2 = find(edge.y);
if (g1 == g2) continue;
else {
p[g2] = g1;
todo -= 1;
mst_cost += edge.cost;
}
}
Post Views (since April 2021) : 2,311