数据结构最小生成数

1、 数据结构 多元化考核作业 题 目：最小生成树 姓 名： 专业班级：物联网工程B1501班 学 号： 目录一、算法思想3 （1）普尔米算法的思想3 （2）克鲁斯卡尔算法思想3二、系统采用的数据结构和算法3（1）数据结构3（2）算法4三、算法的描述与实现5四、结论12附录：13参考文献：20摘要： 随着社会经济的发展，人们生活已经越来越离不开网络，网络成为人们社会生活的重要组成部分，我们拥有一个宽松的上网环境以便更好交流，在此我梦有必要要传播我们的网络速度，从某中角度来说网络传播速度代表着一个国家网络化的高低。 为了解决网络传输的速度问题我们希望在各个城市之间架设一些通信网络线路；以缓解网络速度

2、传输问题， 通过以上我们得出解决此问题的关键在于找到一个短的路径完成网络的假设，这就用到了我们所学的最小生成树问题。一个连通图的生成树是一个极小的连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。那么我们把构造连通网的最小代价生成树称为最小生成树。概述 课程设计目的1了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。算法思想分析该

3、设计的要求是在n个城市之间建设网络，不仅要保证连通，还要求是最经济的架设方法。根据克鲁斯卡尔算法和普尔米算法的不同之处，该程序将城市个数大于十个时应用普尔米算法求最小生成树，而城市个数小于十个时则应用克鲁斯卡尔进行计算。一、算法思想（1）普尔米算法的思想1）选择从0结点开始，并选择与0结点相关联的最小权值边，将与这条边相关联的另一个顶点出列；2）在出列的结点中相关联的所有边中选择一条不与另一个已出列的节点相关联的权值最小的边，并将该边相关联的结点出列；3）重复2直到所有的结点出列。（2）克鲁斯卡尔算法思想为了使生成树上总的权值之和达到最小，应该使每一条边上的权值尽可能的小，所以应从权值最小的边

4、选起，直至选出n-1条不能构成回路的权值最小的边位置。具体做法如下：首先构造一个含n个顶点的森林，然后按权值从小到大从连通图中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一颗树为止，这棵树便是连通图的最小生成树。由于生成树上不允许有回路，因此并非每一条居当前权值最小的边都可选。从生成树的构造过程可见，初始态为 n 个顶点分属 n 棵树，互不连通，每加入一条边，就将两棵树合并为一棵树，在同一棵树上的两个顶点之间自然相连通。由此判别当前权值最小边是否可取只要判别它的两个顶点是否在同一棵树上即可。二、系统采用的数据结构和算法（1）数据结构typedef int Vertextype;ty

5、pedef 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

6、 arcsMAXVEXMAXVEX; /* 边信息 */ GraphMatrix;typedef struct int start_vex, stop_vex; /* 边的起点和终点 */ AdjType weight; /* 边的权 */ Edge;Edge mst5;（2）算法Creat_adjmatrix()；Creat_adjmatrix2()；Kruskal()；out_edgeset()；prim()三、算法的描述与实现Creat_adjmatrix()和Creat_adjmatrix2()是两种建立图的方法。具体算法如下：void Creat_adjmatrix(vexlist

7、GV,adjmatrix GA,int n,int e) int i,j,k,w; printf("输入%d个顶点序号(0-n-1)：",n); for(i=0;i<n;i+) /建立顶点表 scanf("%d",&GVi);/读入顶点信息 for(i=0;i<n;i+)/建立边表 for(j=0;j<n;j+)/初始化边表 if(i=j) GAij=0; else GAij=MaxValue; printf("输入%d条无向带权边（序号 序号 权值）：n",e); for(k=0;k<e;k+)/设置

