文章
5
粉丝
409
获赞
7
访问
52.3k
Kruscal是采用贪心思想,基于加边策略的MST算法。
用并查集管理顶点之间的连通性。
操作两步走:
1.对所有边按照权重升序进行排序
2.从权重最小的边开始,遍历所有的边,只要两个顶点没有连通,则添加这条边,同时统计权重
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define N 5005 //点
#define M 200005 //边
struct Edge{
int s;//起点
int e;//终点
int w;//权重
Edge(int si,int ei,int wi)
{
s=si;e=ei;w=wi;
}
bool operator< (const Edge& b) const{
return w<b.w;
}
};
struct Union{
int par[N];
int count;//集合个数
Union(int n)
{
for(int i=0;i<n;i++)
par[i]=-1;
count = n;
}
bool unite(int a,int b)
{
int ra = find(a);
int rb = find(b);
if(ra!=rb)
{
par[ra]=rb;
count--;
return true;
}
return false;
}
int find(int x)
{
if(par[x]==-1) return x;
else{
int root = find(par[x]);
par[x] = root;//路径压缩
return root;
}
}
};
vector<Edge> edges;
int main()
{
//读入边
int n,m;
scanf("%...
登录后发布评论
赞一个,kruskal