Kruskal算法的时间复杂度为O(ElogE)E为边数
Kruskal算法是基于贪心的思想得到的。
首先我们把所有的边按照权值先从小到大排列，接着按照顺序选取每条边，
如果这条边的两个端点不属于同一集合，那么就将它们合并，直到所有的点都属于同一个集合为止。
至于怎么合并到一个集合，那么这里我们就可以用到一个工具——-并查集
换而言之，Kruskal算法就是基于并查集的贪心算法
即：
输入： 图G
输出： 图G的最小生成树
具体流程：
(1)将图G看做一个森林，每个顶点为一棵独立的树
(2)将所有的边加入集合S，即一开始S = E
(3)从S中拿出一条最短的边(u,v)，如果(u,v)不在同一棵树内，则连接u,v合并这两棵树，同时将(u,v)加入生成树的边集E’
(4)重复(3)直到所有点属于同一棵树，边集E’就是一棵最小生成树
1 int n,m,ans; 2 int f[5005]; 3 struct bian{ 4 int x,y,z; 5 }a[200009]; 6 bool cmp(bian x,bian y){return x.z<y.z;} 7 int F(int x) 8 { 9 if(x!=f[x]) return f[x]=F(f[x]); 10 return x; 11 } 12 int main() 13 { 14 scanf("%d%d",&n,&m); 15 for(int i=1;i<=n;i++)f[i]=i; 16 for(int i=1;i<=m;i++) 17 scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); 18 sort(a+1,a+m+1,cmp); 19 for(int i=1,fx,fy;i<=m;i++) 20 { 21 fx=F(a[i].x);fy=F(a[i].y); 22 if(fx!=fy) 23 { 24 f[fx]=fy; 25 ans+=a[i].z; 26 } 27 } 28 cout<<ans; 29 return 0; 30 }
原文：https://www.cnblogs.com/adelalove/p/11666618.html
