1、普里姆算法求最小生成树沈阳航空航天大学课 程 设 计 报 告课程设计名称：数据结构课程设计课程设计题目：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.1 课程设计目的(一)根据算法设计需要，掌握连通网的数据表示方法；(二)(三)掌握最小生成树的Prim算法；(四)(五)学习独立撰写报告文档。(六) 1.2 课程设计的要求在n个城市之间建立网络，只需保证连通即可，求最经济的架设方法，利用Prim算法输出n个城市之间网络图，输出n个节点的最小生成树。其中，n个城市表示n个节点，两个城市间如果有路则用边连接，生成一个n个节点的边权树，要求键盘输入。二 实验原理分析2
4、.1 最小生成树的定义一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或Prim（普里姆）算法求出。(1).最小生成树的概述(2).在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即）且为无循环图，使得 w(T) 最小，则此 T 为 G 的最小生成树。最小生成树其实是最小权重生成树的简称。(3).最小生成树的分析(4).构造最小生成树可以用多种算法。其中多数算法利用了
5、最小生成树的下面一种简称为MST的性质：假设N=(V,E)是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中uU，vV-U，则必存在一棵包含边(u.v)的最小生成树。2.2 Prim算法的基本思想假设G =（V，E）是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空集。算法开始时，首先从V中任取一个顶点（假定取V0），将它并入U中，此时U=V0，然后只要U是V的真子集，就从那些其一个端点已在T中，另一个端点仍在T外的所有边中，找一条最短（即权值最小）边，假定为（i,j），其中ViU,Vj
6、(V-U),并把该边（i,j）和顶点j分别并入T的边集TE和顶点集U，如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后就把所有n个顶点都并入到生成树T的顶点集中，此时U=V，TE中含有n-1条边，T就是最后得到的最小生成树。可以看出，在普利姆算法中，是采用逐步增加U中的顶点，常称为“加点法”。为了实现这个算法在本设计中需要设置一个辅助数组closedge ，以记录从U到V-U具有最小代价的边。当辅助数组中存在两个或两个以上的最小代价的边时，此时最小生成树的形态就不唯一，此时可以在程序中采用递归的算法思想求出每个最小生成树。(1).在prim算法中要解决两个问题(2).1)在无向
7、网中，当从一个顶点到其他顶点时，若其边上的权值相等，则可能从某一起点出发时，会得到不同的生成树，但最小生成树的权值必定相等，此时我们应该如何把所有的最小生成树求解出来；2)3)每次如何从生成树T中到T外的所有边中，找出一条权值最小的边。例如，在第k次（1kn-1）前，生成树T中已有k个顶点和k-1条边，此时T中到T外的所有边数为k(n-k)，当然它也包括两顶点间没有直接边相连，其权值被看作常量的边在内，从如此多的边中找出最短的边，其时间复杂度0（k（n-k），是很费时间的，是否有好的方法能够降低查找最短边的时间复杂度。4)(3).上述问题的解决方法(4).针对1）中出现的问题，可以通过算法来实
8、现，详情请看Prim算法的概述；针对2）中出现的问题，通过对Prim算法的分析，可以使查找最短边的时间复杂度降低到O(n-k)。具体方法是假定在进行第k次前已经保留着从T中到T外的每一顶点（共n-k个顶点）的各一条最短边，进行第k次时，首先从这n-k条最短边中，找出一条最最短的边，它就是从T中到T外的所有边中的最短边，假设为（i,j），此步需进行n-k次比较；然后把边（i,j）和顶点j分别并入T中的边集TE和顶点集U中，此时T外只有n-(k+1)个顶点，对于其中的每个顶点t，若（j,t）边上的权值小于已保留的从原T中到顶点t的最短边的权值，则用（j,t）修改之，使从T中到T外顶点t的最短边为（
9、j,t），否则原有最短边保持不变，这样，就把第k次后从T中到T外每一顶点t的各一条最短边都保留下来了，为进行第k+1次运算做好了准备，此步需进行n-k-1次比较。所以，利用此方法求第k次的最短边共需比较2(n-k)-1次，即时间复杂度为O(n-k)。三 概要分析和设计3.1 概要分析通过对上述算法的分析，将从以下三方面来进行分析：(1).输入数据的类型(2).在本次设计中，是对无向图进行操作，网中的顶点数，边数，顶点的编号及每条边的权值都是通过键盘输入的，他们的数据类型均为整型，其中，权值的范围为032768（即“”）；(3).输出数据的类型(4).当用户将无向图创建成功以后，就可以通过键盘任
10、意输入一个起点值将其对应的最小生成树的生成路径及其权值显示出来；(5).测试数据(6).本次设计中是通过用Prim算法求最小生成树，分别用以下三组数据进行测试：(一)假设在创建无向图时，只输入一个顶点，如图1所示，验证运行结果；(二) A图1.单一节点的无向图(三)假设创建的无向图如图2所示，验证运行结果；(四)图2.网中存在权值相等的边(五)假设创建的无向图如图3所示，验证结果；(六)图3，网中的权值各不相等3.2 概要设计在本次设计中，网的定义为G=(V,E),V表示非空顶点集,E表示边集,其存储结构这里采用邻接矩阵的方式来存储。 1 数据类型的定义 在本设计中所涉及到的数据类型定义如下：
11、(1).符号常量的定义(2). 算法中涉及到两个符号常量，定义如下： #define MAX 20 功能：用于表示网中最多顶点个数； #define INFINIT 32768 功能：用于表示权的最大值，即。(3).结构体的定义 (4). 整个算法中涉及的结构体定义如下：定义结构体ArcNode 功能：用于存放边的权值 typedef struct int adj;/权值 ArcNode;定义结构体AdjMatrix功能：用于表示网的结构及存储方式。typedefstructintvexsMAX；/vexs表示顶点向量intvexnum,arcnum；/分别表示图的顶点数和弧数ArcNodea
12、rcsMAXMAX；/邻接矩阵AdjMatrix 定义结构体Node 功能：用于表示求最小生成树时用到的辅助数组。 typedef struct int adjvex;/存放顶点编号 int lowcost;/存放顶点权值 Node;外部变量的定义 算法中涉及到两个外部变量，定义如下： Node closeMAX 功能：存放每个顶点所连接的边所对应的权值； int flag=0 功能：标志变量，当创建网时，输入的顶点个数=1时，直接输出 “不存在最小生成树”程序不在往后执行，否则继续往下执行。(5).函数模块(6).在本设计中一共包括六个模块：一、子函数int Locate(AdjMatrix
13、 *G,int V) 二、功能：是求出某个顶点在顶点向量表中的位置，在其函数体中通过for循环将某一顶点与顶点向量表中的所有顶点进行比较，当出现两者相等时，将该顶点在vexsMAX数组中的下标通过return语句返回，否则返回-1；三、子函数AdjMatrix *creat(AdjMatrix *G) 四、功能：是完成无向网的创建，在其函数体中，首先通过键盘输入网中顶点数，若顶点个数vexnum)，其中，调用函数Minium()求出辅助数组close中权值最小的边, 并将其在辅助数组中的相应位置返回到主调函数中并赋给k0，此时closek0中存有当前最小边(u0, v0)的信息，将边所对应的终
14、点放入p的顶点向量表中，累加边的权值；然后，输出；最后，在顶点v0并入U之后,利用for循环更新closedgei；当所有的顶点v0都纳入U集合之后，输出最小生成树中的顶点序列及最小生成树的权值之和。九、子函数void display(AdjMatrix *G) 十、功能：是创建的无向网所对应的邻接矩阵；十一、主函数void main() 十二、功能：是完成对上述各子函数的调用，完成本次设计的要求，在其函数体中，通过while循环可以实现重复创建网以及可以从网中的不同顶点出发求出对应的最小生成树。(7).流程图(8).(9).开始输入ch, 用于判断是否创建无向网Ch=“Y”结束输入起点st1
15、调用create()函数2调用display()函数Flog=0st=03调用prim()函数4调用minium()函数图 4.流程图上述流程图反映了整个算法中各个子函数之间的嵌套调用，从主函数开始顺序往下执行，首先调用creat()函数创建无向网并采用邻接矩阵的方式来存储；然后将该网对应的邻接矩阵通过调用display()函数输出；最后调用prim ()函数求出该网所对应的最小生成树，并且在prim ()函数中通过嵌套调用Minium ()函数求出辅助数组close中权值最小的边，从而完成了本设计的要求。四 测试结果该部分是对前面任务定义中的测试数据进行验证和分析：4.1实验一4.2只含一个
16、顶点的无向图。图5. 只含一个顶点的无向图4.3实验二4.4假定创建的无向网的顶点个数1，并且网中有些边的权值相等。图7.运行结果分析：在上述创建的无向网中，有些顶点之间没有边相连接，所以在邻接矩阵中用表示，由于是以顶点1作为起点生成最小生成树，所以上述运行结果对应的生成树如图7所示。4.3 实验三假定创建的无向网的顶点个数1，并且网中有些边的权值不相等。运行结果如下： 参考文献(1).吴玉蓉，数据结构（C语言版），中国水利水电出版社，2008年；(2).(3).徐孝凯，数据结构实用教程，清华大学出版社，2005年7月；(4).(5).谭浩强，C语言程序设计教程，高等教育出版社，2004年5月
17、。(6).附 录（关键部分程序清单）#includestdio.h#includestring.h #includemalloc.h #includeiostream.h#includeiomanip.h #define MAX 20 /最多顶点个数 #define INFINIT 32768/表示极大值，即 typedef struct int adj; /adj是权值类型 ArcNode; typedef struct int vexsMAX,vexnum,arcnum; /*vexs表示顶点向量;vexnum,arcnum分别表示图的顶点数和弧数*/ ArcNode arcsMAXMAX
18、; /*邻接矩阵*/ AdjMatrix; typedef struct int adjvex;/存放顶点编号 int lowcost;/存放顶点权值 Node; Node closeMAX;/求最小生成树时的辅助数组 int flag=0; /功能：标志变量，当创建网时，输入的顶点个数=1时，直接输出 “不存在最小生成树”程序不在往后执行，否则继续往下执行int Locate(AdjMatrix *G,int V) /求顶点位置函数 int j=-1,k; for(k=0;kvexnum;k+) if(G-vexsk=V) j=k; break; return j; AdjMatrix *c
19、reat(AdjMatrix *G) /创建无向网 int i,j,k,v1,v2,weight,m=1; printf(请输入网中的顶点数：); scanf(%d,&G-vexnum); if(G-vexnumarcnum); for(i=0;ivexnum;i+) /初始化邻接矩阵 for(j=0;jvexnum;j+) if(i=j) G-arcsij.adj=0; else G-arcsij.adj=INFINIT; printf(请输入网中的顶点编号：); /输入网中的顶点编号 for(i=0;ivexnum;i+) scanf(%d,&G-vexsi); printf(输入每条弧所
20、对应的两个顶点及权值!n); for(k=0;karcnum;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); int Minium(AdjMatrix *G,Node close)/close中权值最小的边 int i,min,k; min=INFINIT;/置最小权值为INFINIT for(i=0;ivexnum;i+
21、) if(closei.lowcostvexsn+=u; closek.lowcost=0;/初始化U=u for(i=0;ivexnum;i+) if(i!=k) /对V-U中的顶点i,初始化closei closei.adjvex=u; closei.lowcost=G-arcski.adj; for(j=1;jvexnum-1;j+)/n-1条边(n=G-vexnum) k0=Minium(G,close);/closek0中存有当前最小边(u0, v0)的信息 u0=closek0.lowcost;/u0U v0=G-vexsk0; /v0V-U p-vexsn+=v0;/将终点放入数
22、组中 s+=closek0.lowcost;/求最小生成树的权值之和 printf( %dt%dn,u,v0,closek0.lowcost); /输出最小生成树的路径 closek0.lowcost=0;/将顶点v0纳入U集合 for(i=0;ivexnum;i+)/在顶点v0并入U之后,更新closedgei if(G-arcsk0i.adjarcsk0i.adj; closei.adjvex=v0; printf(n最小生成树中的顶点序列为：); for(i=0;ivexnum;i+) printf( %d ,p-vexsi); printf(n); printf(n最小生成树的权值之和
23、为：%dn,s);void display(AdjMatrix *G) /输出邻接矩阵算法 int i,j; for(i=0;ivexnum;i+) printf(t%d,G-vexsi); printf(n); printf(); for(i=0;ivexnum;i+) printf(); printf(n); for(i=0;ivexnum;i+) printf( %d ,G-vexsi); for(j=0;jvexnum;j+) if(G-arcsij.adj=INFINIT) printf(t); else printf(t%d,G-arcsij.adj); printf(n); for(i=0;ivexnum;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( 设 计 者：李浩渊n); printf( 班 级：34010105
