# 最小生成樹-Kruskal介紹、證明與實作

## 最小生成樹介紹
> 給定一連通帶權無向圖G(V,E)，有n條邊，一個生成樹T就是一個有n-1條邊的連通子圖，求出邊權和最小的T。

對於此問題，經典的演算法有Kruskal與Prim兩種演算法，將會以兩篇文章來介紹。

## Kruskal演算法概述
Kruskal演算法的步驟如下：
1. 將所有邊由小到大排序為$e_1,e_2,...,e_m$。
2. 令$T = \phi$。
3. 對於i從1到m，若$T\cup\{e_i\}$沒有環，將$e_i$加入$T$中

最後的T即是最小生成樹，Kruskal的概念很好理解，即是貪心地拿到不成環的最小權重邊。然而，這個演算法有兩個問題：首先，要如何判斷加了這條邊會成環，再來，為什麼這樣加邊一定是最好的?難道不會被一個小的邊而卡到其他邊嗎？

## 正確性證明
首先我們先解決第二個問題，為了證明演算法的正確性，我們需要引出生成樹的一個性質：
> 性質
> 對於兩個生成樹$T_1與T_2和一條e \in T_1 \backslash
T_2$，存在$e_2 \in T_2 \backslash T_1$使得$(T_2\backslash \{e_2\})\cup \{e_1\}$依然是生成樹。

白話來說，從$T_1$拿出一條邊加入$T_2$後，一定可以在$T_2$拔掉一條邊使得$T_2$還是生成樹。在加入$e_1$後，$T_2$會形成一個環，此時移除環上任一條邊都可以讓$T_2$有n-1條邊連通，代表$T_2$也是樹了。

接著我們就可以開始證明Kruskal演算法的正確性了：

令Kruskal演算法找到的生成樹為$T$，而最小生成樹為$T^*$，如果有多個最佳解，令$T^*$為與$T$交集最大的一個。如果$T=T^*$就結束了，否則，令$e_i$是編號最小且只出現在$T$的邊，根據上面的性質，存在$e_j \in T^* \backslash T$使得$T^*$把$e_j$換出去再把$e_i$放進來仍是一棵生成樹。

假如$i<j$，那$e_i$的權重$\leq e_j$的權重。由於$T^*$是最小生成樹，這樣做出來的$T' = (T^* \backslash\{e_j\})\cup\{e_i\}$的權重會跟$T^*$一樣(或更小)，但是與$T$的交集比$T^*$大，矛盾。

假如$i>j$，由於比$j$前面的邊都在$T$與$T^*$中，根據Kruskal演算法的特性，在遇到$e_j$時就會把$e_j$加入$T$中了，矛盾。

故得證$T=T^*$

## Kruskal 演算法的實作
接下來我們要解決第一個問題：如何判斷加入邊後會成環？加入邊後會成環用另一個角度思考，就是加入邊的兩端點在加邊前已經連通，所以如果我們能維護點的連通性，就能判斷加邊後是否會成環了。

我們在維護聯通性時，要支援以下操作：
* 查詢兩個點是否連通
* 將兩個連通塊合併(加邊)

這樣的問題，可以使用並查集來有效率地解決，關於並查集的介紹，請參考[這份講義](https://hackmd.io/@CLKO/rkRVS_o-4?type=view)

在加邊以前，我們先檢查兩端點是否已經連通，如果尚未連通，則加入此邊，並將兩個連通塊合併。

程式碼如下：

#include<bits/stdc++.h>
#define ll long long
#define MOD 1000000007
#define fastio ios::sync_with_stdio();cin.tie();

using namespace std;
const int INF_INT = 2147483647;
const ll INF_LL = 9223372036854775807LL;
int gcd(int a,int b){return ((b==0)?a:gcd(b,a%b));}
int lcm(int a,int b){return a*b/gcd(a,b);}


struct edge{

    int a,b;
    ll w;

    
};

bool cmp(edge a,edge b){
    return a.w<b.w;
}


vector<int> Dis;//並查集


int search(int a){
    if(Dis[a] == a)return a;
    else{
        Dis[a] = search(Dis[a]);
        return Dis[a];
    }
}
void Union(int a,int b){
    Dis[search(a)] = search(b);
}


void solve(){

    int n,m;
    cin>>n>>m;

    vector<edge> E;

    for(int i=0;i<m;i++){
        edge tmp;
        cin>>tmp.a>>tmp.b>>tmp.w;
        E.push_back(tmp);
    }

    sort(E.begin(),E.end(),cmp);//將邊由小排到大

    Dis.resize(n+1);
    for(int i=1;i<=n;i++)Dis[i] = i;//並查集初始化


    ll cnt = 0;

    int tmp = 0;//用來數加了幾個邊

    for(int i=0;i<m&&tmp!=n-1;i++){

        if(search(E[i].a)!=search(E[i].b)){//確認是否不連通
            tmp++;
            Union(E[i].a,E[i].b);//合併連通塊
            cnt+=E[i].w;
        }

    }
    cout<<cnt<<endl;//輸出最小生成樹的邊權和




    
    
}
int main(){
    fastio;
    solve();
}

## 複雜度分析

排序邊為$O(\mid E \mid log \mid E \mid)$，並查集查詢與更新均攤後接近$O(1)$，執行$O(\mid E\mid)$次。整個演算法的複雜度為$O(\mid E \mid log \mid E \mid)$。

在完全圖中，Prim的複雜度$O(n^2)$是比Kruskal的$O(n^2 log n)$還要好的。

## 參考資料
IOICAMP2021講義
https://hackmd.io/@CLKO/rkRVS_o-4?type=view