2020年数据结构,最小生成树克鲁斯卡尔算法的实现.doc

摘要设计了一个用C/C++编写程序实现克鲁斯卡尔最小生成树算法,该程序操作简单,界面清晰,易于为用户所接受。关键词:克鲁斯卡尔,邻接矩阵,最小生成树,vc++。目录1课题描述 12问题分析和任务定义 23逻辑设计 34详细设计 45程序编码 106程序调试与测试 167结果分析 188总结 19参考文献 201课题描述用C/C++编写程序实现克鲁斯卡尔最小生成树算法。假设要在n个城市之间建立通讯联络网,则连通n个城市只需要n-1条线路。这是我们设计一个最小生成树的程序用来算出最节省经费的前提下建立这个通信站。2问题分析和任务定义假设连通网N=(V,{E}),则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{}),图中每个顶点自成一个连通分量。在E中选择代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入到T中,否则舍去此边而选择下一条代价最小的边。依次类推,直到T中所有顶点都在同一连通分量上为止。3逻辑设计设计思想:采用邻接矩阵来存储图,然后采用克鲁斯卡尔算法求出最小生成树。结构体定义函数模块二(求最小生成树)克鲁斯卡尔算法函数模块一(图的创建)采用邻接矩阵做存储结构主函数引用函数模块一、二,实现算法设计1).定义结构体。2).采用邻接矩阵做存储结构创建图(函数模块一)。3).采用克鲁斯卡尔算法求出该图的最小生成树(函数模块二)。4).在主函数里面分别调用以上各个函数,最终实现设计目的。·函数CreateMGraph用来实现图的创建,以及图的相关信息的存储。图的存储采用邻接矩阵存储结构。·函数minitree_KRUSKAL 用来求图的最小生成树。图的最小生成树有普利姆算法和克鲁斯卡尔算法能够实现,本段代码使用的是克鲁斯卡尔算法,这也是本题所要求使用的。·各个函数间的联系先调用函数CreateMGraph实现图的创建,·在开始的时候添加一些限制条件方便函数的功能实现例如:#defineMaxVertexNum100//最大顶点个数#defineQueueSize30#defineM30·模块一:图的创建·结构体定义为:typedefstruct{ VertexTypevexs[MaxVertexNum]; //顶点表 Linkedges[MaxVertexNum][MaxVertexNum];//图中当前的相连接的两个顶点 intn,e; //图中当前的顶点数和边数}MGraph;·函数定义为:MGraphCreateMGraph(){ MGraphG; inti,j,k,ch3;charch1,ch2;printf("请输入该图的顶点数和边数:\n");scanf("%d,%d",&(),&());printf("请输入该图的顶点信息:\n");for(i=1;i<=;i++){getchar(); scanf("%c",&([i]));}for(i=1;i<=;i++)for(j=1;j<=;j++)[i][j].w=0; printf("请输入该图每条边对应的两个顶点的名称:\n"); for(k=1;k<=;k++){ scanf("%c",&ch1);printf("请输入第%d条边的顶点序号:",k);scanf("%c%c",&ch1,&ch2); printf("请输入第%d条边的权值大小:",k);scanf("%d",&ch3);for(i=1;ch1!=[i];i++);for(j=1;ch2!=[j];j++); e[p].vexh=i; e[p].vext=j;e[p].weight=[i][j].w=ch3;//权值 e[p].flag=0; p++;} returnG;}创建图使用的是函数MGraphCreateMGraph(),该图的存储结构是邻接矩阵,先对图的结构体进行定义,再进行初始化。在函数中需要手动输入图的参数(如顶点数、边数、顶点信息、相连接的顶点、边的权值等)用来建立图并且确定图的邻接矩阵。最后在完成图的信息输入即建立图以后输出图的邻接矩阵表。·模块二:求图的最小生成树。voidminitree_KRUSKAL(MGraph*G){ inti,min,j,k; VEXt[M]; for(i=1;i<=G->n;i++) { t[i].data=G->vexs[i]; t[i].jihe=i; } i=1; while(i<G->n) { min=MaxVertexNum; for(j=0;j<G->e;j++) { if(e[j].weight<min&&e[j].flag==0) { min=e[j].weight; k=j; } } if(t[e[k].v