8、边表 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;i+) /建立顶点表 scanf("%d",&GVi);/读入顶点信息 if(GVi>=m) printf(

9、"您输入的序号有误，请输入0到%d-1之间的数，请重新输入。n",m); scanf("%d",&GVi); for(i=0;i<m;i+)/建立边表 for(j=0;j<m;j+)/初始化边表 GAij=MaxValue; printf("请输入有多少条边。n"); scanf("%d",&e); printf("输入%d条无向带权边（序号 序号 权值）：n",e); for(k=0;k<e;k+)/设置边表 scanf("%d%d%d",

10、&i,&j,&w); GAij=GAji=w;/对称 printf("您输入的图的存贮为下面表，如果不可达则用1000表示。n"); graph.n =m; for(x=0;x<m;x+) for(y=0;y<m;y+) graph.arcsxy=GAxy; printf("%-4d ",graph.arcsxy); printf("n"); 克鲁斯卡尔的算法如下：void kruskal(GraphMatrix * pgraph, Edge mst) int i, j, min, vx, vy;

11、int weight, minweight; Edge edge; for (i = 0; i < pgraph->n-1; i+) msti.start_vex = 0; msti.stop_vex = i+1; msti.weight = pgraph->arcs0i+1; for (i = 0; i < pgraph->n-1; i+) /* 共n-1条边 */ minweight = MAX; min = i; for (j = i; j < pgraph->n-1; j+)/* 从所有边(vx,vy)(vxU,vyV-U)中选出最短的边 */

12、 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 < pgraph->n-1; j+) /* 调整msti+1到mstn-1 */ vy=mstj.stop_vex; weight = pgraph

13、->arcsvxvy; if (weight < mstj.weight) mstj.weight = weight; mstj.start_vex = vx; 普尔米算法如下：void prim(adjmatrix GA,edgeset MST,int n)/利用prim算法从0点出发求图的最小生成树 int i,j,t,k,w,min,m; struct edgeElem x; for(i=0;i<n;i+) if(i>0)/从0点连接其余顶点 MSTi-1.fromvex=0; MSTi-1.endvex=i; MSTi-1.weight=GA0i; for(k=

14、1;k<n;k+) min=MaxValue; m=k-1; for(j=k-1;j<n-1;j+) if(MSTj.weight<min) min=MSTj.weight;m=j;/选择从0点出发权值最小的边 x=MSTk-1;MSTk-1=MSTm;MSTm=x;/交换位置 j=MSTk-1.endvex;/定位于权值最小边的尾顶点 for(i=k;i<n-1;i+)/选取轻边 t=MSTi.endvex;w=GAjt; if(w<MSTi.weight) MSTi.weight=w; MSTi.fromvex=j; Out_edgeset()功能为显示最小生

15、成树，算法描述如下：void out_edgeset(edgeset MST,int e)/显示最小生成树 int k; printf("最小的消耗路线为n"); for(k=0;k<e;k+) printf("(%d %d %d)n",MSTk.fromvex,MSTk.endvex,MSTk.weight);主函数模块主要实现的是普尔米算法和克鲁斯卡尔算法的选择，然后在各自算法下建立图，并实现最小生成树的生成，调用函数，实现所需的功能。并通过while函数，实现功能的循环。具体实现如下：void main() int n,e,i; int a;

16、 system("color 71");/改变屏幕颜色 vexlist GV;/顶点表 adjmatrix GA;/边表 edgeset MST;/最小生成树do printf("输入图的顶点数n，我们将根据您输入的数据大小选择合适的算法。n"); scanf("%d",&n); if(n>=10)/大于10用prim算法来实现，否则kruskal算法来实现 printf("用prim算法从0点出发求图的最小生成树为：n"); printf("请输入图的边数。n"); scanf(

17、"%d",&e); Creat_adjmatrix( GV, GA, n, e);/创建图 prim(GA,MST,n);/生成最小生成树 out_edgeset( MST, n-1);/输出最小生成树 else printf("用kcuskal算法的最小生成树为：n"); GraphMatrix graph;/定义一个结构体来表示存储结构 Creat_adjmatrix2(GV,GA,n,e,graph);/创建图 kruskal(&graph,mst);/生成最小生成树 printf("最小的消耗路线为n"); f

