克鲁斯卡尔算法求助!
代码是残缺的，希望有大佬能帮帮我{:10_254:}城市间道路铺设问题
实现图的最小生成树问题的克鲁斯卡尔算法。
输入：
第一行两个整数，分别表示顶点个数n和边数m，从第二行到第m+1行，每行三个整数分别表示每条边的两个顶点号及权值。
6 10
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6
输出：
依次输出选中的n-1条边及最小生成树的权值之和
1 3 1
4 6 2
2 5 3
3 6 4
2 3 5
15
#include<bits\stdc++.h>
using namespace std;
struct edge{
int u,v,weight;
}e;
void initialize(int n){
for(int i=0;i<n;i++){
}
}
int Find(int i){
}
void merge(int i,int j){
if() return false;
return true;
}
int Kruskal(int n, **e){
int k,j,a,b;
Sort(e, weight);//将边按权重从小到大排序
initialize(n); //初始时每个顶点为一个集合
k = j =1; //k累计已选边的数目，j为所选的边在e中的序号
while (k < n){ //选择n - 1条边
a = Find(e);
b = Find(e);//找出第j条边两个端点所在的集合
if (a != b) { //若不同，第j条边放入树中并合并这两个集合
t = j;
merge(a, b);
}
j++;
}
} //继续考察下一条边
int main(){
int n,m;
printf("请输入顶点个数n和边数m\n");
scanf("%d%d",&n,&m);
printf("\n请输入每条边对应的顶点号以及对应的权值\n");
int i,j;
for (i=0;i<m;i++) scanf("%d%d%d",&e.u,&e.v,&e.weight);
return 0;
} #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define IOS \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0)
const int N = 1e5+5,M = 2e5+5;
int n,m;
int p,path;
int find(int a){
if (p != a) p = find(p);
return p;
}
struct Edge{
int a,b,w;// 需要对边排序，用结构体存储
bool operator< (const Edge& W) const{
return w < W.w;// 重载小于号
}
}edge;
int kruskal(){
sort(edge + 1,edge + m + 1);// 数组从下标为1开始存边
for (int i = 1; i <= n; i ++ ) p = i;// 初始化并查集
int res = 0,cnt = 0;// res存放最小生成树的边权之和，cnt存放最小生成树的边数
for (int i = 1;i <= m;i ++){
int a = edge.a,b = edge.b,w = edge.w;
a = find(a),b = find(b);
if (a != b){
p = b;
res += w;
cnt ++;
path = i;
}// n个点一共n-1条边
if (cnt == n-1) break;// 处理完提前退出
}
return res;
}
int main(){
IOS;
cin >> n >> m;
int u,v,w;
for (int i = 1; i <= m; i ++ ){
cin >> u >> v >> w;
edge = {u,v,w};
}
int res = kruskal();
for (int i = 1;i <= n-1;i ++){
int id = path;
cout << edge.a << ' ' << edge.b << ' ' << edge.w << '\n';
}
cout << res << '\n';
return 0;
}
自己写的，没有按照你给的代码
页:
[1]