给定一个无向图,求其最小生成树
在无向图中,连通且不含环的图称为树。给定无向图(G=(V,E)),连接(G)中所有点,且边集是(E)的子集称为(G)的生成树。 ((Spanning Tree))。
那么对于(G)的所有生成树,其中边权值最小的就是无向图(G)的最小生成树。
这里使用的是(Kruskal)。克鲁斯卡尔算法代码复杂度较低,的时间复杂度是以边数来决定的。 而(我还不会的)(Prim)算法是以点为核心的。
核心 贪心+并查集……将边按权值从小到大排序,如果说第(i)条边的两个节点(u[i])和(v[i])不在【未完成生成树中的】同一个连通分量中,那么它一定属于最小生成树。
然后就将这两个点所在的连通分量合并,这条边加入生成树
正确性易证
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
#define MAXM 200005<<1
#define MAXN 5005
struct edge
{
int u,v,w;
}e[MAXM];
bool cmp(const edge x,const edge y)
{
return x.w<y.w;
}
int f[MAXN],n,m;
int found(int q)
{
if (f[q]==q) return q;
return f[q]=found(f[q]);
}
inline void init()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
f[i]=i;
}
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
}
sort(e+1,e+m+1,cmp);
}
inline int lasmain()
{
int ans=0;
for (int i=1;i<=m;i++)
{
int fx=found(e[i].u),fy=found(e[i].v);
if (fx!=fy)
{
ans+=e[i].w;
f[fx]=fy;
}
}
return ans;
}
int main()
{
init();
printf("%d",lasmain());
return 0;
}