普里姆算法求最小生成树

1、word某某航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：Prim算法求最小生成树院系：计算机学院 专业：计算机科学与技术物联网方向 班级: 学号: 某某: 指导教师:指导教师评语:签名:审査结诒学术诚信声明本人声明：所呈交的报告含电子版与数据文件是我个人在导师指 导下独立进展设计工作与取得的研究结果。尽我所知，除了文中特别 加以标注或致谢中所罗列的内容以外，报告中不包含其他人己经发表 或撰写过的研究结果，也不包含其它教育机构使用过的材料。与我一 同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说明 并表示了谢意。报告资料与实验数据假如有不实之处，本人愿意承受 本

2、教学环节“不与格和“重修或重做的评分结论并承当相关一切 后果。本人签名：日期：2015年1月15日某某航空航天大学课程设计任务书课程设计名称数据结构课程设计专业计算机科学与技术物联网方向学生某某班级学号题目名称Prim算法生成最小生成树起止日期2015 年 1 月 5日起至2015 年1月 16 日止课设内容和要求：在n个城市之间建立网络，只需保证连通即可，求最经济的架设方法，利用Prim算法输出n个城市之间网络图，输出n个节点的最小生成树。其中，n个城市 表示n个节点，两个城市间如果有路如此用边连接，生成一个n个节点的边权树，要求键盘输入。参考资料：算法与数据结构，严蔚敏、吴伟民，清华大学，

3、2006C程序设计，谭浩强，清华大学，2010教研室审核意见：教研室主任签字：指导教师签名年月日学生签名2015 年 1 月15 日目录学术诚信声明-1 -一课程设计目的和要求-4 -1.1课程设计目的-4-1.2课程设计的要求-4- 二实验原理分析-5 -2.1最小生成树的定义-5 -2.2 Prim算法的根本思想-5 -三概要分析和设计-8 -3.1概要分析-8-3.2概要设计-9 -四测试结果-14 -实验一 -14 -实验二-14 -4.3实验三-15 -参考文献-16 -附录关键局部程序清单-17 -一课程设计目的和要求1.1 课程设计目的（一）根据算法设计需要，掌握连通网的数据表示

4、方法;（二）掌握最小生成树的Prim算法；（三）学习独立撰写报告文档。1.2 课程设计的要求在n个城市之间建立网络，只需保证连通即可，求最经济的架设方法，利用Prim算法输出n个城市之间网络图，输出n个节点的最小生成树。其中，n个城 市表示n个节点，两个城市间如果有路如此用边连接，生成一个 n个节点的边权 树，要求键盘输入。二实验原理分析2.1最小生成树的定义一个有n个结点的连通图的生成树是原图的极小连通子图， 且包含原图中的 所有n个结点，并且有保持图连通的最少的边。最小生成树可以用 kruskal 克 鲁斯卡尔算法或Prim普里姆算法求出。(1) .最小生成树的概述在一给定的无向图G =

5、(V, E)中，(u, v)代表连接顶点u与顶点v的边即，而w(u, v)代表此边的权重，假如存在T为E的子集即且为无循环图，使得w(T)最小，如此此T为G的最小生成树。最小生成树其实是最小权重生成树的简称(2) . 最小生成树的分析构造最小生成树可以用多种算法。其中多数算法利用了最小生成 树的下面一种简称为MST的性质：假设N=(V,E) 是一个连通网，U 是顶点集V的一个非空子集。假如(u,v)是一条具有最小权值代价 的边，其中u U，v V-U，如此必存在一棵包含边(u.v)的最小生成 树。2.2 Prim 算法的根本思想假设G = V, E是一个具有n个顶点的连通网，T=(U,TE)是

6、G的最小生成 树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空集。算法开始时， 首先从V中任取一个顶点假定取 V0，将它并入U中，此时U=V0，然后只要 U是V的真子集，就从那些其一个端点已在 T中，另一个端点仍在T外的所有边 中，找一条最短即权值最小边，假定为i,j丨，其中Vi U,Vj (V-U),并把 该边i,j和顶点j分别并入T的边集TE和顶点集U,如此进展下去，每次往生成树里并入一个顶点和一条边，直到n-1次后就把所有n个顶点都并入到生成树T的顶点集中，此时U=V TE中含有n-1条边，T就是最后得到的最小生成树。 可以看出，在普利姆算法中，是采用逐步增加U中的顶点，常称

7、为“加点法。为了实现这个算法在本设计中需要设置一个辅助数组closedge，以记录从U到V-U具有最小代价的边。当辅助数组中存在两个或两个以上的最小代价的边时， 此时最小生成树的形态就不唯一，此时可以在程序中采用递归的算法思想求出每 个最小生成树。(1). 在prim算法中要解决两个问题1) 在无向网中，当从一个顶点到其他顶点时，假如其边上的权值相等，如此可能从某一起点出发时，会得到不同的生成树，但最小生成树的权值必定相等，此时我们应该如何把所有的最小生成树求解出来；2) 每次如何从生成树T中到T外的所有边中，找出一条权值最小的边。例如，在第k次1< k< n-1丨前，生成树T中已

