克鲁斯卡尔算法求无向网的最小生成树数据结构报告

1、数据结构上机报告（1）姓名：张可心 学号班级：1403018一、题目描述用克鲁斯卡尔（Kruskal）算法求无向网的最小生成树，分 析你的算法的时空复杂度，必须有过程说明。输入：输入数据第一行为两个正整数n和m，分别表示顶点数和边 数。后面紧跟m行数据，每行数据是一条边的信息，包括三 个数字，分别表示该边的两个顶点和边上的权值。输出：按顺序输出Kruskal算法求得的最小生成树的边集，每行一 条边，包括三个数字，分别是该边的两个顶点和边上的权值， 其中第一个顶点的编号应小于第二个顶点的编号。示例输入8 112 34 5 TOC o 1-5 h z 6 184 75 6

2、5 108 206 1547115785812示例输出123145256578351058124615二、解题思路假定每对顶点表示图的一条边，每条边对应一个权值;输入每条边的顶点和权值；输入每条边后，计算出最小生成树；打印最小生成树边的顶点及权值。三、源代码#include#includetypedef struct (int a,b,value；node；int stcmp(const void *p,const void *q)(node *a=(node *)p;node *b=(node *)q;if(a-valueb-value)return 1;else if(a-value=b-

3、value)return 0;elsereturn -1;int root(int a,int *b)for(;a!=ba;a=ba);return a；bool isgroup(int a,int b,int *c)( if(root(a,c)=root(b,c)return true； return false；void add(int a,int tob,int *c)( croot(a,c)=root(tob,c)；int main ()(int n,m;scanf(%d %d”,&n,&m);node nom;for(int u=0;um;u+)scanf(%d,&(nou.a);s

4、canf(%d,&(nou.b);scanf(%d,&(nou.value);qsort(no,m,sizeof(no0),stcmp);int bcjn+1;for(int u=1;u=n;u+) bcju=u;int i=0;int cc=n;for(;im;i+)if(!isgroup(noi.a,noi,b,bcj) add(noi.a,noi.b,bcj);cc;printf(%d %d %dn,noi.a,noi.b,noi.value);if(cc=1)break;return 0;四、运行结果C:Program Files (x86)Dev-CppConsolePauser.exeB 1112 314 5 TOC o 1-5 h z 6 184 75 65 108 206 157 117 88 1212 314 55 G5 7 85 105 8 126 15