最小生成树
\(By：Soroak\)
- 定义：一个有 \(n\) 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 \(n\) 个结点，并且有保持图连通的最少的边。最小生成树可以用 \(kruskal\) 算法或 \(Prim\) 算法求出。
Kruskal
定义: \(Kruskal\) 是基于贪心的思想得到的。
首先我们把所有的边按照权值先从小到大排列，接着按照顺序选取每条边，如果这条边的两个端点不属于同一集合，那么就将它们合并，直到所有的点都属于同一个集合为止。看到这里，我们不难想到另外一个算法——并查集，说白了， \(Kruskal\) 算法就是基于并查集的贪心算法。- 时间复杂度: \(O(MlogM)\) \(M\) 是图中边的总数。
基本思想: \(Kruskal\) 是以边为主导地位，始终选择当前可用的最小边权的边，每次选择边权最小的边连接的时候，要判断两个端点之间有没有联通。
代码如下：（感谢gyh大佬的“赞助”）
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct edge
{
int u,v,w;//分存每一条边前,后坐标与权值
}a[3000010];
int n,m,num;//存边的数量
int pre[1000010];//存并查集中的祖先
bool cmp(edge aa,edge bb)
{
return aa.w<bb.w;
}//结构体sort排序必须自定义排序函数
void add(int u,int v,int w)
{
a[++num].u=u;
a[num].v=v;
a[num].w=w;
}
int find(int x)
{
return pre[x]==x?x:pre[x]=find(pre[x]);
}
void join(int x,int y)//并集
{
int r1=find(x),r2=find(y);
if(r1!=r2)
{
pre[r1]=r2;
}
}
signed main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
pre[i]=i;//重置先祖
}
for(int j=1;j<=m;j++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);//输入各边权值
add(u,v,w);
}
sort(a+1,a+num+1,cmp);
int sum=0;
for(int i=1,tot=0;i<=num&&tot!=n;i++)
{
if(find(a[i].u)==find(a[i].v))
{
continue;
}
join(a[i].u,a[i].v);
++tot;
sum+=a[i].w;
}
printf("%d",sum);//输出
return 0;
}