8、有k个顶点和k-1条边，此时T 中到T外的所有边数为k(n-k)，当然它也包括两顶点间没有直接边相连，其 权值被看作常量的边在内，从如此多的边中找出最短的边，其时间复杂度0k n-k，是很费时间的，是否有好的方法能够降低查找最短边的时间复 杂度。.上述问题的解决方法针对1中出现的问题，可以通过算法来实现，详情请看Prim算法的概述；针对2中出现的问题，通过对Prim算法的分析，可以使查找最短边的时间 复杂度降低到0(n-k)。具体方法是假定在进展第k次前已经保存着从T中到T外 的每一顶点共n-k个顶点的各一条最短边，进展第k次时，首先从这n-k条最短边中，找出一条最最短的边，它就是从 T中到T

9、外的所有边中的最短边，假 设为i,j丨，此步需进展n-k次比拟；然后把边i,j和顶点j分别并入T中的 边集TE和顶点集U中，此时T外只有n-(k+1)个顶点，对于其中的每个顶点t， 假如j,t丨边上的权值小于已保存的从原 T中到顶点t的最短边的权值，如此用 j,t丨修改之，使从T中到T外顶点t的最短边为j,t丨，否如此原有最短边保 持不变，这样，就把第k次后从T中到T外每一顶点t的各一条最短边都保存下 来了，为进展第k+1次运算做好了准备，此步需进展 n-k-1次比拟。所以，利用 此方法求第k次的最短边共需比拟2(n-k)-1次，即时间复杂度为0(n-k)。三概要分析和设计3.1概要分析通过对

10、上述算法的分析，将从以下三方面来进展分析:(1) .输入数据的类型在本次设计中，是对无向图进展操作，网中的顶点数，边数，顶点的编号与 每条边的权值都是通过键盘输入的，他们的数据类型均为整型，其中，权值的X围为 032768即“"(2) .输出数据的类型当用户将无向图创建成功以后，就可以通过键盘任意输入一个起点值将其对 应的最小生成树的生成路径与其权值显示出来；(3) .测试数据本次设计中是通过用 Prim算法求最小生成树，分别用以下三组数据进展测 试：(一)假设在创建无向图时，只输入一个顶点，如图1所示，验证运行结果；(二) 假设创建的无向图如图2所示，验证运行结果;在本次设计中，网

11、的定义为 G=(V,E),V表示非空顶点集,E表示边集,其存储 结构这里采用邻接矩阵的方式来存储。1 数据类型的定义 在本设计中所涉与 到的数据类型定义如下：符号常量的定义 算法中涉与到两个符号常量，定义如下：#defi ne MAX 20功能：用于表示网中最多顶点个数；#defi ne INFINIT 32768 功能：用于表示权的最大值，即. 结构体的定义整个算法中涉与的结构体定义如下：? 定义结构体Arode功能：用于存放边的权值typedef structint adj;/ 权值Arode;? 定义结构体AdjMatrix功能：用于表示网的结构与存储方式。typedef structi

12、nt vexsMAX； /vexs 表示顶点向量intvexnum,arum； /分别表示图的顶点数和弧数Arode arcsMAXMAX ； / 邻接矩阵AdjMatrix? 定义结构体Node功能：用于表示求最小生成树时用到的辅助数组。typedef structint adjvex;/存放顶点编号int lowcost;/存放顶点权值Node;? 外部变量的定义算法中涉与到两个外部变量，定义如下：Node closeMAX功能：存放每个顶点所连接的边所对应的权值；int flag=O功能：标志变量，当创建网时，输入的顶点个数=1时，直接输出“不 存在最小生成树'程序不在往后执行，

13、否如此继续往下执行。 函数模块在本设计中一共包括六个模块：一、子函数 int Locate(AdjMatrix *G,int V)功能：是求出某个顶点在顶点向量表中的位置，在其函数体中通过for循环将某一顶点与顶点向量表中的所有顶点进展比拟，当出现两者相等时，将该顶点 在vexsMAX数组中的下标通过return语句返回，否如此返回-1 ；二、子函数 AdjMatrix *creat(AdjMatrix *G)功能：是完成无向网的创建，在其函数体中，首先通过键盘输入网中顶点数， 假如顶点个数<=1时，将标志变量flag置为1并显示“最小生成树不存在，然 后返回主调函数；否如此，继续通过键

