- 【用途】從一張有權無向圖中 (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