最小生成树实验报告材料

1、数据结构课程设计报告题目：最小生成树问题院（系）：计算机工程学院学生姓名：班级：学号：起迄日期：指导教师：20112012年度 第2 学期一、需求分析1 .问题描述：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储 结构采用多种。求解算法多种。2 .基本功能在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实 现最经济的架设方法。程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。3 .输入输出以文本形式输出最小生成树，同时输出它们的权值。通过人机对话方式即 用户通过自行选择命令来输入数据和生成相应的数据结果。二、概要设计1 .设计思路：因为是最小生成树问题，所以采用了课本上介绍过的克鲁斯卡尔算法和 prim算法两种方法来生成最小生成树。根据要求，需采用多种存储结构，所 以我选择采用了邻接表和邻接矩阵两种存储结构。2 .数据结构设计：图状结构：ADT Graph数据对象V: V是具有相同特性的数据元素的集合，称为顶点集。数据关系R: R=VRVR=|v,w6 V且 P(v,w) , 表示从 v 到 w 的弧，谓词P(v,w)定义了弧的意义或信息基本操

2、作：CreateGraph( &G, V, VR )初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图GoDestroyGraph( &G )初始条件：图G存在。操作结果：销毁图GoLocateVex( 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中

3、增添新顶点v。DeleteVex( &G, v )初始条件：图G存在，v是G中某个顶点。操作结果：删除G中顶点v及其相关的弧。InsertArc( &G, v, w )初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中增添弧,若G是无向的，则还增添对称弧。DeleteArc( &G, v, w )初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中删除弧,若G是无向的，则还删除对称弧。DFSTraverse( G, Visit()初始条件：图G存在，Visit是顶点的应用函数。操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函数Visit 一次且仅一次。一旦visit() 失败，则操作失败。BFSTraverse( G, Visit()初始条件：图G存在，Visit是顶点的应用函数。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit 一次且仅一次。一旦visit() 失败，则操作失败。ADT Graph存储结构：邻接矩阵：#define INFINITY INT_MAX/最大值无穷#define MAX_VERTEX_NUM 20/最大顶点

4、个数typedef enumUDN GraphKind;typedef struct ArcCellVRType adj;/VRType 是顶点关系类型/对带权图为权值类型InfoTyep *info;/ 该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexType vexsMAX_VERTEX_NUM;/点向量AdjMatrix arcs;/邻接矩阵int vexnum,arcnum;/ 图的当前顶点数和弧数 GraphKind kind;MGraph;三、详细设计1.数据类型的定义图类型# define M 20# define MAX 20# define null 0# define MAX_VERTEX_NUM 20/ 最大顶点个数# define MAX_NAME 3 /顶点字符串的最大长度 +1# define MAX_INFO 20 /相关信息字符串的最大长度 +1#define INFINITY INT_MAX/用整型最大值代替typedef int VRType;typ

5、edef char InfoType;typedef char VertexTypeMAX_NAME;/邻接矩阵的数据结构typedef structVRType adj; /顶点关系类型。对无权图，用1（是）或0（否）表示 相邻否；/对带权图，则为权值类型InfoType *info; /该弧相关信息的指针（可无）ArcCell, adjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;/图的数据结构typedef structVertexType vexsMAX_VERTEX_NUM;/ 顶点向量adjMatrix arcs;/邻接矩阵int vexnum,/图的当前顶点数arcnum;/ 图的当前弧数 mGraph;/记录从顶点集U到V-U的代价最小的边的辅助数组定义typedef structVertexType adjvex;VRType lowcost;minsideMAX_VERTEX_NUM;2.主要模块的算法描述主函数int main(void) /主函数int i;scanf(%d,&i);switch(i)/*选择菜单 */case 1:用pr

6、im算法求最小生成树break;case 2:用kruskal算法求最小生成树break;default:printf(tt输入错误！请重新输入！n);使用prim算法生成最小生成树定义图的数据结构；图的构建；/*prim算法求最小生成树*/对I,j,k 定义；记录从顶点集U到V-U的代价最小的边的辅助数组定义；把顶点信息的赋给k;辅助数组初始化；令最小代价初始化为0, closedgek.lowcost=0;/初始,U=u；满足当循环变量i小于图的当前节点数时循环；按照选取最小代价法则（即求closedge.lowcost的最小正值）选取当前节点的下一结点（第k顶点）；输出生成树的边；将第k顶点并入U集合；满足循环变量j小于图的当前点数时循环；新顶点并入U集后重新选择最小边；使用克鲁斯卡尔算法生成最小生成树图的构建并初始化定义图的数据结构；申请节点空间（如果失败则返回信息）；创建图；/*kruskal算法求最小生成树*/对 i,j,n,m, parentM,edge edgesM 定义或初始化；满足当循环变量i小于图的当前节点数时循环；满足循环变量j=i+1小于图的当前点数时循环；i

7、f（ 第i个顶点于第j个顶点相连） 把 i 赋给 edgesk.begin ；把 j 赋给 edgesk.end ；把i , j之间的权值赋给edgesk.weight ；K+; /*对结构体edge进行初始化*/对图G边的权值进行排序sort(edges, G);当循环变量i小于当前弧度数时将0赋给parenti,初始化数组；当循环变量i小于当前弧度数时(此时第i条弧为最小的)找第i条弧的起点和终点；并分别赋给你n, mi当n, m不相等时把 m赋给 parentn；输出此时第i条弧的起点、终点、权值；流程图：四、调试分析本次课程设计基本达到了设计需求。 但是还有很多不足。比如不能随意切换两种 算法，也不能由用户选择使用邻接矩阵还是邻接表， 以后更加深入的学习计算机 知识或许可以在这两个方面进行改进。五、测试结果prim算法正确结果：寤吃嚎造耀嬴请选择相应的菜单U-幻请翻入兀户网G的顶点打,边麴,边是否含其它信息是二1,三5“空格区分3 2 0 请输不顶煮的值3个子高八瀛九条边的顶点工顶点之权值皿空格作为间隔：1 2 1弟小价生成树的各条边为：Cl-2(2-3请按任意键继续. . .

8、prim算法错误结果:权值以空格作为间隔的各条边为道提人无向网G的顶点带 ，皤入1个顶点的值请输入工条边的顶点T请选择相应的菜单仃-幻：9数.边是否含其它信息是r .否：0 ： 空格区分3克鲁斯卡尔算法正确结果:I 请选择相应的菜单标输入边数和顶点数：2 3请输入有边的2个顶点1 2 请输入工与2之间的权值 请输入有边的2个顶点1 3金爵之间的权值源0 1110 01 0权排序之后的为士 1, 2 2最小生瞬扰二 1, 2 2 lr 3 4li青按任意谨也续.克鲁斯卡尔算法错误结果:kruskal请选择相应的菜单储输入边数和顶点数 1 请输入有边的2个顶点工1 请输入1与1之间的极值再请输入有边的a个顶点11请辄入1与1之间的权值需邻曩矩阵为:心排序之后的为: -858993460r -858993460 -858993460展小生成树为:六、体会与自我评价“数据结构”是计算机程序设计的重要理论技术基础，它不仅是计算机学科 的核心课程，而且已成为其他理工专业的热门选修课。本学期通过学习这门课程， 我学会了分析研究计算机加工的数据结构的特性，以及算法的事件分析和空间分析。这些帮助我在设计程序的过程中，更好为数据选择适当的逻辑结构、存储结 构及其相应的算法。通常情况下，交通、道路问题的数学模型是一种称为“图”的数据结构。在 本课题中，每个顶点代表一个城市，每一条边代表一条通信录井，同时给每条路 径赋予权值，代表着这条路径的建设代价。 通过最小生成树的实现，可以实现以 最节省经费的方式来建立这个通信网。 对于n个顶点的联通网可以建立许多不同 的生成树，每一棵生成树都可以是一个通信网。 但是根据要求，我们需要以最少 的经费来完成整个通信网的建设，于是便有了最小生成树问题。为了完成本次课程设计，因为课本上只有 prim算法的代码，所以克鲁斯卡 尔算法还需要自己使用百度进行查找。 在查找到算法

《最小生成树实验报告材料》由会员m****分享，可在线阅读，更多相关《最小生成树实验报告材料》请在金锄头文库上搜索。