14、盘输入网中的边数，通过二重for循环初始化邻接矩阵，然后输入各个顶点的编号与每条边的权值，调用函数Locate()求出每条边所对应的两个顶点在顶点向量表中的位置后，将对应在邻接矩阵中的相 应位置赋予权值，从而在邻接矩阵中存放了相关连的顶点之间边的权值，完成无 向网的存储；三、子函数 int Minium(AdjMatrix *G,Node close)功能：是求出辅助数组 close中权值最小的边，在其函数体中，首先将最 小权值min置为INFINIT，通过for循环将辅助数组中的各条边的权值 与min进展比拟，最终使得 min中存放的是当前数组close中最小的权值，并 将其在辅助数组中的相

15、应位置返回主调函数中；四、子函数 void prim(AdjMatrix *G,int u)功能：是利用PRIM：普里姆算法求出无向网所对应的最小生成树，在其函 数体中，首先，定义AdjMatrix *p用于存放最小生成树中的顶点按生成最小生 成树时的顺序存放，调用函数Locate()求出起点u在顶点向量表中的位置，将 u存放到p的顶点向量表中，初始化初始化U=u，利用for循环对V-U中的顶点 i,初始化closei，再利用for循环找n-1条边(n=G->vexnum)，其中，调用函数Minium()求出辅助数组close中权值最小的边,并将其在辅助数组中的相应 位置返回到主调函数中

16、并赋给 kO,此时closek0中存有当前最小边(uO, vO)的 信息，将边所对应的终点放入p的顶点向量表中，累加边的权值；然后，输出 <起点 终点 权值 >最后，在顶点 vO并入U之后，利用for循环更新 closedgei;当所有的顶点v0都纳入U集合之后，输出最小生成树中的顶点序 列与最小生成树的权值之和。五、子函数 void display(AdjMatrix *G)功能：是创建的无向网所对应的邻接矩阵；六、主函数 void main()功能：是完成对上述各子函数的调用，完本钱次设计的要求，在其函数体中，通过while循环可以实现重复创建网以与可以从网中的不同顶点出发求出

17、对应的 最小生成树。. 流程图上述流程图反映了整个算法中各个子函数之间的嵌套调用，从主函数开始顺 序往下执行，首先调用creat()函数创建无向网并采用邻接矩阵的方式来存储；然后将该网对应的邻接矩阵通过调用display。函数输出；最后调用prim ()函数求出该网所对应的最小生成树，并且在prim ()函数中通过嵌套调用 Minium ()函数求出辅助数组close中权值最小的边，从而完成了本设计的要求。四测试结果该局部是对前面任务定义中的测试数据进展验证和分析:4.1实验一只含一个顶点的无向图。-怛供总母：丫甘.口止.“”斤旦卢屮r £铝£飞11丄1丄1川亘 1EU-m

18、 “*是忙叵R5 flTpl 昨胡HLriffiwifmftfifif!惮导*百 鱼逹无 问用:手帝I人叫P .否ill|占任 萤密丫号押胃FlfWf if 1fll青皆If *!向 爲了*轧 ' V P j 诽"ll| T"" » - Cl "十甲 HIMi»W bffWBf WW;WW i*MWH-W-irtfMWM'ii-WW 崗軸A.何中的助5亦-图5.只含一个顶点的无向图4.2 实验二假定创建的无向网的顶点个数1，并且网中有些边的权值相等。分析：在上述创建的无向网中，有些顶点之间没有边相连接，所以在邻接矩 阵

19、中用表示，由于是以顶点1作为起点生成最小生成树，所以上述运行结果对 应的生成树如图7所示。实验三假定创建的无向网的顶点个数>1,并且网中有些边的权值不相等。运行结果 如下:尉卜牛威护I中芋顶点序列为» I 1234 E £ J刑用普甲妞就R出占1岀斜尉I江成树的路槿如下<起点-，终点权值<1 ->216 ><1 ->35><1 ->46><1->611><1->518 >最才灶Ji湖比枉植2和为：躬诗继纽評尼点吞口喩®E出匚参考文献(1) .吴玉蓉，数据结构C语言

20、版，中国水利水电，2008年;(2) .徐孝凯，数据结构实用教程，清华大学，2005年7月；(3) .谭浩强，C语言程序设计教程，高等教育，2004年5月。附录关键局部程序清单#include"stdio.h"#include"string.h"#include"malloc.h"#include"iostream.h"#include"iomanip.h"#define MAX 20 / 最多顶点个数#define INFINIT 32768表示极大值，即®typedef struc

