最小生成树

最小生成树 湖南人文科技学院计算机科学技术系 课程说明书 课 程 名 称: 数据结构 课 程 代 码: 题 目: 最小生成树问题 年级/专业/班: 08级计算机科学与技术一班 学 生 姓 名: 肖禁 吴广 刘聪 邱建标 胡子龙 学 号:08408110 0840807 08408109 08408106 08408108 指 导 教 师: 袁 辉 勇 开 题 时 间: 2009 年 12 月 23 日 完 成 时 间: 2009 年 1 月 1 日 摘 要..................................................................2 一、引 言 ..............................................................3 二、设计目的与任务 .................................... 3 1、课程设计的目的 ...................................................3 2、课程设计的任务 ...................................................3 三、设计方案 ............................................................4 1、需求分析 .........................................................4 2、总体设计 .........................................................4 3、详细设计 .........................................................9 4、程序清单 .........................................................9 四、调试分析与体会 ..................................................... 26 五、运行结果 ........................................................... 27 六、结 论 ............................................................. 29 七、致 谢 ............................................................. 29 八、参考文献 ........................................................... 29 1 本课程设计通过代码实现将理论知识和具体实践相结合，巩固提高了对对数据结 构的相关方法与概念的理解，使学生的发散思维及动手能力进一步加强，加强对计算 机及软件的进一步了解。 在本次课程设计中,我们要研究的是最小生成树问题, 建立一个图，采用邻接矩阵 存储方式,利用普里姆算法和克鲁斯卡尔算法求网的最小生成树 。利用最小生成树我 们可以解决许多实际问题。它的功能是给定一个图得出最小代价。如在建立通信联络 网，使建立通信网的经费最小，它的用途很广。 数据结构；最小生成树 X Abstract This course design through code to theoretical knowledge and practice, combining consolidate improved on data structures related methods and the understanding of concepts, make the students' divergent thinking ability and to further strengthen the computer and software, to strengthen the further understanding of the project. In this course, we will study in the design of the problem is Minimum Cost Spanning Tree, establish a diagram, using adjacency matrix of storage ways, use Prim algorithm and Kruskal algorithm of minimum spanning tree. Using the Minimum Cost Spanning Tree, we can solve many problems. Its function is given a figure that the lowest cost. As in establishing communications network, As in establishing communications network, establish the chain funds, Its purpose is very wide。 Keywords: Data Structure；Minimum Cost Spanning Tree； 2 一、 《数据结构》是计算机科学与技术专业和信息管理与信息系统专业的必修课之一，是 一门综合性的专业基础课。本课程较系统地介绍了软件设计中常用的数据结构以及相应的 实现算法，如线性表、栈、队列、树和二叉树，图、检索和排序等，并对性能进行分析和 比较，非常丰富。 它是学习操作系统、编译原理、数据库原理等计算机专业核心课 程的基础，掌握好这门课程的内容，是学习计算机其他相关课程的必备条件。因此，该课 程在专业建设的地位十分重要。 本课程设计我们要解决的问题是图最小生成树问题。要有到图和求最小生成树的 两种数据结构算法普里姆算法和克鲁斯卡尔算法，以及储存图的边和点的邻接矩阵。(简要介绍本课程设计用到的数据结构) 本题要做的是构造连通网的最小生成树的问题,我们首先要做的是创建一个邻接矩 阵，用以来存储图，然后我们要想好怎样利用普里姆算法和克鲁斯卡尔算法来构造最小生 成树。把这两种算法写入主函数，调试好程序。最后写好报告。 (简要介绍本课程设计所做的工作) 1 1．了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 3 2．初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3．提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4．训练用系统的观点和软件开发一般进行软件开发。 2 问题描述：已知一个无向连通网表示n个城市以及城市间可能设置的通信线路，其中网的 顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于n个点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，我 们要选择这样一棵生成树，使总的耗费最小。即构造连通网的最小生成树的问题。 1 1) 建立一个图，其存储方式可以采用邻接矩阵形式，需要定义两个数组，一个存储 顶点，一个存储边，存储边的数组表明节点间的连通关系和边的权值；。 2) 利用普里姆算法和克鲁斯卡尔算法求网的最小生成树 3) 按顺序输出生成树中各条边以及它们的权值。 2 1) 抽象数据类型(ADT)如下： { v是具有相同特性的数据元素的集合，称为顶点集。 R={VR} VR={|v,w属于v且p(v,w),(v,w)表示从v到w的弧，谓词 p(v,w)定义了弧的意义或信息} (1) CreatGraph(&G,V,VR)； 初始条件：V是图的顶点集，VR是图中弧的集合。 操作结果：按V和VR的定义构造图G。 4 (2) LocateVex(G, u)； 初始条件：图G存在,u和G中顶点有相同的特征。 操作结果：若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他 信息。 (3) DestoryGraph(&u)； 初始条件：图G存在。 操作结果：销毁图G。 (4) GetVex(G, v)； 初始条件：图G存在，v是图中某个顶点。 操作结果：返回v的值。 (5) NextAdjVex(G, v, w)； 初始条件：图G存在，v是图中某个顶点，w是v的邻接顶点。 操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个 邻接点，则返回“空”。 (6) BFSTraverse(G, Visit( ))； 初始条件：图G存在，Visit是顶点的应用函数。 操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit 一次且仅一次。一旦visit( )失败，则操作失败。 } 2) 存储结构 Typedef struct { int adj; int weight; }AdjMatrix[MAX][MAX]; Typedef struct { AdjMatrix arc; int vexnum, arcnum; } MGraph; 3) 流程图 5 （1）主函数程序流程图 开始 输入顶点和弧的个数 输入一条边依附的顶点和权 否 是否为强连通图（含有 多个连同分量） 是 菜单 0 1 显示该图的连接矩阵 最少生成树PRIM算法及代价 是否继续： 是否继续： y/n y/n n n y y 结束 菜单 菜单 结束 （2）.创建邻接矩阵流程图 6 开始 输入顶点和弧的个数 输入一条边依附的顶点和权 否 是否为强连通图（含有 多个连同分量） 是 图G邻接矩阵创建 成功！ 结束 （3）. 最小生成树Prim算法程序流程图 7 开始 菜单 1 0 1/0? 最小生成树PRIM算法及代价 该图的邻接矩阵 y/n? y/n? y n y n 菜单 结束 菜单 结束 8 3 在该函数中主要有五段代码块，分别是主函数代码块、邻接矩阵定义模块代码、创建链接 矩阵模块代码、最小生成树Prim算法及代价模块代码与最小生成树kruskal算法及代价模 块代码，五段代码块分别有着不同的作用，共同满足了课题所需要实现的功能。 1) 主函数模块代码 { algraph gra; MGraph_L G; int i,d,g[20][20]; char a='a'; d=creatMGraph_L(G); vnode v; cout<>s; switch(s) { case 0: cout<<"邻接矩阵显示如下："<>y; if(y=='n') break; } } 程序解释：该主函数用一个循环语句，来执行其它的函数的功能。从键盘输入顶点数和边数 上限，再调用定义连接矩阵的函数，后输出创建连接矩阵的信息，再调用creatMGraph（）函 数，接着进入菜单，然后再选择输入一个数确定是要输出连接矩阵还是最小生成树及代价， 最后选择输入确定字母y或N确定是否继续。 2) 邻接矩阵定义模块代码 typedef struct ArcCell { int adj; char *info; }ArcCell,AdjMatrix[20][20]; typedef struct 10 { char vexs[20]; AdjMatrix arcs; int vexnum,arcnum; }MGraph_L; int localvex(MGraph_L G,char v) { int i=0; while(G.vexs[i]!=v) { ++i; } return i; } 程序解释：用typedef struct定义连接矩阵，通过二维数组来存储连接矩阵，并设定参数的最 大值为20。 3) 创建链接矩阵模块代码 int creatMGraph_L(MGraph_L &G) { char v1,v2; int i,j,w; cout<<"„„„„创建无向图（城市分布图）„„„„"<>G.vexnum>>G.arcnum; for(i=0;i!=G.vexnum;++i) { cout<<"输入顶点（城市）"<>G.vexs[i]; } for(i=0;i!=G.vexnum;++i) for(j=0;j!=G.vexnum;++j) 11 { G.arcs[i][j].adj=int_max; G.arcs[i][j].info=NULL; } for(int k=0;k!=G.arcnum;++k) { cout<<"输入一条边依附的顶点（城市）和权（距离）:(a b 3)不包括“()”"<>v1>>v2>>w; i=localvex(G,v1); j=localvex(G,v2); G.arcs[i][j].adj=w; G.arcs[j][i].adj=w; } cout<<"图G邻接矩阵创建成功！"<vexnum; i++) { for (j = i + 1; j <= D->vexnum; j++) { if (D->arc[i][j].adj == 1) { edges[k].begin = i; edges[k].end = j; edges[k].weight = D->arc[i][j].weight; k++; } } } sort(edges, D); for (i = 1; i <= D->arcnum; i++) { parent[i] = 0; } printf("最小生成树为:\n"); for (i = 1; i <= D->arcnum; i++)//核心部分 { n = Find(parent, edges[i].begin); m = Find(parent, edges[i].end); if (n != m) { parent[n] = m; printf("<< %d, %d >> %d\n", edges[i].begin, edges[i].end, edges[i].weight); SUM=SUM+edges[i].weight; } } cout<<"最少生成树的代价:"; cout< #include using namespace std; #define int_max 10000 #define inf 9999 #define max 20 #define MAX 20 #define M 20 typedef struct ArcCell { int adj; char *info; }ArcCell,AdjMatrix[20][20]; typedef struct { char vexs[20]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; int localvex(MGraph G,char v) { int i=0; while(G.vexs[i]!=v) { ++i; } return i; } 15 int creatMGraph(MGraph &G) { char v1,v2; int i,j,w; printf("建立邻接矩阵:\n"); printf("请输入图G顶点（城市）和弧（边）的个数:\n"); scanf("%d",&G.vexnum); scanf("%d",&G.arcnum); for(i=0;i>G.vexs[i]; } for(i=0;i>v1>>v2>>w; //scanf("%c%c%d",&//输入一条边依附的两点及权值 i=localvex(G,v1); j=localvex(G,v2); G.arcs[i][j].adj=w; G.arcs[j][i].adj=w; } 16 printf("图G邻接矩阵创建成功！\n"); return G.vexnum; } void ljjzprint(MGraph G) { int i,j,n=0; for(i=0;i!=G.vexnum;i++) { for(j=0;j!=G.vexnum;j++) cout<arcnum,&D->vexnum); for (i = 1; i <= D->vexnum; i++)//初始化图 { for ( j = 1; j <= D->vexnum; j++) { D->arc[i][j].adj = D->arc[j][i].adj = 0; } } for ( i = 1; i <= D->arcnum; i++)//输入边和权值 { printf("\n请输入有边的2个顶点"); scanf("%d %d",&n,&m); while(n < 0 || n > D->vexnum || m < 0 || n > D->vexnum) { printf("输入的数字不符合要求 请重新输入:"); scanf("%d%d",&n,&m); } 20 D->arc[n][m].adj = D->arc[m][n].adj = 1; getchar(); printf("\n请输入%d与%d之间的权值:", n, m); scanf("%d",&D->arc[n][m].weight); } printf("邻接矩阵为:\n"); for ( i = 1; i <= D->vexnum; i++) { for ( j = 1; j <= D->vexnum; j++) { printf("%d ",D->arc[i][j].adj); } printf("\n"); } } void sort(edge edges[],MGraphA *D)//对权值进行排序 { int i, j; for ( i = 1; i < D->arcnum; i++) { for ( j = i + 1; j <= D->arcnum; j++) { if (edges[i].weight > edges[j].weight) { Swapn(edges, i, j); } } } printf("权排序之后的为:\n"); 21 for (i = 1; i < D->arcnum; i++) { printf("<< %d, %d >> %d\n", edges[i].begin, edges[i].end, edges[i].weight); } } void Swapn(edge *edges,int i, int j)//交换权值 以及头和尾 { int temp; temp = edges[i].begin; edges[i].begin = edges[j].begin; edges[j].begin = temp; temp = edges[i].end; edges[i].end = edges[j].end; edges[j].end = temp; temp = edges[i].weight; edges[i].weight = edges[j].weight; edges[j].weight = temp; } void MiniSpanTree(MGraphA *D)//生成最小生成树 { int i, j, n, m,SUM=0; int k = 1; int parent[M]; edge edges[M]; for ( i = 1; i < D->vexnum; i++) { for (j = i + 1; j <= D->vexnum; j++) { if (D->arc[i][j].adj == 1) { 22 edges[k].begin = i; edges[k].end = j; edges[k].weight = D->arc[i][j].weight; k++; } } } sort(edges, D); for (i = 1; i <= D->arcnum; i++) { parent[i] = 0; } printf("最小生成树为:\n"); for (i = 1; i <= D->arcnum; i++)//核心部分 { n = Find(parent, edges[i].begin); m = Find(parent, edges[i].end); if (n != m) { parent[n] = m; printf("<< %d, %d >> %d\n", edges[i].begin, edges[i].end, edges[i].weight); SUM=SUM+edges[i].weight; } } cout<<"最少生成树的代价:"; cout< 0) { f = parent[f]; } return f; } void main() { algraph gra; MGraph G; MGraphA *D; int i,d,m,g[20][20]; char a='a'; int s; char y='y'; while(y='y') { printf(" „„„„最小生成树的求法„„„„\n"); printf(" ?????????????????????????????? \n"); printf(" ? 最小生成树的求法 ? \n"); printf(" ? 1.建立邻接矩阵(无向图) ? \n"); printf(" ? 2.显示邻接矩阵 ? \n"); printf(" ? 3.用prim算法求最小生成树(无向图) ? \n"); printf(" ? 4.用kruskal算法求最小生成树 ? \n"); printf(" ??????????????????????????????\n"); printf(" 请选择相应的菜单:"); cin>>s; switch(s) { 24 printf(" ?????????????????????????????? \n"); printf(" ? 最小生成树的求法 ? \n"); printf(" ? 1.建立邻接矩阵(无向图) ? \n"); printf(" ? 2.显示邻接矩阵 ? \n"); printf(" ? 3.用prim算法求最小生成树(无向图) ? \n"); printf(" ? 4.用kruskal算法求最小生成树 ? \n"); printf(" ??????????????????????????????\n"); printf(" 请选择相应的菜单:"); case 1: d=creatMGraph(G); vnode v; cout<>y; if(y=='n') break; } } XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 1、问题一：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 现象：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 原因：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 2、问题二：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 现象：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 原因：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 26 3、问题三：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 现象：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 原因：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 4、问题四：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 现象：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 原因：XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 运行程序后出界面，运行结果如图1所示。 图中有1-4四个选项，可任选取其中的一个选项进行运算，但选项2、3、4须是 在无向图建立的基础上进行操作。 选取选项1进行操作，运行结果如图2所示。 27 图2 建立无向图G 依据提示，分别输入无向图的顶点个数与弧的个数，然后依次输入各个顶点所对应的 符号及与各个顶点相关联的弧与权值，存在邻接矩阵中。 在建立好无向图后，就可以对无向图进行操作了，若选取选项2，运行结果如图3所 示。 图3 显示无向图 28 无向图建立后所对应的邻接矩阵。 若选取选项3，运行结果如图4所示。 图中显示了求得的最小生成树所对应的边、权值与最小生成树的代价。 经过我们不懈的努力我们终于完成了本次课程设计，通过这次课程设计，我感觉到 要真正做出一个程序并不很容易，但只要用心去做，总会有收获，特别是当我遇到 一个问题，想办法去解决，最后终于找到方法时，心里的那份喜悦之情真是难以形容。编写程 序中遇到问题再所难免，应耐心探究其中的原因，从出现问题的地方起，并联系前后程序， 仔细推敲，逐个排查。直到最终搞清为止。我们本次做的是图的做小生成树问题，深刻的 体会到它的实用性。通过本次课程设计我们发现我们对于C语言和数据结构还有很多地方不知道，今后需要努力学习。 我们真心的感谢袁辉勇老师对我们精心的指导和不倦的教育,他在我们的课程设计过程中提出了指导性的方案和架构，并指引我们阅读相关的资料和书籍，使我们的课设能够 按时顺利的完成。 同时也感谢学校给我们这次机会，训练我们灵活应用所学数据结构知识，独立完成问 题分析的能力，让我们学会怎样结合数据结构理论知识去解决实际问题。 29 也谢谢我们这组的组员默契的配合，共同完成了这个课程设计。 [1] 严蔚敏. 数据结构（C语言版）[M]. 北京：清华大学出版社,1997. [2] 任丰原, 黄海宁, 林闯. 无线传感器网络[J]. 软件学报, 2003, 14(7):1282-1291. [3] 《数据结构实验教程》，王玲 刘芳等著，成都：四川大学出版社，2002 [4] 谭浩强. C程序设计（第三版）[M]. 北京：清华大学出版社，2005. 30 1、设计的目的与要求： 1) 灵活应用所学数据结构知识，独立完成问题分析。 2) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等方法。 3) 训练用系统的观点和软件开发一般规范进行软件开发。 4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力。 2、设计进度及完成情况 日 期 内 容 6.19 分析问题，找出所要解决问题的关键 6.20—6.21 总体设计，找出解决方案 6.22 详细设计，列出解决步骤 6.23—6.24 程序编码 6.25—6.26 程序调试，修改加以完善 6.27 书写文档 设计成绩： （教师填写） 指导老师： （签字） 二00 年 月 日 31