Kruskal

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

注：若無特殊說明，本文頂點與邊編號均從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];
}
void 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;
}

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