[图论]Kruskal

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}由大到小排序即可。