《最小生成树课程设计(共19页).doc》由会员分享，可在线阅读，更多相关《最小生成树课程设计(共19页).doc（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上湖南人文科技学院计算机科学技术系课程设计说明书 课 程 名 称: 数据结构 课 程 代 码: 题 目: 最小生成树问题 年级/专业/班: 08级计算机科学与技术一班 学 生 姓 名: 肖禁 吴广 刘聪 邱建标 胡子龙 学 号: 指 导 教 师: 袁 辉 勇 开 题 时 间: 2009 年 12 月 23 日完 成 时 间: 2010 年 1 月 1 日目 录 摘 要最小生成树是数据结构中图的一种重要应用，在图中对于n个顶点的连通网可以建立许多不同的生成树，最小生成树就是在所有生成树中总的代价最小的生成树。本课程设计是以邻接矩阵作为图的存储结构,分别采用Prim和Kru
2、skal算法求最小生成树。Kruskal算法和Prim算法是求最小生成树的常用算法它们分别适用于稠密图和稀疏图。最小生成树的应用非常的广，如矿井通风设计和改造最优化方面以及如何搭建最短的网络线缆, 构建造价最低的通讯网络 。关键词：最小生成树；Kruskal算法；Prim算法Abstract The minimum Cost spanning tree data structure is an important application of Chinese, in the picture for n vertex even TongWang can create many different
3、 spanning tree, minimum spanning tree is in all spanning tree in the total cost of the minimum spanning tree. This course is designed as a figure of the adjacency matrix storage structure, we adopt Prim and Kruskal minimum spanning tree algorithm. Kruskal Prim algorithm and minimum spanning tree alg
4、orithm is used for the algorithm respectively applicable and sparsely populated. Minimum spanning tree is very wide application in mines, such as the ventilation design and modification and optimization in how to set up the shortest cable network, constructing the lowest cost of communications netwo
5、rkKeywords: Minimum Cost Spanning Tree；Kruskal algorithm；Prim algorithm 数据结构课程设计-最小生成树 一、引 言数据结构是计算机科学与技术专业和信息管理与信息系统专业的必修课之一，是一门综合性的专业基础课。本课程较系统地介绍了软件设计中常用的数据结构以及相应的实现算法，如线性表、栈、队列、树和二叉树，图、检索和排序等，并对性能进行分析和比较，内容非常丰富。本课程设计我们要解决的问题是图最小生成树问题。要用到图的先相关数据结构和求最小生成树的两种数据结构算法普里姆算法和克鲁斯卡尔算法，以及储存图的边和点的邻接矩阵。本课程设计
6、要解决的问题构造连通网的最小生成树 ,我们首先要做的是创建一个邻接矩阵，用以来存储图，然后我们要想好怎样利用普里姆算法和克鲁斯卡尔算法来构造最小生成树。把这两种算法写入主函数，调试好程序。最后写好报告。二、设计目的与任务1、课程设计目的 本课程设计的目的是了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发。 2、课程设计的任务 问题描述: 已知一个无向连通网表示n个城市以及城市间可能设置的通信线路，其中
7、网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于n个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。我们要选择一棵生成树，使总的耗费最小。 三、设计方案1、需求分析1)建立一个图，其存储方式可以采用邻接矩阵形式，需要定义两个数组，一个存储顶点，一个存储边，存储边的数组表明节点间的连通关系和边的权值；。2)利用普里姆算法和克鲁斯卡尔算法求网的最小生成树3)按顺序输出生成树中各条边以及它们的权值。2、概要设计1) 抽象数据类型(ADT)如下：ADT Graph 数据对象V：v是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R=VR VR=|v
8、,w属于v且p(v,w),(v,w)表示从v到w的弧，谓词p(v,w)定义了弧的意义或信息 基本操作：(1) CreatGraph(&G,V,VR)；初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和VR的定义构造图G。(2) LocateVex(G, u)； 初始条件：图G存在,u和G中顶点有相同的特征。操作结果：若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。(3) DestoryGraph(&u)；初始条件：图G存在。操作结果：销毁图G。(4) GetVex(G, v)；初始条件：图G存在，v是图中某个顶点。操作结果：返回v的值。(5) NextAdjVex(G
9、, 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;AdjMatrixMAXMAX;Typedef struct djMatrix arc; int vexnum, arcnum;
10、 MGraph;3) 流程图2、用prim算法求解最小生成树3、用kruskal算法最最小生成树功能选择开 始1、建立邻接矩阵结 束3、详细设计在该函数中主要有五段代码块，分别是主函数代码块、邻接矩阵定义模块代码、创建链接矩阵模块代码、最小生成树Prim算法及代价模块代码与最小生成树kruskal算法及代价模块代码，五段代码块分别有着不同的作用，共同满足了课题所需要实现的功能。 1) 主函数模块代码algraph gra; MGraph_L G; int i,d,g2020;char a=a; d=creatMGraph_L(G); vnode v;coutendl注意：若该图为非强连通图(含
11、有多个连通分量)时endl 最小生成树不存在,则显示为非法值endlendl;cout菜单endlendl;cout0、显示该图的邻接矩阵endl;cout1、最小生成树PRIM算法及代价endl;int s; char y=y;while(y=y) cout请选择菜单：s; switch(s)case 0: cout邻接矩阵显示如下：endl; ljjzprint(G); break; case 1: for(i=0;i!=G.vexnum;+i) for(intj=0;j!=G.vexnum;+j) gi+1j+1=G.arcsij.adj; coutprim:endl; prim(g,d
12、); break; coutendly; if(y=n) break; 该主函数用一个循环语句，来执行其它的函数的功能。从键盘输入顶点数和边数上限，再调用定义连接矩阵的函数，后输出创建连接矩阵的信息，再调用creatMGraph（）函数，接着进入菜单，然后再选择输入一个数确定是要输出连接矩阵还是最小生成树及代价，最后选择输入确定字母y或N确定是否继续。 2) 邻接矩阵定义模块代码typedef struct ArcCell int adj; char *info;ArcCell,AdjMatrix2020;typedef struct char vexs20; AdjMatrix arcs;
13、int vexnum,arcnum;MGraph_L;int localvex(MGraph_L G,char v) int i=0; while(G.vexsi!=v) +i; return i;用typedef struct定义连接矩阵，通过二维数组来存储连接矩阵，并设定参数的最大值为20。3) 创建链接矩阵模块代码 int creatMGraph_L(MGraph_L &G) char v1,v2; int i,j,w; cout创建无向图（城市分布图）endl;cout 请输入图G顶点（城市）和弧（边）的个数:(4 6)不包括“()”G.vexnumG.arcnum; for(i=0;
14、i!=G.vexnum;+i) cout输入顶点（城市）iG.vexsi; for(i=0;i!=G.vexnum;+i)for(j=0;j!=G.vexnum;+j) G.arcsij.adj=int_max; G.arcsij.info=NULL; for(int k=0;k!=G.arcnum;+k) cout输入一条边依附的顶点（城市）和权（距离）:(a b 3)不包括“()”v1v2w; i=localvex(G,v1); j=localvex(G,v2); G.arcsij.adj=w; G.arcsji.adj=w; cout图G邻接矩阵创建成功！endl; return G.v
15、exnum;该语句是从键盘输入顶点数和边数，输入顶点和权值，通过循环语句的调用，最后调用creatMGraph_L（）创建连接矩阵 。4) 最小生成树Prim算法及代价模块代码 int prim(int gmax,int n) int lowcostmax,prevexmax; int i,j,k,min;int sum=o; for(i=2;i=n;i+) lowcosti=g1i; prevexi=1; lowcost1=0; for(i=2;i=n;i+) /形成n-1条边的生成树 min=inf; k=0; for(j=2;j=n;j+) if(lowcostjmin)&(lowcos
16、tj!=0)min=lowcostj; k=j; printf(%d,%d)%dt,prevexk-1,k-1,min); sum+=min; lowcostk=0; for(j=2;j=n;j+) if(gkjlowcostj) lowcostj=gkj; prevexj=k; printf(n); cout最少生成树的代价:; coutsum; return 0; 该语句运用一系列的循环语句来实现的，利用前面的创建好的链接矩阵，通过各边权值的比较，最后调用prim()函数，实现最小生成树的生成，同时运用sum把最小生成树各边权值相加得到最小生成树的代价。5) 最小生成树kruskal算法及
17、代价模块代码 void MiniSpanTree(MGraphA *D)/生成最小生成树 int i, j, n, m, SUM=0; int k = 1;int parentM; edge edgesM;for ( i = 1; i vexnum; i+) for (j = i + 1; j vexnum; j+) if (D-arcij.adj = 1) edgesk.begin = i; edgesk.end = j; edgesk.weight = D-arcij.weight; k+;sort(edges, D);for (i = 1; i arcnum; i+) parenti =
18、 0; printf(最小生成树为:n);for (i = 1; i arcnum; i+)/核心部分 n = Find(parent, edgesi.begin); m = Find(parent, edgesi.end);if (n != m) parentn = m; printf( %dn, edgesi.begin, edgesi.end, edgesi.weight);SUM=SUM+edgesi.weight;cout最少生成树的代价:; coutSUM.该语句运用一系列的循环语句来实现的，利用前面的创建好的链接矩阵，通过各边权值的比较，最后调用MiniSpanTree ()函数
19、，实现最小生成树的生成，同时运用sum把最小生成树各边权值相加得到最小生成树的代价。4、程序清单#include #include using namespace std; #define int_max 10000#define inf 9999 #define max 20#define MAX 20#define M 20typedef struct ArcCellint adj;char *info;ArcCell,AdjMatrix2020;typedef struct char vexs20;AdjMatrix arcs; int vexnum,arcnum;MGraph;int
20、localvex(MGraph G,char v) int i=0; while(G.vexsi!=v) +i; return i;void ljjzprint(MGraph G) int i,j,n=0; printf(建立的邻接矩阵如下：n); printf(n); printf( _n); for(i=0;i!=G.vexnum;i+) for(j=0;j!=G.vexnum;j+) if(j=0)printf( ); printf(%d,G.arcsij.adj);printf( );n+; if(n=G.vexnum) printf(n);n=0; printf( _n);int c
21、reatMGraph(MGraph &G)char v1,v2; int i,j,w; printf(建立邻接矩阵:n); printf(请输入图G顶点（城市）和弧（边）的个数:); scanf(%d,&G.vexnum); scanf(%d,&G.arcnum); printf(输入所有顶点:); for(i=0;iG.vexsi; for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsij.adj=int_max; G.arcsij.info=NULL; printf(输入所有边及依附的顶点（城市）和权（距离）:n);for(int k=0;k
22、v1v2w; i=localvex(G,v1); j=localvex(G,v2); G.arcsij.adj=w; G.arcsji.adj=w; ljjzprint(G); printf(图G邻接矩阵创建成功！n); return G.vexnum; int visitedmax; int we;typedef struct arcnode int adjvex; struct arcnode *nextarc; char *info; arcnode;typedef struct vnode char data; arcnode *firstarc; vnode,adjlist;type
23、def struct/图的定义 adjlist verticesmax; int vexnum, arcnum; int kind; algraph;int prim(int gmax,int n) /最小生成树PRIM算法 int lowcostmax, prevexmax; int i,j,k,min; int sum=0; for(i=2;i=n;i+) lowcosti=g1i; prevexi=1; lowcost1=0; for(i=2;i=n;i+) min=inf; k=0; for(j=2;j=n;j+) if(lowcostjmin)&(lowcostj!=0) min=l
24、owcostj; k=j; printf(%d,%d)%dt,prevexk-1,k-1,min); sum+=min;lowcostk=0; for(j=2;j=n;j+) if(gkjlowcostj) owcostj=gkj;prevexj=k; printf(n); cout最少生成树的代价:; coutarcnum,&D-vexnum);for (i = 1; i vexnum; i+)/初始化图for ( j = 1; j vexnum; j+) D-arcij.adj = D-arcji.adj = 0;for ( i = 1; i arcnum; i+)/输入边和权值print
25、f(n请输入有边的2个顶点); scanf(%d %d,&n,&m);while(n D-vexnum | m D-vexnum)printf(输入的数字不符合要求 请重新输入:); scanf(%d%d,&n,&m); D-arcnm.adj = D-arcmn.adj = 1; getchar();printf(n请输入%d与%d之间的权值:, n, m); scanf(%d,&D-arcnm.weight);printf(邻接矩阵为:n);for ( i = 1; i vexnum; i+)for ( j = 1; j vexnum; j+)printf(%d ,D-arcij.adj)
26、; printf(n);void sort(edge edges,MGraphA *D)/对权值进行排序int i, j;for ( i = 1; i arcnum; i+)for ( j = i + 1; j arcnum; j+)if (edgesi.weight edgesj.weight) Swapn(edges, i, j);printf(权排序之后的为:n);for (i = 1; i arcnum; i+)printf( %dn, edgesi.begin, edgesi.end, edgesi.weight);void Swapn(edge *edges,int i, int
27、j)/交换权值 以及头和尾int temp; temp = edgesi.begin;edgesi.begin = edgesj.begin; edgesj.begin = temp; temp = edgesi.end;edgesi.end = edgesj.end; edgesj.end = temp;temp = edgesi.weight; edgesi.weight = edgesj.weight;edgesj.weight = temp;void MiniSpanTree(MGraphA *D)/生成最小生成树int i, j, n, m,SUM=0; int k = 1;int
28、parentM; edge edgesM;for ( i = 1; i vexnum; i+)for (j = i + 1; j vexnum; j+)if (D-arcij.adj = 1)edgesk.begin = i; edgesk.end = j; edgesk.weight = D-arcij.weight; k+; sort(edges, D);for (i = 1; i arcnum; i+)parenti = 0; printf(最小生成树为:n);for (i = 1; i arcnum; i+)/核心部分n = Find(parent, edgesi.begin); m
29、= Find(parent, edgesi.end);if (n != m) parentn = m; printf( %dn, edgesi.begin, edgesi.end, edgesi.weight); SUM=SUM+edgesi.weight;cout最少生成树的代价:; cout 0) f = parentf;return f;void main() algraph gra; MGraph G; MGraphA *D; int i,d,m,g2020; char a=a; int s; char y=y; while(y=y) printf( 最小生成树的求法n); print
30、f( _n); printf( | 1.建立邻接矩阵(无向图) |n); printf( | 2.用prim算法求最小生成树(无向图) |n); printf( | 3.用kruskal算法求最小生成树 |n); printf( |_ |n); printf( _请选择相应的菜单(1-3) :); cins; switch(s) case 1: d=creatMGraph(G); vnode v; coutendl注意：若该图为非强连通图(含有多个连通分量)时endl 最小生成树不存在,则显示为非法值endlendl; break; case 2: coutprim算法求解如下：endl; f
31、or(i=0;i!=G.vexnum;+i) for(int j=0;j!=G.vexnum;+j)gi+1j+1=G.arcsij.adj; prim(g,d); break; case 3: coutkruskal算法求解如下：endl; D = (MGraphA*)malloc(sizeof(MGraphA); CreatGraph(D); MiniSpanTree(D); break; printf(n); coutendly; if(y=n) break; 四、调试分析与体会在我组的集体努力下，课程设计终于完成，由于我们对数据结构和c语言不是很了解，有时忽略了一些关键的细节，使得在编
32、写程序的过程中出现了一些问题。对于打字有时粗心导致出现一些难以发现的小错误，在我们的耐心，细致的调试下最终使得程序能够运行，课程设计完满完工。1、问题一：求出图中的最小值 现象：求出的最小值是0原因：图中没有连通的两个顶点之间的权值赋值为02、问题二：求最小生成树时，else语句需再调用一个函数 现象：对某些二叉树能求出最小生成树，但不能普遍适应原因：对于找最小生成树边的各种可能没有考虑全面，代码才没有广泛的适应性3、问题三：两个顶点之间的边是否是最小生成树的边现象：代码的功能不能分辨出是否是最小生成树的边原因：把简单的代码写的很复杂，从而杂乱无章出现错误。五、运行结果将程序员录入后,让其运行
33、。将会出现一个菜单的界面，执行各种操作均有其对应的代码。要执行何种操作只需输入对应的指令即可进行，在每步操作后均会有相应的提示。操作简单方便实用，下面即为一些操作的示意图。运行程序后出界面，运行结果如图1所示。图1 初界面图中有1-3三个选项，可选取其中的一个选项进行操作。选取选项1进行操作，运行结果如图2所示。图2 建立邻接矩阵依据提示，分别输入无向图的顶点个数与弧的个数，然后依次输入各个顶点所对应的符号及与各个顶点相关联的弧与权值，存在邻接矩阵中。若选取选项3，运行结果如图4所示。 图3 求的最小生成树图中显示了求得的最小生成树所对应的边、权值与最小生成树的代价。六、结 论经过我们不懈的努
34、力我们终于完成了本次课程设计，通过这次课程设计，我感觉到要真正做出一个程序并不很容易，但只要用心去做，总会有收获，特别是当我遇到 一个问题，想办法去解决，最后终于找到方法时，心里的那份喜悦之情真是难以形容。编写程序中遇到问题再所难免，应耐心探究其中的原因，从出现问题的地方起，并联系前后程序，仔细推敲，逐个排查。直到最终搞清为止。我们本次做的是图的做小生成树问题，深刻的体会到它的实用性。通过本次课程设计我们发现我们对于C语言和数据结构还有很多地方不知道，今后需要努力学习。七、致 谢在这里我真心的感谢袁辉勇老师对我们精心的指导和不倦的教育,他在我们的课程设计过程中提出了指导性的方案和架构,时事关注
35、我们设计的进程，并指引我们阅读相关的资料和书籍，使我们的课设能够按时顺利的完成。还有吴广同学全面承担本次课程设计的程序编写工作,并为此付出大量的时间和精力。在这里我代表我们组全体同学对他表示感谢,同时也组员的积极配合与协作。同时也感谢学校给我们这次机会，训练我们灵活应用所学数据结构知识，独立完成问题分析的能力，让我们学会怎样结合数据结构理论知识去解决实际问题。八、参考文献1 严蔚敏. 数据结构（C语言版）M. 北京：清华大学出版社,1997.2 谭浩强. C程序设计（第三版）M. 北京：清华大学出版社，2005.1. 3 二霍红卫算法设计与分析西安西安电子科技大学出版社，2005.113-12
36、7.4 陈杰.计算机专业课程设计中的需求分析J.集美大学学报，2009，10(2)：8992.5 高一凡. 数据结构算法实现及解析M . 西安:西安电子科技大学出版社, 2002课程设计任务书及成绩评定课题名称： 最小生成树问题 完 成 者：肖禁 吴广 邱健标 刘聪 胡子龙 1、设计的目的与要求： 1) 灵活应用所学数据结构知识，独立完成问题分析。2) 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等方法。3) 训练用系统的观点和软件开发一般规范进行软件开发。4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力。2、设计进度及完成情况日 期内 容6.19分析问题，找出所要解决问题的关键6.206.21总体设计，找出解决方案6.22详细设计，列出解决步骤6.236.24程序编码6.256.26程序调试，修改加以完善6.27书写文档3、成绩评定：设计成绩： （教师填写）指导老师： （签字）二00 年 月 日专心-专注-专业