大数据结构课程设计-最小生成树
数据结构期末课程设计题目第8题:最小生成树问题学院专业班别学号姓名陈聪2015年7月6日一、需求分析1、问题描述若要在n个城市之间建设通讯网络,只需要架设n-1条线路即可。如何以最 低的经济代价建设这个通讯网,是一个网的最小生成树问题。2、基本要求(1)利用克鲁斯卡尔算法求网的最小生成树。(2)实现并查集。以此表示构造生成树过程中的连通分量。(3)以文本形式输出生成树中各条边以及他们的权值。3、实现提示通讯线路一旦建立,必然是双向的。因此,构造最小生成树的网一定是无向 网。设图的顶点数不超过30个,并为简单起见,网中边的权值设成小于100的 整数,可利用C语言提供的随机数函数产生。图的存储结构的选取应和所作操作向适应。为了便于选择权值最小的边,此 题的存储结构既不选用邻接矩阵的数组表示法,也不选用邻接表,而是以存储边 (带权)的数组即边集数组表示图。二、详细设计根据课设题目要求,拟将整体程序分为三大模块,分别是:图的存储结构,并查 集的实现,克鲁斯卡尔算法的实现。1、边集数组的类型定义:typedef structint x, y;int w;edge;x表示起点,y表示终点,w为权值。2、并查集功能的实现由以下函数实现:Make_Set(int x)初始化集合;Find_Set(int x)查找x元素所在的集合,回溯时压缩路径; Union(int x, int y, int可)合并x,y所在的集合。3、克鲁斯卡尔算法的实现该算法的实现位于主函数中:qsort(e, n, sizeof(edge), cmp);将边排序printf("最小生成树的各条边及权值为:n");for (i = 0; i < n; i+)x = Find_Set(ei.x);y = Find_Set(ei.y);if (x != y )printf("%c - %c : %dn", ei.x + 'A', ei.y + 'A', ei.w);Union(x, y, ei.w);4、设计中还包含以下函数:(1) /*比较函数,按权值(相同则按x坐标)非降序排序*/int cmp(const void *a, const void *b)if (*(edge *)a).w = (*(edge *)b).w)return (*(edge *)a).x - (*(edge *)b).x;return (*(edge *)a).w - (*(edge *)b).w;(2) 快排函数qsort,包含在stdlib.h头文件里qsort(e, n, sizeof(edge), cmp);(3) C语言提供的随机数函数srand( unsigned int seed );使用随机数函数如下:srand( (unsigned)time( NULL );for( i = 0; i < n;i+ )ei.w=rand()%100+1;ei.x = chx - 'A'if(chy=h+48) chx+;ei.y = (chy+) - 'A'if(chy=h+49) chy=chx+1;Make_Set (i);输出1100之间的随机数,使用rand()%100+1。5、主程序的流程图一'、开始(结束)三、调试分析调试过程中遇到的问题:随机产生权值时,通过边数不能确定起点和终点。解决:通过顶点数对所有边取随机数。四、用户使用说明及测试结果1、打开界面:r最小生成树问题:人为输入权值请输入1,随机生成权值请输入的:(1)人为输入权值,输入1,回车:尹最小生成树可题:,为输入权值请输入上,随机生成权值请输入。:请输入边的条数(小于436):输入7,回车:最刁生成权寸问题=人为输入权值请输入L随机生成枳直请输入触:1请输入边的条数(小于理非)=请输入边的信息.起点n袈点n枳值"Sm.)分别用空格隅升二输入边的信息及结果如下:最小生成树问题:,为输入权值请输入,随机生成权值请输入& :§输入边的条数(小于436):帝输入边的信息(起点,终点,权值«106)分别用空格隔开:k b 3k d 8k e 10b d 6d e 9b c 15L e 12快小生成树的各条边及权值为:a b : 3b - d : 6fl - e : 9c e : 12Process exited uitli return value 0 Press any key to continue . . . H(2)随机生成权值,输入0:五、经验和体会通过本次课程设计,我学会了利用克鲁斯卡尔算法求最小生成树。另外学会了利 用随机函数产生随机数,以及课本没有提到的边集数组的定义和使用。六、附录源代码#include <stdio.h>#include <stdlib.h>#include "time.h"#define MAX 435 /*定义边(x,y),权为w */ typedef structint x, y;int w;edge;edge eMAX;/* rankx表示x的秩*/int rankMAX;/* fatherx表示x的父节点*/int fatherMAX;/*比较函数,按权值(相同则按x坐标)非降序排序*/int cmp(const void *a, const void *b)if (*(edge *)a).w = (*(edge *)b).w)return (*(edge *)a).x - (*(edge *)b).x;return (*(edge *)a).w - (*(edge *)b).w;/*初始化集合*/void Make_Set(int x)fatherx = x;rankx = 0;/*查找x元素所在的集合,回溯时压缩路径*/int Find_Set(int x)while(fatherx)x=fatherx;return x;/*合并x,y所在的集合*/void Union(int x, int y, int w)if (x = y) return;/*将秩较小的树连接到秩较大的树后*/if (rankx > ranky)fathery = x;elseif (rankx = ranky)ranky+;fatherx = y;/*主函数*/int main()printf("*最小生成树问题:n");int i, n,h,k=0;int x, y;char chx, chy;printf("n人为输入权值请输入1,随机生成权值请输入0: n");scanf("%d",&k);if(k=1)/*读取边的数目*/printf("请输入边的条数(小于436):n");scanf("%d”, &n);getchar();/*读取边信息并初始化集合*/printf("请输入边的信息(起点,终点,权值(<100)分别用空格隔开:n");for (i = 0; i < n; i+)scanf("%c %c %d”, &chx, &chy, &ei.w);getchar();ei.x = chx - 'A'ei.y = chy - 'A'Make_Set(i);elseprintf("请输入顶点数(<=30):n");scanf("%d”, &h);getchar();srand( (unsigned)time( NULL );n=(h-1)*h/2;chx=49;chy=50;for( i = 0; i < n;i+ )ei.w=rand()%100+1;ei.x = chx - 'A'if(chy=h+48) chx+;ei.y = (chy+) - 'A'if(chy=h+49) chy=chx+1;Make_Set(i);printf("随机生成的各条边及权值为:n");for (i = 0; i < n; i+)printf("%c - %c : %dn", ei.x + 'A', ei.y + 'A', ei.w);/*将边排序*/qsort(e, n, sizeof(edge), cmp);printf("最小生成树的各条边及权值为:n");for (i = 0; i < n; i+)x = Find_Set(ei.x);y = Find_Set(ei.y);if (x != y )printf("%c - %c : %dn", ei.x + 'A', ei.y + 'A', ei.w);Union(x, y, ei.w);return 0;