数据结构课程设计报告(最小生成树).docx

数据构造课程设计报告课程名称：最小生成树课题负责人名学号 :同组成员名单角色：指导教师： 评阅成绩： 评阅意见：提交报告时间： 2023 年 12 月 19 日最小生成树计算机科学与技术 专业学生：指导教师：摘要 选择一颗生成树，使之总的消费最少，也就是要构造连通网的最小代价生成树简称为最小生成树的问题，一颗生成树的代价就是树上各边的代价之和，构造最小生成树可以有多种算法， 其中多数算法利用了 MST 的性质。关键词： 最小生成树 连通图 普里姆算法 克鲁斯卡尔算法 MST一、 设计目的1. 了解并把握数据构造与算法的设计方法，具备初步的独立分析和设计力量；2. 初步把握软件开发过程的问题分析、 系统设计、程序编码、测试等根本方法和技能；3. 提高综合运用所学的理论学问和方法独立分析和解决问题的力量；4. 训练用系统的观点和软件开发一般标准进展软件开发，培育软件工作者所应具备的科学的工作方法和作风。二、 算法思想分析该设计的要求是在 n 个城市之间建设网络，不仅要保证连通，还要求是最经济的架设方法。 依据克鲁斯卡尔和普里姆算法的不同之处，该程序将城市个数大于十个时应用普里姆算法求最小生成树，而城市个数小于十个时则应用克鲁斯卡尔进展计算。1. 算法思想1) 普里姆 Prim算法思想a) 选择从 0 节点开头，并选择 0 节点相关联的最小权值边，将与这条边相关联的另一顶点出列；b) 在出列的节点中相关联的全部边中选择一条不与另一个已出列的节点相关联的权值最小的边，并将该边相关联的节点出列；c) 重复 b)直到全部的节点出列。2) 克鲁斯卡尔 Kruskal 算法思想为了使生成树上总的权值之和最小，应当使每一条边上的权值尽可能的小，所以应从权值最小的边选起，直至选出 n-1 条不能构成回路的权值最小的边位置。具体做法如下：首先构造一个含 n 个顶点的森林，然后按权值从小到大从连通图中选择不使森林中产生回路的边参加到森林中去，直至该森林变成一棵树为止，这棵树便是连通图的最小生成树。由于生成树上不允许有回路，因此并非每一条居当前最小的边都可选。从生成树的构造过程可见，初始态为个顶点分属 n 棵树，互不连通，每参加一条边，就将两棵树合并为一棵树，在同一棵树上的两个顶点之间自然相连通，由此判别当前权值最小边是否可取只要判别它的两个顶点是否在同一棵树上即可。n2.系统承受的数据构造和算法1)数据构造Typedef int Vertextype;Typedef int adimatrixMaxVertexNumMaxVertexNum;TypedefintVertextype vexlistMaxVertexNum;TypedefintVexType;TypedefintAdjType;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;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,vy V-U中选出最短的边 if(mstj.weight<minweight)minweight = mstj.weight; min = j;/mstmin 是 最 短 的边 (vx,vy)(vx U,vy V-U), 将mstmin 参加最小生成树edge = mstmin; mstmin = msti; msti = edge;vx = msti.stop_vex;/vx 为刚参加最小生成树的顶点的下标for(j=i+1;j<pgraph->n-1;j+)vy=mstj.stop_vex;weight=pgraph->arcsvxvy; if(weight<mstj.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;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;4. out_edgeset 功能为显示最小生成树。四、 运行程序运行程序，得到如下窗口，如图 1：输入顶点数，选择算法：当输入的顶点数小于 10 时，选择 Kruskal 算法，如图 2当输入的顶点数大于 10 时，选择 Prim 算法，如图 3输入顶点序号，如图 4：输入边的状况，完成图的建立，如图 5：最终，输入 0 则完毕程序，输入 1 则连续。五、 结论该程序实现了在 n 个城市之间建设网络，既保证了连通性， 也成为了最经济的架设方法。 程序中应用了普里姆算法和克鲁斯卡尔算法，实现了矩阵的输出以及最小生成树的输出。 不过， 该程序仍有缺乏之处，图的输入数据过大，易出错，不易返回， 仍需完善。参考文献1 数据构造程序设计题典 李春葆编 清华大学出版社2 数据构造 C 语言版 严蔚敏 吴伟民编 清华大学出版社3 数据构造课程设计 苏仕华编 机械工业出版社附录：源代码#include “process.h“/ 转变屏幕颜色和字符颜色的头文件#include<stdio.h> #include<stdlib.h>#define MaxVertexNum12#define MaxEdgeNum 20#define MaxValue 1000#define MAXVEX 6 #define MAX 1e+8 typedef 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 structint 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;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+)/ 设置边表scanf(“%d%d%d“,&i,&j,&w);GAij=GAji=w;/ 对称void Creat_adjmatrix2(vexlistGV,adjmatrixGA,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(“ 您输入的序号有误，请输入 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“,&i,&j,&w);GAij=GAji=w;/ 对称n“);printf(“ 您输入的图的存贮为下面表， 假设不行达则用 1000 表示。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;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)(vx U,vyV-U) 中选出最短的边 */if(mstj.weight < minweight) minweight = mstj.weight; min = j;/* mstmin 是最短的边(vx,vy)(vx U, vy V-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; pgraph->arcsvxvy;if (weight < mstj.weight) mstj.weight = weight; mstj.start_vex = vx;weight=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.weig ht);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 mainint n,e,i; int a;system(“color 71“);/ 转变屏幕颜色dovexlist GV;/ 顶点表adjmatrix GA;/ 边表edgeset MST;/ 最小生成树printf(“ 输入图的顶点数 n，我们将依据您输入的数据大小选择适宜的算法。 n“);scanf(“%d“,&n);if(n>=10)/ 大于 10 用 prim 算法来实现，否则 kruskal 算法来实现printf(“ 用prim 算法从 0 点动身求图的最小生成树为： n“); printf(“ 请输入图的边数。 n“);scanf(“%d“,&e);Creat_adjmatrix( GV, GA, n, e);/ 创立图prim(GA,MST,n);/ 生成最小生成树out_edgeset( MST, n-1);/ 输出最小生成树生成树elseprintf(“ 用 kcuskal 算法的最小生成树为： n“); GraphMatrix graph;/ 定义一个构造体来表示存储构造Creat_adjmatrix2(GV,GA,n,e,graph);/ 创立图kruskal(&graph,mst);/ 生成最小生成树printf(“ 最小的消耗路线为 n“); for (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);