C语言数据结构 克鲁斯卡尔算法求无向网的最小生成树.输入:输入数据第一行为两个正整数n和m,分别表示顶点数和边数.后面紧跟m行数据,每行数据是一条边的信息,包括三个数字,分别表示该
来源:学生作业帮助网 编辑:作业帮 时间:2024/08/01 23:46:23
![C语言数据结构 克鲁斯卡尔算法求无向网的最小生成树.输入:输入数据第一行为两个正整数n和m,分别表示顶点数和边数.后面紧跟m行数据,每行数据是一条边的信息,包括三个数字,分别表示该](/uploads/image/z/10133832-48-2.jpg?t=C%E8%AF%AD%E8%A8%80%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84+%E5%85%8B%E9%B2%81%E6%96%AF%E5%8D%A1%E5%B0%94%E7%AE%97%E6%B3%95%E6%B1%82%E6%97%A0%E5%90%91%E7%BD%91%E7%9A%84%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91.%E8%BE%93%E5%85%A5%EF%BC%9A%E8%BE%93%E5%85%A5%E6%95%B0%E6%8D%AE%E7%AC%AC%E4%B8%80%E8%A1%8C%E4%B8%BA%E4%B8%A4%E4%B8%AA%E6%AD%A3%E6%95%B4%E6%95%B0n%E5%92%8Cm%2C%E5%88%86%E5%88%AB%E8%A1%A8%E7%A4%BA%E9%A1%B6%E7%82%B9%E6%95%B0%E5%92%8C%E8%BE%B9%E6%95%B0.%E5%90%8E%E9%9D%A2%E7%B4%A7%E8%B7%9Fm%E8%A1%8C%E6%95%B0%E6%8D%AE%2C%E6%AF%8F%E8%A1%8C%E6%95%B0%E6%8D%AE%E6%98%AF%E4%B8%80%E6%9D%A1%E8%BE%B9%E7%9A%84%E4%BF%A1%E6%81%AF%2C%E5%8C%85%E6%8B%AC%E4%B8%89%E4%B8%AA%E6%95%B0%E5%AD%97%2C%E5%88%86%E5%88%AB%E8%A1%A8%E7%A4%BA%E8%AF%A5)
C语言数据结构 克鲁斯卡尔算法求无向网的最小生成树.输入:输入数据第一行为两个正整数n和m,分别表示顶点数和边数.后面紧跟m行数据,每行数据是一条边的信息,包括三个数字,分别表示该
C语言数据结构 克鲁斯卡尔算法求无向网的最小生成树.
输入:
输入数据第一行为两个正整数n和m,分别表示顶点数和边数.后面紧跟m行数据,每行数据是一条边的信息,包括三个数字,分别表示该边的两个顶点和边上的权值.
输出:
按顺序输出Kruskal算法求得的最小生成树的边集,每行一条边,包括三个数字,分别是该边的两个顶点和边上的权值,其中第一个顶点的编号应小于第二个顶点的编号.
示例输入
8 11
1 2 3
1 4 5
1 6 18
2 4 7
2 5 6
3 5 10
3 8 20
4 6 15
4 7 11
5 7 8
5 8 12
示例输出
1 2 3
1 4 5
2 5 6
5 7 8
3 5 10
5 8 12
4 6 15
C语言数据结构 克鲁斯卡尔算法求无向网的最小生成树.输入:输入数据第一行为两个正整数n和m,分别表示顶点数和边数.后面紧跟m行数据,每行数据是一条边的信息,包括三个数字,分别表示该
//要用到并查集判断回路,代码先给你吧,看不懂追问
#include <algorithm>
#include <stdio.h>
using namespace std;
#define MAXN 1005 //假设点数不超过1000
int n,m;
int fa[MAXN];
int id[MAXN];
struct Edge { //边的数据结构
int from, to;
int len;
};
Edge edge[MAXN * MAXN];
bool cmp(Edge a, Edge b) { //边的比较函数
return a.len < b.len;
}
int find(int x) { //并查集,用于判断是否与已选择的边构成环
if (fa[x] == -1)
return x;
else
return fa[x] = find(fa[x]);
}
void Kruskal(int n) {
memset(fa, -1, sizeof(fa)); //初始化fa数组
int cnt = 0;
for (int i = 0; i < m; i++) {
int u = edge[i].from;
int v = edge[i].to;
int t1 = find(u); //找第一个点的起始点
int t2 = find(v); //找第二个点的起始点
if (t1 != t2) { //如果不相等,则不构成回路
fa[t1] = t2;
id[cnt]=i;
cnt++;
if (cnt == n - 1) //当已选了n-1条边时,退出循环
break;
}
}
}
int main()
{
while(scanf("%d%d",&n,&m))
{
int a,b,c;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
edge[i].from=min(a,b);
edge[i].to=max(a,b);
edge[i].len=c;
}
sort(edge,edge+m,cmp);
Kruskal(n);
for(int i=0;i<n-1;i++)
{
int t=id[i];
printf("%d %d %d\n",edge[t].from,edge[t].to,edge[t].len);
}
}
return 0;
}