数据结构课程设计-最小生成树

数据结构课程设计报告 最小生成树数据结构课程设计报告 设计题目：最小生成树专 业： xxxxxx院 系： 计算机学院姓 名： xxxxxxxxx学 号： xxxxxx时间：2013年10月7日目 录一、设计目的.-2-二、算法思想分析-2-1.算法思想.-3-1）普里姆（Prim）算法思想.-3-2）克鲁斯卡尔（Kruskal）算法思想.-3-2.系统采用的数据结构和算法-3-三、算法的描述与实现.-4-四、用户手册-7-五、总结.-10-六、参考文献.-10-七、附录（源代码）.-10- 摘要 选择一颗生成树，使之总的消费最少，也就是要构造连通网的最小代价生成树（简称为最小生成树）的问题，一颗生成树的代价就是树上各边的代价之和，构造最小生成树可以有多种算法，其中多数算法利用了MST的性质。关键词：最小生成树 连通图 普里姆算法 克鲁斯卡尔算法 MST一、 设计目的1. 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。二、 算法思想分析该设计的要求是在n个城市之间建设网络，不仅要保证连通，还要求是最经济的架设方法。根据克鲁斯卡尔和普里姆算法的不同之处，该程序将城市个数大于十个时应用普里姆算法求最小生成树，而城市个数小于十个时则应用克鲁斯卡尔进行计算。1. 算法思想1) 普里姆（Prim）算法思想a) 选择从0节点开始，并选择0节点相关联的最小权值边，将与这条边相关联的另一顶点出列；b) 在出列的节点中相关联的所有边中选择一条不与另一个已出列的节点相关联的权值最小的边，并将该边相关联的节点出列；c) 重复b)直到所有的节点出列。2) 克鲁斯卡尔（Kruskal）算法思想为了使生成树上总的权值之和最小，应该使每一条边上的权值尽可能的小，所以应从权值最小的边选起，直至选出n-1条不能构成回路的权值最小的边位置。具体做法如下：首先构造一个含n个顶点的森林，然后按权值从小到大从连通图中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通图的最小生成树。由于生成树上不允许有回路，因此并非每一条居当前最小的边都可选。从生成树的构造过程可见，初始态为n个顶点分属n棵树，互不连通，每加入一条边，就将两棵树合并为一棵树，在同一棵树上的两个顶点之间自然相连通，由此判别当前权值最小边是否可取只要判别它的两个顶点是否在同一棵树上即可。2. 系统采用的数据结构和算法1) 数据结构Typedef int Vertextype;Typedef int adimatrixMaxVertexNumMaxVertexNum;Typedef int Vertextype vexlistMaxVertexNum;Typedef int VexType;Typedef int AdjType;Typedef struct edgeElem edgesetMaxVertexNum;struct edgeElemint fromvex;/头顶点int endvex;/尾顶点int weight;/权;Typedef structint n;/图的顶点个数AdjType acrsMAXVEXMAXVEX;/边信息GraphMatrix;Typedef structint start_vex,stop_vex;/边的起点和终点AdjType weight;/边的权Edge;Edge mst5;2) 算法Great_adjmatrix();Great_adjmatrix2();Kruskal();out_edgeaet();prim();三、 算法的描述与实现1. Great_adjmatrix()和Great_adjmatrix2()是两种建立图的方法；2. 克鲁斯卡尔算法（Kruskal）：Void kruskal(GraphMatrix * pgraph,Edge mst)int i,j,min,vx,vy;int weight,minweight;Edge edge;for(i=0;in-1;i+)msti.start_vex = 0;Msti.stop_vex = i+1;Msti.weight = pgraph-arcs0i+1;for(i=0;in-1;i+)/共n-1条边minweight = MAX;min = i;for(j=i;jn-1;j+)/从所有（vx,vy）（vxU,vyV-U）中选出最短的边if(mstj.weightminweight)minweight = mstj.weight;min = j;/mstmin是最短的边(vx,vy)(vxU,vyV-U),将mstmin加入最小生成树edge = mstmin;mstmin = msti;msti = edge;vx = msti.stop_vex;/vx为刚加入最小生成树的顶点的下标for(j=i+1;jn-1;j+)vy=mstj.stop_vex;weight=pgraph-arcsvxvy;if(weightmstj.weight)mstj.weight=weight;mstj.start_vex = vx;3. 普里姆算法（Prim）：void prim(adjmatrix GA,edgeset MST,int n)/利用prim算法从0点出发求图的最小生成树int i,j,t,k,w,min,m;struct edgeElem x;for(i=0;i0) /从0点连接其余顶点MSTi-1.fromvex=0;MSTi-1.endvex=i;MSTi-1.weight=GA0i;for(k=1;kn;k+)min=MaxValue;m=k-1;for(j=k-1;jn-1;j+)if(MSTj.weightmin)min=MSTj.weight;M=j;/选择从0点出发权值最小的边x=MSTk-1;MSTk-1=MSTm;MSTm=x;/交换位置j=MSTk-1.endvex;/定位于权值最小边的尾顶点for(i=k;in-1;i+)/选取轻边t=MSTi.endvex;w=GAjt;if(wMSTi.weight)MSTi.weight=w;MSTi.fromvex=j;4. out_edgeset()功能为显示最小生成树。四、 用户手册1.运行程序，得到如下窗口：2.输入顶点数，选择算法：1）当输入的顶点数小于10时，选择Kruskal算法，如下图2）当输入的顶点数大于10时，选择Prim算法，如下图五、总结该程序实现了在n个城市之间建设网络，既保证了连通性，也成为了最经济的架设方法。程序中应用了普里姆算法和克鲁斯卡尔算法，实现了矩阵的输出以及最小生成树的输出。不过，该程序仍有不足之处，图的输入数据过大，易出错，不易返回，仍需完善。六、参考文献1 数据结构程序设计题典 李春葆编 清华大学出版社2 数据结构（C语言版） 严蔚敏 吴伟民编 清华大学出版社3 数据结构课程设计 苏仕华编 机械工业出版社七、附录：（源代码）#include#include#define MaxVertexNum 12#define MaxEdgeNum 20#define MaxValue 1000#define MAXVEX 6#define MAX 1e+8typedef int Vertextype;typedef int adjmatrixMaxVertexNumMaxVertexNum;typedef Vertextype vexlistMaxVertexNum;typedef int VexType;typedef int AdjType;typedef struct edgeElem edgesetMaxVertexNum; struct edgeElemint fromvex;/头顶点int endvex;/尾顶点int weight;/权;typedef struct int n; /* 图的顶点个数 */ /*VexType vexsMAXVEX; 顶点信息 */ AdjType arcsMAXVEXMAXVEX; /* 边信息 */ GraphMatrix;typedef struct int start_vex, stop_vex; /* 边的起点和终点 */ AdjType weight; /* 边的权 */ Edge;Edge mst5;void Creat_adjmatrix(vexlist GV,adjmatrix GA,int n,int e) int i,j,k,w; printf(输入%d个顶点序号(0-n-1)：,n); for(i=0;in;i+) /建立顶点表 scanf(%d,&GVi);/读入顶点信息 for(i=0;in;i+)/建立边表 for(j=0;jn;j+)/初始化边表 if(i=j) GAij=0; else GAij=MaxValue; printf(输入%d条无向带权边（序号 序号 权值）：n,e); for(k=0;ke;k+)/设置边表 scanf(%d%d%d,&i,&j,&w); GAij=GAji=w;/对称 void Creat_adjmatrix2(vexlist GV,adjmatrix GA,int m,int e,GraphMatrix &graph) int i,j,k,w,x,y; printf(输入%d个顶点序号(0-m-1)，序号从0开始。,m); for(i=0;i=m) printf(您输入的序号有误，请输入0到%d-1之间的数，请重新输入。n,m); scanf(%d,&GVi); for(i=0;im;i+)/建立边表 for(j=0;jm;j+)/初始化边表 GAij=MaxValue; printf(请输入有多少条边。n); scanf(%d,&e); printf(输入%d条无向带权边（序号 序号 权值）：n,e); for(k=0;ke;k+)/设置边表 scanf(%d%d%d,&i,&j,&w); GAij=GAji=w;/对称 printf(您输入的图的存贮为下面表，如果不可达则用1000表示。n); graph.n =m; for(x=0;xm;x+) for(y=0;ym;y+) graph.arcsxy=GAxy; printf(%-4d ,graph.arcsxy); printf(n); void kruskal(GraphMatrix * pgraph, Edge mst) int i, j, min, vx, vy; int weight, minweight; Edge edge; for (i = 0; i n-1; i+) msti.start_vex = 0; msti.stop_vex = i+1; msti.weight = pgraph-arcs0i+1; for (i = 0; i n-1; i+) /* 共n-1条边 */ minweight = MAX; min = i; for (j = i; j n-1; j+)/* 从所有边(vx,vy)(vxU,vyV-U)中选出最短的边 */ if(mstj.weight minweight) minweight = mstj.weight; min = j; /* mstmin是最短的边(vx,vy)(vxU, vyV-U)，将mstmin加入最小生成树 */ edge = mstmin; mstmin = msti; msti = edge; vx = msti.stop_vex; /* vx为刚加入最小生成树的顶点的下标 */ for(j = i+1; j n-1; j+) /* 调整msti+1到mstn-1 */ vy=mstj.stop_vex; weight = pgraph-arcsvxvy; if (weight mstj.weight) mstj.weight = weight; mstj.start_vex = vx; void out_edgeset(edgeset MST,int e)/显示最小生成树 int k; printf(最小的消耗路线为n); for(k=0;ke;k+) printf(%d %d %d)n,MSTk.fromvex,MSTk.endvex,MSTk.weight);void prim(adjmatrix GA,edgeset MST,int n)/利用prim算法从0点出发求图的最小生成树 int i,j,t,k,w,min,m; struct edgeElem x; for(i=0;i0)/从0点连接其余顶点 MSTi-1.fromvex=0; MSTi-1.endvex=i; MSTi-1.weight=GA0i; for(k=1;kn;k+) min=MaxValue; m=k-1; for(j=k-1;jn-1;j+) if(MSTj.weightmin) min=MSTj.weight;m=j;/选择从0点出发权值最小的边 x=MSTk-1;MSTk-1=MSTm;MSTm=x;/交换位置 j=