18、or (i = 0; i < graph.n-1; i+) printf("(%d %d %d)n", msti.start_vex, msti.stop_vex, msti.weight);/输出最小生成树 printf("谢谢使用！n"); printf("继续？输入1继续，输入0退出。n");/方便用户重复使用程序 scanf("%d",&a); getchar(); system("cls");/清屏语句 while(a=1); 举例说明如下：运行程序，得出如下窗口，如图1

19、。 图1 进入界面输入顶点数6，选择算法，如图2。 图2 算法的选择输入顶点序号，如图3。图4 顶点输入输入边的情况，完成图的建立，如图5。 图5 完成图的建立与最小生成树输入0则跳出程序，输入1则跳回图1。四、结论该程序实现了在n个城市之间建设网络，既保证连通性，也成为了最经济的架设方法。程序中应用了普尔米算法和克鲁斯卡尔算法，实现了矩阵的输出以及最小生成树的输出。同时，该程序的主函数使用了while函数，使程序变得更完整，更清晰，可以使操作者完成一次运行后选择退出或者继续运行。不过，该程序也有不足之处，图的输入数据过大，引起出错不容易返回。附录：代码：#include "proc

20、ess.h" /改变屏幕颜色和字符颜色的头文件#include<stdio.h>#include<stdlib.h>#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;

21、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

22、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;i<n;i+) /建立顶点表 scanf("%d",&GVi);/读入顶点信息 for(i=0;i<n;i+)/建立边表 for(j=0;j<n;j+)/初始化边表 if(i=j) GAij=0; else GAij=MaxValue; prin

23、tf("输入%d条无向带权边（序号 序号 权值）：n",e); for(k=0;k<e;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;i+) /建立顶

24、点表 scanf("%d",&GVi);/读入顶点信息 if(GVi>=m) printf("您输入的序号有误，请输入0到%d-1之间的数，请重新输入。n",m); scanf("%d",&GVi); for(i=0;i<m;i+)/建立边表 for(j=0;j<m;j+)/初始化边表 GAij=MaxValue; printf("请输入有多少条边。n"); scanf("%d",&e); printf("输入%d条无向带权边（序号 序号 权值

25、）：n",e); for(k=0;k<e;k+)/设置边表 scanf("%d%d%d",&i,&j,&w); GAij=GAji=w;/对称 printf("您输入的图的存贮为下面表，如果不可达则用1000表示。n"); graph.n =m; for(x=0;x<m;x+) for(y=0;y<m;y+) graph.arcsxy=GAxy; printf("%-4d ",graph.arcsxy); printf("n"); void kruskal(Gra

26、phMatrix * pgraph, Edge mst) int i, j, min, vx, vy; int weight, minweight; Edge edge; for (i = 0; i < pgraph->n-1; i+) msti.start_vex = 0; msti.stop_vex = i+1; msti.weight = pgraph->arcs0i+1; for (i = 0; i < pgraph->n-1; i+) /* 共n-1条边 */ minweight = MAX; min = i; for (j = i; j < pg

27、raph->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 < pgraph->n-1; j+) /*

28、调整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;k<e;k+) printf("(%d %d %d)n",MSTk.fromvex,MSTk.endvex,MSTk

29、.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;i<n;i+) if(i>0)/从0点连接其余顶点 MSTi-1.fromvex=0; MSTi-1.endvex=i; MSTi-1.weight=GA0i; for(k=1;k<n;k+) min=MaxValue; m=k-1; for(j=k-1;j<n-1;j+) if(MSTj.weight<min) min=MSTj.weight;m=j;/选择从0点出发权值最小的边 x=MSTk-1;MSTk-1=MSTm;MSTm=x;/交换位置 j=MSTk-1.endvex;/定位于权值最小边的尾顶点 for(i=k;i<n-1;i+)/选取轻边 t=MSTi.endvex;w=GAjt; if(w<MSTi.weight) MSTi.weight=w; MSTi.fromvex=j; void main(