【筆記】Minimum Spanning Tree (MST) 最小生成樹

  • 【用途】從一張有權無向圖中 (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;
    }
}
分享本文 Share with friends