C语言数据结构 克鲁斯卡尔算法求无向网的最小生成树.输入:输入数据第一行为两个正整数n和m,分别表示顶点数和边数.后面紧跟m行数据,每行数据是一条边的信息,包括三个数字,分别表示该

来源:学生作业帮助网 编辑:六六作业网 时间:2024/12/24 21:20:35
C语言数据结构克鲁斯卡尔算法求无向网的最小生成树.输入:输入数据第一行为两个正整数n和m,分别表示顶点数和边数.后面紧跟m行数据,每行数据是一条边的信息,包括三个数字,分别表示该C语言数据结构克鲁斯卡

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;
}

C语言数据结构 克鲁斯卡尔算法求无向网的最小生成树.输入:输入数据第一行为两个正整数n和m,分别表示顶点数和边数.后面紧跟m行数据,每行数据是一条边的信息,包括三个数字,分别表示该 求一个学过数据结构(C语言版)的大神,有一个关于克鲁斯卡尔算法和普里姆算法的问题!需要大神指点,如题 用普里姆(Prim)或克鲁斯卡尔(Kruskal)算法画出下列无向网的最小生成树求解答,有回必应 对图2所示的无向带权图,用普里姆算法或克鲁斯卡尔算法求其最小生成树 最小生成树 普里姆算法和克鲁斯卡尔算法基本功能要求:①输入并存储至少8个顶点14条边的无向图.②分别编写普里姆算法和克鲁斯卡尔算法,求出最小生成树,输出最小生成树的生成过程.好 请对下图的无向带权图:1写出它的邻接矩阵,并按普里姆算法求其最小生成树;1写出它的邻接矩阵,并按普里姆算法求其最小生成树;2写出它的邻接表,并按克鲁斯卡尔算法求其最小生成树. 求最小生成树程序用克鲁斯卡尔算法编写;C++语言;当然最后输出的是那个最小的权值.输入数据的时候最好用一个邻接矩阵的形式150分决不食言!有说明的最好 数据结构无向图的建立帮忙写个建立无向图的代码,C语言,要能跑通的代码哦~(无向图通过邻接矩阵建立) 求数据结构与算法分析:C语言描述Mark Allen Weiss写的是课文,最好是英文的. 数据结构(C) 请用类C语言实现括号匹配的检验这个算法 1. 已知一个图如图所示,用克鲁斯卡尔算法计算最小生成树中各边上数值之和为( )A. 24 B . 26 C. 28 D. 33 我肿么算都是24呀. 数据结构的结构与算法和C语言的区别是什么 数据结构 用C语言编程:求邻接矩阵存储结构的有向图G中各结点的出度 学C语言算法与数据结构买什么书好,不是伪代码的 C语言数据结构与算法要掌握哪些知识, 求一个括号算法匹配算法的代码,C语言版的数据结构 求推荐数据结构与算法的参考书 求数据结构c语言描述求无向网的最小生成树的代价.多组数据,输入数据第一行为整数t,表示有几组测试数据.每组测试数据由m+1行构成,第一行为两个正整数n和m,分别表示顶点数和边数.后面紧