最小生成树实验报告

数据结构课程设计报告题目：最小生成树问题院〔系〕： 计算机工程学院 学生姓名:班级：学号:起迄日期:指导教师:2011—2012年度第2学期一、需求分析1.问题描述：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。2.根本功能在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。3.输入输出以文本形式输出最小生成树，同时输出它们的权值。通过人机对话方式即用户通过自行选择命令来输入数据和生成相应的数据结果。二、概要设计1.设计思路：因为是最小生成树问题，所以采用了课本上介绍过的克鲁斯卡尔算法和prim算法两种方法来生成最小生成树。根据要求，需采用多种存储结构，所以我选择采用了邻接表和邻接矩阵两种存储结构。2.数据结构设计：图状结构：ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={<v,w>|v,w∈V且P(v,w)，<v,w>表示从v到w的弧，谓词P(v,w)定义了弧<v,w>的意义或信息}根本操作：CreateGraph(&G,V,VR)初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。DestroyGraph(&G)初始条件：图G存在。操作结果：销毁图G。LocateVex(G,u)初始条件：图G存在，u和G中顶点有相同特征。操作结果：假设G中存在顶点u，那么返回该顶点在图中位置；否那么返回其它信息。GetVex(G,v)初始条件：图G存在，v是G中某个顶点。操作结果：返回v的值。PutVex(&G,v,value)初始条件：图G存在，v是G中某个顶点。操作结果：对v赋值value。FirstAdjVex(G,v)初始条件：图G存在，v是G中某个顶点。操作结果：返回v的第一个邻接顶点。假设顶点在G中没有邻接顶点，那么返回“空”。NextAdjVex(G,v,w)初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。操作结果：返回v的〔相对于w的〕下一个邻接顶点。假设w是v的最后一个邻接点，那么返回“空”。InsertVex(&G,v)初始条件：图G存在，v和图中顶点有相同特征。操作结果：在图G中增添新顶点v。DeleteVex(&G,v)初始条件：图G存在，v是G中某个顶点。操作结果：删除G中顶点v及其相关的弧。InsertArc(&G,v,w)初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中增添弧<v,w>，假设G是无向的，那么还增添对称弧<v,w>。DeleteArc(&G,v,w)初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中删除弧<v,w>，假设G是无向的，那么还删除对称弧<v,w>。DFSTraverse(G,Visit())初始条件：图G存在，Visit是顶点的应用函数。操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit()失败，那么操作失败。BFSTraverse(G,Visit())初始条件：图G存在，Visit是顶点的应用函数。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit()失败，那么操作失败。}ADTGraph存储结构：邻接矩阵：#defineINFINITYINT_MAX//最大值无穷#defineMAX_VERTEX_NUM20//最大顶点个数typedefenum{UDN}GraphKind;typedefstructArcCell{ VRTypeadj;//VRType是顶点关系类型 //对带权图为权值类型 InfoTyep*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{ VertexTypevexs[MAX_VERTEX_NUM];//顶点向量 AdjMatrixarcs;//邻接矩阵 intvexnum,arcnum;//图的当前顶点数和弧数 GraphKindkind;}MGraph;详细设计1.数据类型的定义<1>图类型#defineM20#defineMAX20#definenull0#defineMAX_VERTEX_NUM20//最大顶点个数#defineMAX_NAME3//顶点字符串的最大长度+1#defineMAX_INFO20//相关信息字符串的最大长度+1#defineINFINITYINT_MAX//用整型最大值代替∞typedefintVRType;typedefcharInfoType;typedefcharVertexType[MAX_NAME];//邻接矩阵的数据结构typedefstruct{VRTypeadj;//顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；//对带权图，那么为权值类型InfoType*info;//该弧相关信息的指针(可无)}ArcCell,adjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//图的数据结构typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量adjMatrixarcs;//邻接矩阵intvexnum,//图的当前顶点数arcnum;//图的当前弧数}mGraph;//记录从顶点集U到V-U的代价最小的边的辅助数组定义typedefstruct{VertexTypeadjvex;VRTypelowcost;}minside[MAX_VERTEX_NUM];2.主要模块的算法描述<1>主函数intmain(void)//主函数{inti;scanf("%d",&i); switch(i)/*选择菜单*/{case1:{用prim算法求最小生成树}break;case2:{用kruskal算法求最小生成树}break;default:printf("\t\t输入错误！请重新输入！\n");}}<2>使用prim算法生成最小生成树{定义图的数据结构；图的构建；{/*prim算法求最小生成树*/对I,j,k定义；记录从顶点集U到V-U的代价最小的边的辅助数组定义；把顶点信息的赋给k；辅助数组初始化；令最小代价初始化为0，closedge[k].lowcost=0;//初始,U={u}；满足当循环变量i小于图的当前节点数时循环；{按照选取最小代价法那么〔即求closedge.lowcost的最小正值〕选取当前节点的下一结点〔第k顶点〕；输出生成树的边；将第k顶点并入U集合；满足循环变量j小于图的当前点数时循环；{新顶点并入U集后重新选择最小边；}}}}<3>使用克鲁斯卡尔算法生成最小生成树{图的构建并初始化{定义图的数据结构；申请节点空间(如果失败那么返回信息)；创立图；/*kruskal算法求最小生成树*/{对i,j,n,m,parent[M],edgeedges[M]定义或初始化；满足当循环变量i小于图的当前节点数时循环；{满足循环变量j=i+1小于图的当前点数时循环；{if(第i个顶点于第j个顶点相连){把i赋给edges[k].begin；把j赋给edges[k].end；把i，j之间的权值赋给edges[k].weight；K++；}/*对结构体edge进行初始化*/}}对图G边的权值进行排序sort(edges,G)；当循环变量i小于当前弧度数时{将0赋给parent[i]，初始化数组；}当循环变量i小于当前弧度数时(此时第i条弧为最小的){找第i条弧的起点和终点；并分别赋给你n，m；当n，m不相等时{把m赋给parent[n]；输出此时第i条弧的起点、终点、权值；}}}流程图：主函数主函数克鲁斯卡尔算法Prim算法克鲁斯卡尔算法Prim算法调试分析本次课程设计根本到达了设计需求。但是还有很多缺乏。比方不能随意切换两种算法，也不能由用户选择使用邻接矩阵还是邻接表，以后更加深入的学习计算机知识或许可以在这两个方面进行改良。五、测试结果prim算法正确结果：prim算法错误结果：克鲁斯卡尔算法正确结果：克鲁斯卡尔算法错误结果：六、体会与自我评价“数据结构”是计算机程序设计的重要理论技术根底，它不仅是计算机学科的核心课程，而且已成为其他理工专业的热门选修课。本学期通过学习这门课程，我学会了分析研究计算机加工的数据结构的特性，以及算法的事件分析和空间分析。这些帮助我在设计程序的过程中，更好为数据选择适当的逻辑结构、存储结构及其相应的算法。通常情况下，交通、道路问题的数学模型是一种称为“图”的数据结构。在本课题中，每个顶点代表一个城市，每一条边代表一条通信录井，同时给每条路径赋予权值，代表着这条路径的建设代价。通过最小生成树的实现，可以实现以最节省经费的方式来建立这个通信网。对于n个顶点的联通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。但是根据要求，我们需要以最少的经费来完成整个通信网的建设，于是便有了最小生成树问题。为了完本钱次课程设计，因为课本上只有prim算法的代码，所以克鲁斯卡尔算法还需要自己使用百度进行查找。在查找到算法之后