21、tint adj; /adj是权值类型Arode;typedef structint vexsMAX,vexnum,arum; /*vexs表示顶点向量；vexnum,arum分别表示图的顶点数和弧数*/Arode arcsMAXMAX; /*邻接矩阵 */AdjMatrix;typedef structint adjvex;/ 存放顶点编号 int lowcost;/存放顶点权值Node;Node closeMAX;/求最小生成树时的辅助数组int flag=O; /功能：标志变量，当创建网时，输入的顶点个数<=1时，直接输岀“不存在最小生成树"求顶点位置函数程序不在往后执行

22、，否如此继续往下执行int Locate(AdjMatrix *G,int V) / intj=-1,k;for(k=O;k<G->vexnum;k+) if(G->vexsk=V)j=k;break;return j;AdjMatrix *creat(AdjMatrix *G) /创建无向网int i,j,k,v1,v2,weight,m=1;printf（”请输入网中的顶点数："）;scanf("%d",&G->vexnum);if(G->vexnum<=1)printf("n*flag=1; return

23、 G; elseprintf(" 请输入网中的边数: scanf("%d",&G->arum);for(i=0;i<G->vexnum;i+) /for(j=0;j<G_>vexnum;j+) if(i=j)G->arcsij.adj=0;elseG->arcsij.adj=INFINIT;最小生成树不存在!*n"）;"）;初始化邻接矩阵printf（"请输入网中的顶点编号："）;/输入网中的顶点编号for(i=0;i<G->vexnum;i+) scanf（&q

24、uot;%d",&G-vexsi）;printf（"输入每条弧所对应的两个顶点与权值格式：起点终点权值!n"）;for(k=0;k<G->arum;k+)printf(" 请输入第d条边:",m);输入一条弧的两个顶点与权值m+;scanf("%d %d %d"，&v1,&v2,&weight); / i=Locate(G,v1);j=Locate(G,v2);G->arcsij.adj=weight;G->arcsji.adj=weight;return(G);中权值

25、最小的边int Minium(AdjMatrix *G,Node close)/closeint i,min,k;min=INFINIT;置最小权值为 INFINITfor(i=0;i<G->vexnum;i+)if(closei.lowcost<min&&closei.lowcost!=0)min=closei.lowcost;k=i;return k;/返回权值最小的边在辅助数组中的位置G的最小生成void prim(AdjMatrix *G,int u)/普里姆算法/从顶点u出发，按普里姆算法构造连通网树，并输岀生成树的每条边int i,j,k,k0,u

26、0,v0,s=0,n=0;AdjMatrix *p;p=(AdjMatrix *)malloc(sizeof(AdjMatrix); k=Locate(G,u);/k 为顶点u的位置 p->vexsn+=u;closek.lowcost=0;/初始化 U=ufor(i=0;i<G->vexnum;i+)if(i!=k) / 对V-U中的顶点i,初始化closeiclosei.adjvex=u;closei.lowcost=G->arcski.adj;for(j=1;j<=G->vexnum-1;j+)/n-1条边(n=G->vexnum)k0=Mini

27、um(G,close);/closek0中存有当前最小边(u0, v0)的信息u0=closek0.lowcost;/u0 Uv0=G->vexsk0; /v0 V-Up->vexsn+=v0;将终点放入数组中s+=closek0.lowcost;求最小生成树的权值之和printf(" v%d->%dt%d>n",u,v0,closek0.lowcost); /输出最小生成树的路径closek0.lowcost=0;将顶点 v0 纳入 U 集合for(i=0;i<G->vexnum;i+)/ 在顶点 v0 并入 U之后,更新 closed

28、geiif(G->arcskOi.adj<closei.lowcost)closei.lowcost=G->arcskOi.adj;closei.adjvex=vO;printf("n最小生成树中的顶点序列为：");for(i=0;i<G->vexnum;i+)printf(" %d ",p->vexsi);printf("n");printf("n最小生成树的权值之和为：dn",s);输岀邻接矩阵算法 void display(AdjMatrix *G) /int i,j;fo

29、r(i=0;i<G->vexnum;i+) printf("t%d",G->vexsi); printf("n");printf("| ");for(i=0;i<G->vexnum;i+)prin tf("");printf("n");for(i=0;i<G->vexnum;i+)printf(" %d | ",G->vexsi);for(j=0;j<G->vexnum;j+) if(G->arcsij.adj

30、=INFINIT) printf("t g");elseprintf("t%d",G->arcsij.adj); printf("n");for(i=0;i<G->vexnum;i+) printf("");printf("n");void main() / 主函数char ch;int st;AdjMatrix *G,*p;p=(AdjMatrix *)malloc(sizeof(AdjMatrix);printf(”*n");printf("普里姆最小生成树算法！n"）;printf("n*n");printf("设计者:printf("班 级:printf("指导教师:printf("设计时间:李浩渊n");34010105 班 n");X纯龙教师n");2015 年 1 月 15 日 n");printf("n*");printf("n*键!*n");假如创建无向网请输入