最小生成树实验报告

数据结构课程设计报告主题：最小生成树问题学院(系):计算机工程学院学生姓名：班级：学生编号：开始和结束日期：讲师：2011-2012年下半年一、需求分析1.问题描述：要在n个城市之间建立网络，只需确保连通性，就能找到最经济的架设方法。有许多种存储结构。有许多种求解算法。2.基本功能为了在n个城市之间建立网络，只需要架设n-1条线路，而最经济的架设方法可以通过建立最小生成树来实现。该程序可以使用Kruskar算法或prim算法生成最小生成树。3.输入和输出最小生成树作为文本输出，它们的权重也输出。通过人机对话，即用户通过自己选择命令输入数据并产生相应的数据结果。二。轮廓设计1.设计理念：因为这是最小生成树问题，Kruskar算法和Prim算法使用两种方法来生成最小生成树。根据需要，需要多种存储结构在我的选择中，我采用了两种存储结构：邻接列表和邻接矩阵。2.数据结构设计：图形结构：自动数据图表数据对象V: V是具有相同特征的数据元素集，称为顶点集。数据关系r: r=vrVR=|v，wV和P(v，w)，表示从V到w的弧，谓词P(v，w)定义了弧的含义或信息基本操作：创建图形(G，V，VR)初始条件：V是图的顶点集，VR是图中的弧集。操作结果：按照v和VR的定义构造图g。展开图(G)初始条件：图g存在。操作结果：破坏图形g。LocateVex(G，u)初始条件：图g存在，并且u和g中的顶点具有相同的特征。运算结果：如果G中有一个顶点U，则返回该顶点在图中位置；否则返回回到其他信息。GetVex(G，v)初始条件：图g存在，v是g中的一个顶点。操作结果：返回v的值凸(G，v，值)初始条件：图g存在，v是g中的一个顶点。操作结果：给v赋值。FirstAdjVex(G，v)初始条件：图g存在，v是g中的一个顶点。运算结果：返回v的第一个相邻顶点。如果顶点在G中没有相邻顶点，返回“空”。NextAdjVex(G，v，w)初始条件：图g存在，v是g中的一个顶点，w是v的相邻顶点。运算结果：返回下一个相邻的顶点。如果w是v最后一个相邻点返回“空”。插入凸(G，v)初始条件：图g存在，v与图中的顶点具有相同的特征。运算结果：给图g增加一个新的顶点v。删除凸(G，v)初始条件：图g存在，v是g中的一个顶点。操作结果：删除顶点V及其相关的弧插入弧(G，v，w)初始条件：图g存在，v和w是g中的两个顶点。操作结果：给g加弧，如果g是无向的，加对称弧。删除弧(G、v、w)初始条件：图g存在，v和w是g中的两个顶点。操作结果：在g中删除弧，如果g是无向的，也删除对称弧。董事(G，拜访() )初始条件：图G存在，访问是顶点的应用函数。操作结果：深度优先遍历地图。遍历过程中为每个顶点调用功能访问只发生一次。一旦visit()失败，操作就会失败。博客世界(G，Visit()初始条件：图G存在，访问是顶点的应用函数。操作结果：进行图的广度优先遍历。遍历过程中为每个顶点调用功能访问只发生一次。一旦visit()失败，操作就会失败。日积月累图表存储结构：邻接矩阵：#定义无穷大INT_MAX/最大无穷大#定义最大顶点数20/最大顶点数typedef枚举 UDN GraphKind；typedef结构ArcCellVRType adj。/VRType是顶点关系类型/加权图的权重类型信息信息；/弧相关信息的指针ArcCell，AdjMatrix最大顶点数最大顶点数；typedef结构顶点类型激怒最大顶点数；/顶点向量AdjMatrix弧；/邻接矩阵int vexnum，arcnum/图的当前顶点数和弧数类石墨； MGraph3.详细设计1.数据类型的定义图形类型#定义M 20#定义最大20#定义null 0#定义最大顶点数20/最大顶点数#定义顶点字符串1的最大长度#定义最大信息20 /相关信息字符串的最大长度1#定义INFINITY INT_MAX/将替换为整数最大值typedef int VRType。typedef char InfoType类型定义字符类型最大值名称；/邻接矩阵的数据结构typedef结构VRType adj。/顶点关系类型。对于未经授权的图形，请使用1(是)或0(否)不相邻；/对于加权图，它是加权类型信息类型*信息；/弧相关信息的指针(可选)ArcCell，adjMatrix最大顶点数最大顶点数；/图形的数据结构typedef结构顶点类型激怒最大顶点数；/顶点向量adjMatrix弧；/邻接矩阵Int vexnum，/图形的当前顶点数arcnum/图形的当前弧数 mGraph/记录从顶点集到顶点集的最便宜边的辅助数组定义typedef结构VertexType adjvexVRType低成本；最大顶点数；2.主要模块的算法描述1主要功能Int main(void) /主函数int I；scanf(“% d”，I)；开关(i) /*选择菜单*/案例1:用prim算法寻找最小生成树休息；案例2:用kruskal算法寻找最小生成树休息；默认： printf( t t类型错误！请重新进入！ n )；2使用prim算法生成最小生成树定义图形的数据结构；图的构造；/*最小生成树的prim算法*/I、j、k的定义；记录从顶点集到顶点集的最低成本边的辅助数组定义；将顶点信息分配给k；二级阵列初始化；将最小成本初始化为0，关闭k。低成本=0；/最初，u=u。当循环变量I小于图的当前节点数时，满足循环；根据选择最小成本规则(即，寻找最小正价值，低成本)，选择何时前一个节点的下一个节点(第k个顶点)；输出生成树的边；将第k个顶点合并到u集中；当循环变量j小于图形的当前点数时循环；在新顶点被合并到U集中之后，最小的边被重新选择。3使用kruskal算法生成最小生成树图的构造和初始化定义图形的数据结构；申请节点空间(发生故障时返回信息)；创建图表；/*最小生成树的kruskal算法*/定义或初始化I，j，n，m，父m，边缘m；当循环变量I小于图的当前节点数时，满足循环；当循环变量j=i 1小于图形的当前点数时循环；如果(I顶点连接到j顶点)将I指定给边k。开始；将j指定给边k。结束；将I和J之间的权重分配给边K。重量；k；/*初始化结构边缘*/排序(边缘，G)；)图的G边的权重；当循环变量I小于当前弧度数时将0分配给父i以初始化数组；当循环变量I小于当前弧度数时(此时第I个弧最小)找到I弧的起点和终点；分别给你n，m；当n和m不相等时将m分配给父n；此时输出I弧的起点、终点和重量；流程图：主要功能kruskal算法Prim算法四、调试分析本课程设计基本符合设计要求。但仍有许多不足之处。例如，两种算法不能随意切换，用户不能选择使用邻接矩阵还是邻接表。将来，对计算机知识的更深入学习可能会在这两个方面得到提高。V.测试结果Prim算法校正结果：Prim算法错误结果：Kruskar算法的正确结果：Kruskar算法错误结果：六、经验和自我评价“数据结构”是计算机编程的重要理论和技术基础。它不仅是计算机科学的核心课程，而且已经成为其他科技专业的热门选修课。通过这学期的学习，我学会了分析和研究计算机处理的数据结构的特征，以及算法的事件分析和空间分析。这些有助于我在程序设计过程中更好地为数据选择合适的逻辑结构、存储结构和相应的算法。通常，交通和道路问题的数学模型是一种称为“图”的数据结构。在本主题中，每个顶点代表一个城市，每个边代表一个通信井，同时，每个路径被赋予权重，这代表了该路径的建设成本。通过实现最小生成树，可以以最经济的方式建立通信网络。对于具有n个顶点的通信网络，可以建立许多不同的生成树，并且每个生成树可以是一个通信网络。但是，根据需求，我们需要用最少的资金完成整个通信网络的建设，所以存在最小生成树问题。为了完成本课程的设计，因为教科书中只有初级算法代码，克鲁斯卡算法也需要用百度来搜索。算法找到后，应将其转换成程序源代码来实现其功能。这需要使用计