演算法知識 - Kruskal Algorithm

Kruskal Algorithm 介紹

主要是在一張圖中組合成一顆樹，其中每一條邊都有一個成本，且要求這顆樹的總和成本必須要是最小。
時間複雜度為 \(O(E \log E)\)

主要用來找出一張圖中的最小生成樹、最大生成樹

Kruskal Algorithm 證明與實作

證明

• 不難理解，我們可以知道從最小的邊開始組合成的一棵樹一定是總成本最小的
• 但是有可能再拿最小的邊時，發現這個邊與其他邊有衝突
  • 舉例：(1,3) 成本 2，(1,3) 成本 3，(1,4) 成本 10
  • 如果從最小的拿，那我們必須避免使用 (1,3) 成本 3
• 因此我們使用並查集，只要拿最小的邊，並且判斷這兩個邊的節點是否在同個 set 裡，如果有那就要捨棄掉，因為已經有更小的邊連接他們了。
  • 可能會有疑問，那有沒有可能這個生成樹是多顆生成樹，其實並沒有被連接
  • 只要保證他是一張圖，那麼圖中的每一個點我們會遍地經歷過，就勢必會經過連接點，此時若沒有更小的邊，那我們就會加入他，並透過 disjoint set 來合併這兩個生成樹
  • 因此，我們必須確認他是一張圖，而不是兩張圖，因為如果是兩張分裂的圖那麼 set 很高機率會變拆成兩組。
  • 此時就變成有兩顆生成樹
• 不斷連接，只到將所有的邊都使用過。

原理

• 使用 disjoint set 判斷每一個節點現在屬於哪一個生成樹
• 再來將每一個 edge 放入 vector，並 sort
• 使用 for loop，確認邊的節點是否有在同個 set
  • 如果都在同個 set，則不需要這個 edge
  • 如果不同，則加入此 edge，並記錄

Kruskal Algorithm 實作

不廢話，直接上來

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 200020
#define int long long
using namespace std;
int n, m;
int a, b, c;
int p[MAXN];

struct edge{
    int u, v, c; //u,v 分別為邊的節點， c 是成本
    
    edge(): u(0), v(0), c(0) {}
    edge(int u, int v, int c): u(u), v(v), c(c) {}
    bool operator < (const edge& other) const{
        return c < other.c;
    }
};
vector<edge> node;
vector<edge> MST; //最小生成樹

int find_root(int x){
    //cout << "find_root " << x << "\n";
    if(p[x] != x) return p[x] = find_root(p[x]);
    return x;
}

void kruskal(){
    node.clear();
    MST.clear();
    for(int i = 0; i < n; i++) p[i] = i; //init disjoint set

    for(int i = 0; i < m; i++){
        cin >> a >> b >> c; //輸入邊、成本
        node.push_back({a,b,c});
    }
    sort(node.begin(), node.end()); //排序，這邊排序方式為遞增

    for(edge it: node){
        //cout << it.u << " " << it.v << " " << it.c << "\n";
        //cout << p[3] << " " << p[4] << "\n";
        int pu = find_root(it.u); //判斷邊的節點們是否都在同個 set 
        int pv = find_root(it.v);
        if(pu != pv){ //分析 3-1
                p[pv] = pu;
                MST.push_back(it); //記錄此 edge
        }
    }

    for(edge it: MST){
        cout << it.u << " " << it.v << " " << it.c << "\n"; //輸出所有邊
    }


}

參考連結

Minimum Spanning Tree: Kruskal’s Algorithm by 師大演算法

心得

專家們、科學家們研究出來的成果希望我都可以把他們吸收進去，並且運用在我未來的道路上。