---
tags: APCS
---

# Kruskal 演算法

graph G {
    splines="line"
    node[shape=circle]
    {rank=same;1,2}
    {rank=same;3,4,5,6}
    0 -- 1 [label=3]
    0 -- 2 [label=1]
    1 -- 3 [label=1]
    1 -- 5 [label=1]
    2 -- 5 [label=7]
    2 -- 6 [label=5]
    3 -- 4 [label=2]
    4 -- 5 [label=1]
}

//
// Minimum Cost Spanning Tree - Kruskal
//
//  依序挑選 n-1 條不會造成 loop 的最小邊
//
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <queue>

using namespace std;

//---------------------------------------------------------------------------
// 測試資料
//
// 第一行，一個整數 n 表示有幾個節點
// 剩下一直到結尾的每一行的 3 個整數都代表一條邊，格式為 v1 v2 w
//  v1 v2 代表線的兩個端點，
//  w 代表這條線的權重(或成本)
//
string input = "\
7\n\
0 1 3\n\
0 2 1\n\
1 3 1\n\
1 5 1\n\
2 5 7\n\
2 6 5\n\
3 4 2\n\
4 5 1\n";

// Kruskal 演算法主要以邊為考量，所以將邊的兩端都放在結構裡
struct Edge {
    int from, to, weight;
};

// 重載 < 運算子，定義如何比較兩個 Edge 變數
// priority_queue<Edge> 會自動調用這個運算子，將優先權高的排在前面
bool operator<(const Edge &e1, const Edge &e2)
{
    // weight 高的優先權較小
    return e1.weight > e2.weight;
}

// 用結構紀錄圖的組態
struct Graph {
    int n;
    vector<Edge>    edge;
};

// 以往上找 root 的方式找到群組的頭 (parent == 自己)
int group(vector<int> &parent, int n)
{
    for (; parent[n] != n; n = parent[n]) ;
    return n;
}

int mst_kruskal(Graph g)
{
    vector<int>     parent(g.n);        // 每個點的 parent，往上追到 root 來比對是否為同一個群組
    priority_queue<Edge>    pq;         // 挑選邊用的優先佇列，會依優先權高至低的順序自動排列元素
    int remain_edges = g.n - 1,         // 只要挑完 n-1 條邊就可以了
        min_cost = 0;
    
    for (int i = 0; i < g.n; i++)
        parent[i] = i;                  // 先將每個點的 parent 設為自己(每個點的群組頭就是自己)

    for (auto &e: g.edge) {             // 將圖裡所有的邊都丟進優先佇列中等待處理
        pq.push(e);
    }

    while (remain_edges > 0 && !pq.empty()) {
        auto e = pq.top(); pq.pop();        // 依次挑出優先權最高(成本最小)的邊
        int g1 = group(parent, e.from), 
            g2 = group(parent, e.to);
        
        if (g1 != g2) {             // 兩端不在同一群組的邊才可以挑，不然會 loop
            parent[g1] = g2;        // 合併群組(將群組的 parent 指向另一個群首就可以了)
            min_cost += e.weight;
            remain_edges--;
        }
    }
    return min_cost;
}

int main()
{
    stringstream    sin(input);
    Graph   G;
    int     a, b, r;

    sin >> G.n;
    while (sin >> a >> b >> r) {
        G.edge.push_back({a, b, r});
    }
    cout << mst_kruskal(G) << '\n';
    return 0;
}