Kruskal’s Algorithm

Kruskal’s Algorithm 是用來找最小生成樹的演算法
其尋找的方式是從不斷添加權重最小的邊，且如果添加後形成環就將其移除

在實作上，可以用 Union-Find 判斷會不會形成環

要點

需要一個一維陣列，裡面放邊權重、A 節點、B 節點
將其排序後遍歷，並且透過 Union-Find 檢查
如果兩者的祖先不相同則代表添加後不會形成環
添加後將兩節點 合併（Union）

實作

這邊是 Kruskal’s Algorithm 會用到的 Union-Find
詳細的解釋在 這裡

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> anc;

int Find(int x) {
    return (anc[x] == x ? x : anc[x] = Find(anc[x]));
}

bool Union(int a, int b) {
    anc[Find(b)] = Find(a);
}

int main() {
    int n;
    cin >> n;
    anc.resize(n);
    iota(anc.begin() , anc.end(), 0);
}

將邊的權重放在第一項，節點編號放在後面
並且透過 sort 依照邊的權重排序

1
2
3
vector<tuple<int, int, int>> g;
g.push_back({w, a, b});
sort(g.begin(), g.end());

之後遍歷該陣列，檢查 Find(a) != Find(b)
若條件成立，則添加此邊

1
2
3
4
5
6
for (auto [w, a, b] : g) {
    if (Find(a) != Find(b)) {
        ...... //依照問題需求動作
        Union(a, b);
    }
}

範例

題目：UVA 10034

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define WA() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())

vector<int> anc;


int Find(int x) {
    return (anc[x] == x ? x : anc[x] = Find(anc[x]));
}

bool Union(int a, int b) {
    a = Find(a), b = Find(b);
    if (a == b) return false;
    return anc[b] = a, true;
}

signed main() { WA();
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        anc.resize(n);
        iota(all(anc), 0);
        vector<pair<double, double>> v(n);
        vector<tuple<double, double, double>> g;
        for (auto &i : v) cin >> i.fi >> i.se;
        for (int i = 0; i+1 < n; i++) for (int j = i + 1; j < n; j++) {
                g.push_back({sqrt((v[j].fi-v[i].fi)*(v[j].fi-v[i].fi)+(v[j].se-v[i].se)*(v[j].se-v[i].se)), i, j});
        }
        sort(all(g));

        double ans = 0;
        for (auto &[dis, a, b] : g) if (Union(a, b)) ans += dis;

        cout << fixed << setprecision(2) << ans << '\n';
        if (t) cout << '\n';
    }
}

題目：UVA 1208

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
// 我不會處理這題測資的輸入 :(
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define WA() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define int long long

vector<int> anc;

int Find(int x) {
    return (anc[x] == x ? x : anc[x] = Find(anc[x]));
}

bool Union(int a, int b) {
    a = Find(a), b = Find(b);
    if (a == b) return false;
    return anc[b] = a, true;
}

signed main() { WA();
    int t;
    cin >> t;
    for (int c = 1; c <= t; c++) {
        int n;
        cin >> n;
        cin.ignore();
        vector<vector<int>> v(n);
        for (int i = 0; i < n; i++) {
            string s;
            int tmp;
            getline(cin, s);
            for (auto &c : s) if (!isalnum(c)) c = ' ';
            stringstream ss(s);
            while (ss >> tmp) v[i].push_back(tmp); 
        }

        vector<tuple<int, int, int>> g;
        for (int i = 0; i+1 < n; i++) for (int j = i+1; j < n; j++) {
            if (v[i][j]) g.push_back({v[i][j], i, j});
        }

        sort(all(g));

        anc.resize(n);
        iota(all(anc), 0);
        cout << "Case " << c << ":\n";
        for (auto &[w, a, b] : g) if (Union(a, b)) printf("%c-%c %d\n", a+'A', b+'B', w);
    }
}