Kruskal

• 本質：貪心，對邊進行操作。
• 存儲結構：邊集數組。
• 適用對象：可為負權圖，可求最大生成樹。
• 核心思想：最短的邊一定在最小生成樹(MST)上，對最短的邊進行貪心。
• 算法流程：對全體邊集\(\set{E}\)由小到大排序。遍歷所有邊，每次添加使已選邊集不成環的邊，直到已選\(V-1\)條邊。可使用并查集判環，每次加邊前先判斷兩點是否同屬一個集合，每次加邊時將兩點合并到一個集合。
• 復雜度：\(O(E\log_2E)\)

注：若無特殊說明，本文頂點與邊編號均從0開始。

數據結構定義

using ll=long long;
ll n,m,s;//點數,邊數,源點
struct edge{
    int u,v,w;
}e[m];
bool cmp(edge a,edge b){
    return a.w<b.w;
}
int s[n];
int Find(int x){
    if(s[x]!=x) s[x]=find(s[x]);
    return s[x];
}
int init(){
    for(int i=0;i<n;i++) s[i]=i;
}

實現

int kruskal(){
    sort(e,e+m,cmp);
    init();
    int ans=0,cnt=0;
    for(int i=0;i<m;i++){
        if(cnt==n-1) break;
        int U=e[i].u,V=e[i].v,W=e[i].w;
        int u1=Find(U),u2=Find(V);
        if(u1==u2) continue;//成環,不選當前邊
        else{
            ans+=W;
            s[u1]=u2;//合并到一個集合
            cnt++;
        }
    }
    if(cnt==n-1) return ans;
    return -1;
}

若求最大生成樹，改為對邊集\(\set{E}\)由大到小排序即可。