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

《数据结构,最小生成树克鲁斯卡尔算法的实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Word格式摘要设计了一个用C/C++编写程序实现克鲁斯卡尔最小生成树算法，该程序操作简单，界面清晰，易于为用户所接受。关键词：克鲁斯卡尔，邻接矩阵，最小生成树，vc++。完美整理Word格式完美整理Word格式目录1课题描述12问题分析和任务定义23逻辑设计34详细设计45程序编码106程序调试与测试167结果分析188总结19参考文献20完美整理Word格式1课题描述用C/C++编写程序实现克鲁斯卡尔最小生成树算法。假设要在n个城市之间建立通讯联络网，则连通n个城市只需要n-1条线路。这是我

2、们设计一个最小生成树的程序用来算出最节省经费的前提下建立这个通信站。完美整理Word格式2问题分析和任务定义假设连通网N=（V,{E}）,则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{})，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直到T中所有顶点都在同一连通分量上为止。完美整理Word格式3逻辑设计设计思想：采用邻接矩阵来存储图，然后采用克鲁斯卡尔算法求

3、出最小生成树。结构体定义函数模块二（求最小生成树）克鲁斯卡尔算法函数模块一（图的创建）采用邻接矩阵做存储结构主函数引用函数模块一、二，实现算法设计1）．定义结构体。2）．采用邻接矩阵做存储结构创建图（函数模块一）。3）．采用克鲁斯卡尔算法求出该图的最小生成树（函数模块二）。4）．在主函数里面分别调用以上各个函数，最终实现设计目的。完美整理Word格式4详细设计4.1．程序结构·函数CreateMGraph用来实现图的创建，以及图的相关信息的存储。图的存储采用邻接矩阵存储结构。·函数minitre

4、e_KRUSKAL用来求图的最小生成树。图的最小生成树有普利姆算法和克鲁斯卡尔算法可以实现，本段代码使用的是克鲁斯卡尔算法，这也是本题所要求使用的。·各个函数间的联系先调用函数CreateMGraph实现图的创建，然后调用函数minitree_KRUSKAL求出该图的最小生成树4.2．设计说明·在开始的时候添加一些限制条件方便函数的功能实现例如：#defineMaxVertexNum100//最大顶点个数#defineQueueSize30#defineM30·模块一：图的创建·结构体定义为：t

5、ypedefstruct{VertexTypevexs[MaxVertexNum];//顶点表Linkedges[MaxVertexNum][MaxVertexNum];//图中当前的相连接的两个顶点intn,e;//图中当前的顶点数和边数}MGraph;·函数定义为：MGraphCreateMGraph(){完美整理Word格式MGraphG;inti,j,k,ch3;charch1,ch2;printf("请输入该图的顶点数和边数:");scanf("%d,%d",&(G.n),&(G.

6、e));printf("请输入该图的顶点信息:");for(i=1;i<=G.n;i++){getchar();scanf("%c",&(G.vexs[i]));}for(i=1;i<=G.n;i++)for(j=1;j<=G.n;j++)G.edges[i][j].w=0;printf("请输入该图每条边对应的两个顶点的名称:");for(k=1;k<=G.e;k++){scanf("%c",&ch1);printf("请输入第%d条边的顶点序号：",k);scanf("%c%c",&

7、ch1,&ch2);printf("请输入第%d条边的权值大小：",k);scanf("%d",&ch3);for(i=1;ch1!=G.vexs[i];i++);for(j=1;ch2!=G.vexs[j];j++);e[p].vexh=i;e[p].vext=j;e[p].weight=G.edges[i][j].w=ch3;//权值e[p].flag=0;p++;}returnG;}流程如图4.1所示完美整理Word格式创建图使用的是函数MGraphCreateMGraph()，该图的存储

8、结构是邻接矩阵，先对图的结构体进行定义，再进行初始化。在函数中需要手动输入图的参数（如顶点数、边数、顶点信息、相连接的顶点、边的权值等）用来建立图并且确定图的邻接矩阵。最后在完成图的信息输入即建立图以后输出图的邻接矩阵表。·模块二：求图的最小生成树。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(in){