[已解决]克鲁斯卡尔算法求助!

vizey

代码是残缺的，希望有大佬能帮帮我

城市间道路铺设问题
实现图的最小生成树问题的克鲁斯卡尔算法。

输入：
第一行两个整数，分别表示顶点个数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[100];

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[j]); 
                b = Find(e[j]);  //找出第j条边两个端点所在的集合
                 if (a != b) {            //若不同，第j条边放入树中并合并这两个集合
                        t[k++] = 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[i].u,&e[i].v,&e[i].weight);

    
        return 0;
} 

最佳答案

月排行榜 / 总排行榜

grant1944

2021-9-7 21:18:23

#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[N],path[N];

int find(int a){
    if (p[a] != a) p[a] = find(p[a]);
    return p[a];
}

struct Edge{
    int a,b,w;// 需要对边排序，用结构体存储
    bool operator< (const Edge& W) const{
        return w < W.w;// 重载小于号
    }
}edge[M];

int kruskal(){
    sort(edge + 1,edge + m + 1);// 数组从下标为1开始存边
    for (int i = 1; i <= n; i ++ ) p[i] = i;// 初始化并查集
    
    int res = 0,cnt = 0;// res存放最小生成树的边权之和，cnt存放最小生成树的边数
    for (int i = 1;i <= m;i ++){
        int a = edge[i].a,b = edge[i].b,w = edge[i].w;
        a = find(a),b = find(b);
        if (a != b){
            p[a] = b;
            res += w;
            cnt ++;
            path[cnt] = 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[i] = {u,v,w};
    }
    
    int res = kruskal();

    for (int i = 1;i <= n-1;i ++){
        int id = path[i];
        cout << edge[id].a << ' ' << edge[id].b << ' ' << edge[id].w << '\n';
    }
    cout << res << '\n';
    return 0;
}

自己写的，没有按照你给的代码

跳转到最佳答案楼层

grant1944

#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[N],path[N];

int find(int a){
    if (p[a] != a) p[a] = find(p[a]);
    return p[a];
}

struct Edge{
    int a,b,w;// 需要对边排序，用结构体存储
    bool operator< (const Edge& W) const{
        return w < W.w;// 重载小于号
    }
}edge[M];

int kruskal(){
    sort(edge + 1,edge + m + 1);// 数组从下标为1开始存边
    for (int i = 1; i <= n; i ++ ) p[i] = i;// 初始化并查集
    
    int res = 0,cnt = 0;// res存放最小生成树的边权之和，cnt存放最小生成树的边数
    for (int i = 1;i <= m;i ++){
        int a = edge[i].a,b = edge[i].b,w = edge[i].w;
        a = find(a),b = find(b);
        if (a != b){
            p[a] = b;
            res += w;
            cnt ++;
            path[cnt] = 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[i] = {u,v,w};
    }
    
    int res = kruskal();

    for (int i = 1;i <= n-1;i ++){
        int id = path[i];
        cout << edge[id].a << ' ' << edge[id].b << ' ' << edge[id].w << '\n';
    }
    cout << res << '\n';
    return 0;
}

自己写的，没有按照你给的代码