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

《克鲁斯卡尔(Kruskal)算法求无向网的最小生成树数据结构报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、 5 103 8 204 6 154 7 115 7 85 8 12示例输出1 2 31 4 52 5 65 7 83 5 105 8 124 6 15一、解题思路（1）假定每对顶点表示图的一条边，每条边对应一个权值；（2）输入每条边的顶点和权值；（3）输入每条边后，计算出最小生成树；（4）打印最小生成树边的顶点及权值。三、源代码#include#includetypedefstruct{inta,b,value;}node;intstcmp(constvoid*p,constvoid*q){nod

3、e*a=(node*)p;node*b=(node*)q;if(a->value>b->value){return1;}elseif(a->value==b->value){return0;}else{return-1;}}introot(inta,int*b){for(;a!=b[a];a=b[a]);returna;}boolisgroup(inta,intb,int*c){if(root(a,c)==root(b,c))returntrue;returnfalse;}voidadd(inta,inttob,int*c){c[roo

4、t(a,c)]=root(tob,c);}intmain(){intn,m;scanf("%d%d",&n,&m);nodeno[m];for(intu=0;u

5、sgroup(no[i].a,no[i].b,bcj)){add(no[i].a,no[i].b,bcj);cc--;printf("%d%d%d",no[i].a,no[i].b,no[i].value);}if(cc==1)break;}return0;}四、运行结果