(图论编程题3参考)构成可以使n个城市连接的最小生成树

目录一．需求分析.............................................................................11.1设计的任务.....................................................................................................11.2程序所能达到的功能.....................................................................................11.3程序执行命令.................................................................................................1二．概要设计.............................................................................22.1抽象数据类型结构体数组的定义：.............................................................22.2程序模块.........................................................................................................32.3流程图..............................................................................................................3三．详细设计.............................................................................43.1数据类型定义.................................................................................................43.2程序主要模块.................................................................................................4四．调试分析和测试结果.........................................................64.1调试分析.........................................................................................................64.2测试结果..........................................................................................................7五．总结......................................................................................8六．参考文献.............................................................................8七．致谢......................................................................................9八．附录......................................................................................91构造可以使N个城市连接的最小生成树一．需求分析1.1设计的任务给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。1.2程序所能达到的功能1.2.1城市间的道路网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。1.2.2显示出城市间道路网的邻接矩阵。1.2.3最小生成树中包括的边及其权值，并显示得到的最小生成树的总代价。1.3程序执行命令输入城市数、道路数→输入城市名→输入道路信息→执行Kruskal算法→执行Prim算法→输出最小生成树2二．概要设计2.1抽象数据类型结构体数组的定义：#ifndefADJACENCYMATRIXED//防止该头文件被重复引用#defineADJACENCYMATRIXED//而引起的数据重复定义#defineINFINITY32767//最大值∞#defineMAX_VERTEX_NUM20//最大顶点个数typedefintVRType;//权值，即边的值typedefcharInfoType;//附加信息的类型，后面使用时会定义成一个指针typedefcharVertexType[MAX_VERTEX_NUM];//顶点类型typedefenum{DG=1,DN,UDG,UDN}GraphKind;//{有向图，有向网，无向图，无向网}typedefstructArcCell{VRTypeadj;//VRType是顶点关系类型。对无权图，用1或0表示相邻否；对带权图，则为权值类型。InfoType*info;//该弧关系信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前顶点数和弧数GraphKindkind;//图的种类标志}MGraph;typedefstruct//普里姆算法辅助数组的定义{VertexTypeadjvex;VRTypelowcost;}closedge[MAX_VERTEX_NUM];#endif//结束if32.2程序模块MGraphG;//网G，唯一的全局变量intmain(intargc,char*argv[]);//主函数StatusLocateVex(MGraphG,VertexTypev);//判断城市v在网G中的位置StatusCreateUDN(MGraph&G);//创建网G的邻接矩阵voidDisplayNet(MGraphG);//以邻接矩阵的形式显示网GvoidMiniSpanTree_KRUSKAL(MGraphG);//最小生成树的Kruskal算法voidMiniSpanTree_PRIM(MGraphG,VertexTypeu);//最小生成树的Prim算法StatusMinimum(closedgecloseEdge,intn);//Prim算法中求下一个城市的函数voidDeleteInfo(MGraph&G);//释放堆内存上动态申请的空间2.3流程图创建用邻接矩阵表示的城市道路网输入城市数G.vexnum、道路数G.arcnum输入城市名G.vexs[i]输入表示道路的两个城市及道路值G.arcs[i][j].adj返回OK2.3.1创建邻接矩阵的流程图(N-S图)4Prim算法化辅助数组closeEdgefor(i=1;iG.vexnum;++i)求下一个城市k=Minimum(closeEdge,G.vexnum)输出找到的道路标记城市，避免重复输出总耗费图2.3.2Prim算法流程图（N-S图）三．详细设计3.1数据类型定义为了用邻接矩阵表示图G，先是定义二维数组的每一个元素含道路值然后在图的定义中定义一个此二维数组的结构成员。并且在图中还定义一个用来存放城市的一维数组及int型的城市数级道路数。用二维数组的两个下标表示道路，这两个下标又在一位数组中对应两个城市。这样就建立起了一个城市到城市之间的道路网。3.2程序主要模块说明：该程序共含5个模块，本人负责其中2个模块构造：3.2.1初始化图G***************LocateVex(MGraphG,VertexTypev)****************5StatusLocateVex(MGraphG,VertexTypev);{while(strcmp(G.vexs[i],v)){i++;}返回i；}****************CreateUDN*************************{输入城市数、道路数；for(i=0;i城市数;++i)输入城市名；for(i=0;i城市数;++i)for(j=0;j城市数;++j)初始化邻接矩阵：道路值=INFINITY;for(i=0;i城市数;++i)for(j=0;j城市数;++j)输入两个城市表示道路，输入道路值；}3.2.2PRIM算法**************************MiniSpanTree_PRIM*********voidMiniSpanTree_PRIM(MGraphG,VertexTypeu){定义辅助数组：closedgecloseEdge;初始化：strcpy(closeEdge[j].adjvex,u);closeEdge[j].lowcost=G.arcs[k][j].adj;for(i=1;iG.vexnum;++i){在其余G.vexnum-1个城市中找到离辅助数组中标记的道路最小6值；显示找到的道路；标记新找到的城市；}}**********************Minimum*****************StatusMinimum(closedgecloseEdge,intn){在辅助数组中找到道路值最小的道路的两点城市：if((closeEdge[i].lowcost!=0)&&(minTempcloseEdge[i].lowcost))返回该城市在G中的位置}四．调试分析和测试结果4.1调试分析4.1.1邻接矩阵初始化本函数的主要功能是对无向网进行邻接矩阵的初始化。构造这种具有n个顶点和e条边的无向网时，关键需要考虑其时间复杂度O（n^+e*n）,其中对邻接矩阵G.arcs的初始化花费了O（n^）的时间。4.1.2Prim算法Prim算法的思路是逐步将城市纳入生成树中，这里面的关键步骤是要找到下一个城市。于是通过讨教别人，写了StatusMinimum(closedgecloseEdge,intn)函数，这样就可以在辅助数组中找到道路值最小的道路的两点城市了。74.2测试结果图4.2.1邻接矩阵初始化运行显示界面图4.2.2Prim算法运行显示界面8五．总结通过本周的课程设计，我们小组终于圆满完成了课程设计的任务，我也有不少收获。既巩固和加深了对数据结构的理解，认识到《数据结构》是计算机专业一门重要的专业技术基础课程，还提高了我综合运用本课程所学知识的能力。而且，并不是单纯的看看教材就能解决我们的实际问题，所以还要去查找各种我们所需要的资料，所以这次课程设计也培养了我选用参考书，查阅手册及文献资料的能力。要完成一个课程设计的课题并不是一次就能编译成功的，中间会出现很多的大问题小问题，改错是个很繁琐的问题。通过这次课程设计培养了我独立思考，深入研究，分析问题，解决问题的能力。在以后的学习过程中我将要注意以下几点：1、认真上好专业实验课，多在实践中锻炼自己。2、写程序的过程要考虑周到，严密。3、在做设计的时