#include <cstdlib>
#include <iostream>
using namespace std;
#define MAXN 1000
#define NUM 1000*1000
#define inf 1<<30 //31 is overflowing
int P[MAXN];
int rank[MAXN];
void Make_set(int x)
{
P[x] = x;
rank[x] = 0; //合并两集合的一个启发函数值
}
int Find_set(int x)
{
if(x != P[x]) P[x] = Find_set(P[x]);
return P[x];
}
void Link_set(int x,int y)
{
if(rank[x] > rank[y]) P[y] = x;
else P[x] = y;
if(rank[x] == rank[y]) rank[y]++;
}
void Union_set(int x,int y)
{
Link_set(Find_set(x),Find_set(y));
}
/////基于并查集的求最小生成树的Kruskal算法的实现
////if (u,v) is not exist,G[u][v] = inf
////if u has been added in set of the smallest tree,then G[u][u] = 1;
int e[MAXN][MAXN];
struct Tree{
int u;
int v;
int value;
};
Tree tree[NUM];
int count_n = 0;
void st_Kruskal(int n)
{
int i = 0,j = 0;
for(i = 0;i < n;i++)
{
Make_set(i);
}
int u = 0,v = 0;
count_n = 0;
while(1)
{
int min = inf;
for(i = 0;i < n;i++)
{
for(j = 0;j < n;j++)
{
if(i != j && e[i][j] < min)
{
min = e[i][j];
u = i,v = j;
}
}
}
if(min == inf) break;
if(Find_set(u) != Find_set(v))
{
tree[count_n].u = u;
tree[count_n].v = v;
tree[count_n].value = e[u][v];
Union_set(u,v);
e[u][u] = e[v][v] = 1;
count_n++;
}
e[u][v] = inf;
}
}
int main()
{
int n = 0,i = 0,j = 0;
while(cin>>n)
{
for(i = 0;i < n;i++)
{
for(j = 0;j < n;j++)
{
cin>>e[i][j];
if(e[i][j] == -1) e[i][j] = inf;
}
}
st_Kruskal(n);
for(i = 0;i < count_n;i++)
{
cout<<tree[i].u<<" "<<tree[i].v<<" "<<tree[i].value<<endl;
}
}
return 0;
}
test:
6
0 6 2 -1 -1 -1
6 0 1 11 -1 -1
2 1 0 9 13 -1
-1 11 9 0 3 4
-1 -1 13 3 0 4
-1 -1 -1 4 4 0
result:
1 2 1
0 2 2
3 4 3
3 5 4
2 3 9
bingchaji_kruskal.rar_并查集
版权申诉
27 浏览量
2022-09-22
17:52:47
上传
评论
收藏 1KB RAR 举报
JaniceLu
- 粉丝: 78
- 资源: 1万+
最新资源
- MyBatis动态SQL是一种强大的特性,它允许我们在SQL语句中根据条件动态地添加或删除某些部分,从而实现更加灵活和高效的数据
- MyBatis动态SQL是一种强大的特性,它允许我们在SQL语句中根据条件动态地添加或删除某些部分,从而实现更加灵活和高效的数据
- MyBatis动态SQL是一种强大的特性,它允许我们在SQL语句中根据条件动态地添加或删除某些部分,从而实现更加灵活和高效的数据
- MyBatis动态SQL是一种强大的特性,它允许我们在SQL语句中根据条件动态地添加或删除某些部分,从而实现更加灵活和高效的数据
- 文件批量改名神器10.0一款简单易用的批量文件重命名工具(已注册PRO版本).rar
- MyBatis动态SQL是一种强大的特性,它允许我们在SQL语句中根据条件动态地添加或删除某些部分,从而实现更加灵活和高效的数据
- MyBatis动态SQL是一种强大的特性,它允许我们在SQL语句中根据条件动态地添加或删除某些部分,从而实现更加灵活和高效的数据
- MyBatis动态SQL是一种强大的特性,它允许我们在SQL语句中根据条件动态地添加或删除某些部分,从而实现更加灵活和高效的数据
- MyBatis动态SQL是一种强大的特性,它允许我们在SQL语句中根据条件动态地添加或删除某些部分,从而实现更加灵活和高效的数据
- MyBatis动态SQL是一种强大的特性,它允许我们在SQL语句中根据条件动态地添加或删除某些部分,从而实现更加灵活和高效的数据
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