最小生成树kruskal算法实现.doc

(最小生成树kruskal算法的实现)一。需求分析:题目:最小生成树kruskal算法的实现问题描述:任意创建一个图,用kruskal算法求去他的最小生成树。举例:若要在n个城市之间建设通信网络,只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网,我们可以用求kruskal算法求这个网的最小生成树来解决这个问题。(1)建立一个图,其存储方式可以采用邻接矩阵形式,需要定义两个数组,一个存储顶点,一个存储边,存储边的数组表明节点间的连通关系和边的权值;(2)利用克鲁斯卡尔算法求网的最小生成树;(3)按顺序输出生成树中各条边以及它们的权值。输入的形式和输入值的范围:输入的数值有各顶点,两顶点之间的权值。输入的顶点最多不能大于20个。输出的形式:先输出图的邻接矩阵,输出权值的排序,最后输出最小生成树的各边和权值。程序所能达到的功能;用户可以任意的输入一个顶点小于20的图,该程序可以求出图的邻接矩阵和最小生成树。D测试数据:651212323434541563245输出结果:《V1,V2》1《V2,V3》2《V3,V4》3《V4,V5》4二。概要分析1本程序中用到的所有抽象数据类型的定义ADTGraph{数据对象V:V是具有向他特性的数据元素的集合,称为顶点集。数据关系对象:R={VR}VR={<V,W>|(V,W),<V,W>表示V到W的弧,谓词P(V,W)定义了弧<V,W>的意义或信息}基本操作P:CreateCraph(&G,V,VR);初始条件:V是图的顶点集,VR是图中的弧的集合。操作结果:按V和VR的定义构造图G..MiniSpanTree(G);初始条件:图G存在。操作结果:求出图G的最小生成树Sort(edge*,MGraph*);初始条件:图G存在,edge存在。操作结果;对edge进行了排序。Swapn(edge*,intx,inty);初始条件:edge存在,x,y是两条边操作结果:交换了x,y这两条边。Find(int*,int);初始条件:edge存在:操作结果:对这些边进行遍历查找。2主程序的流程intmain(void)//主函数{ MGraph*G;程序中定义一个图 G=(MGraph*)malloc(sizeof(MGraph));为这个图动态分配存储空间 if(G==NULL) {printf("memoryallcationfailed,goodbye"); exit(1); }如果这个图不存在系统将会非正常结束 CreatGraph(G);创建一个图{输入总边数和总顶点输入各顶点和顶点之间的权值输出该图的邻接矩阵}MiniSpanTree(G); 求该图的最小生成树{对权值进行排序输出排序后的权值和顶点对各边依次进行判断,是否存在回路,如果没有回路,则输出这条边,否则,则不输出} system("pause");程序运行暂停 return0;3序模块之间的层次(调用)#defineM20#defineMAX20规定该程序所能创建图的最大顶点数为20个点typedefstruct//用结构体定义边{ }edge;typedefstruct//用结构体定义数组{ }AdjMatrix[MAX][MAX];typedefstruct//用结构体定义一个图{}MGraph;函数申明voidCreatGraph(MGraph*);//图构建函数申明voidsort(edge*,MGraph*);//权值排序函数申明voidMiniSpanTree(MGraph*);//生成最小树函数的申明intFind(int*,int);//尾顶点查找voidSwapn(edge*,int,int);//权值、头顶点、尾顶点交换voidCreatGraph(MGraph*G)//构件图{ printf("请输入边数和顶点数:\n");G->arc[i][j].adj=G->arc[j][i].adj=0;//先把矩阵中所有元素赋值为0 for(i=1;i<=G->um;i++)//输入边和权值 G->arc[n][m].adj=G->arc[m][n].adj=1;//将输入的顶点记录为1 getchar(); printf("请输入%d与%d之间的权值:\n",n,m); printf("邻接矩阵为:\n");输出邻接矩阵 ···········································································以上是图的创建,邻接矩阵的建立将辅助权值排序voidMiniSpanTree(MGraph*G)//生成最小生成树{}sort(edges,G);//sort函数调用,对权值进行排