普里姆算法求最小生成树精编版

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

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

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

4、） .-17- 3 -一课程设计目的和要求1.1课程设计目的(一) 根据算法设计需要，掌握连通网的数据表示方法；(二) 掌握最小生成树的Prim 算法；(三) 学习独立撰写报告文档。1.2课程设计的要求在 n 个城市之间建立网络，只需保证连通即可，求最经济的架设方法，利用 Prim 算法输出 n 个城市之间网络图，输出 n 个节点的最小生成树。其中， n 个城市表示 n 个节点，两个城市间如果有路则用边连接， 生成一个 n 个节点的边权树，要求键盘输入。- 4 -二 实验原理分析2.1最小生成树的定义一个有n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保

5、持图连通的最少的边。 最小生成树可以用 kruskal（克鲁斯卡尔）算法或 Prim （普里姆）算法求出。(1). 最小生成树的概述在一给定的无向图G = (V, E)中， (u, v)代表连接顶点 u与顶点 v的边（即），而 w(u,v)代表此边的权重，若存在T 为 E 的子集（即）且为无循环图，使得 w(T)最小，则此 T 为 G 的最小生成树。最小生成树其实是最小权重生成树的简称。(2). 最小生成树的分析构造最小生成树可以用多种算法。其中多数算法利用了最小生成树的下面一种简称为 MST 的性质：假设 N=(V,E) 是一个连通网，U是顶 点集 V 的一 个非 空子 集 。若 (u,v)

6、 是 一条 具 有最 小权 值（ 代价 ）的边， 其中 u U ， v V-U ， 则必 存在 一棵包含 边 (u.v) 的 最小生 成 树 。2.2Prim 算法的基本思想假设 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），其中 Vi U,Vj

7、(V-U), 并把该边（ i,j）和顶点 j 分别并入 T 的边集 TE 和顶点集 U，如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1 次后就把所有 n 个顶点都并入到生成- 5 -树 T 的顶点集中，此时 U=V，TE中含有 n-1 条边， T 就是最后得到的最小生成树。可以看出，在普利姆算法中，是采用逐步增加 U 中的顶点，常称为“加点法” 。为了实现这个算法在本设计中需要设置一个辅助数组closedge ，以记录从 U 到V-U 具有最小代价的边。当辅助数组中存在两个或两个以上的最小代价的边时，此时最小生成树的形态就不唯一，此时可以在程序中采用递归的算法思想求出每个最小生成

8、树。(1). 在 prim 算法中要解决两个问题1) 在无向网中，当从一个顶点到其他顶点时，若其边上的权值相等，则可能从某一起点出发时，会得到不同的生成树，但最小生成树的权值必定相等，此时我们应该如何把所有的最小生成树求解出来；2) 每次如何从生成树 T 中到 T 外的所有边中，找出一条权值最小的边。例如，在第 k 次（ 1kn-1）前，生成树 T 中已有 k 个顶点和 k-1 条边，此时 T 中到 T 外的所有边数为 k(n-k) ，当然它也包括两顶点间没有直接边相连，其权值被看作常量的边在内，从如此多的边中找出最短的边，其时间复杂度0（k（n-k），是很费时间的，是否有好的方法能够降低查找

9、最短边的时间复杂度。(2). 上述问题的解决方法针对 1）中出现的问题，可以通过算法来实现，详情请看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

10、) 个顶点，对于其中的每个顶点 t，若（ j,t ）边上的权值小于已保留的从原 T 中到顶点 t 的最短边的权值， 则用（j,t ）修改之，使从 T 中到 T 外顶点 t 的最短边为（j,t ），否则原有最短边保持不变， 这样，就把第 k 次后从 T 中到 T 外每一顶点 t 的各一条最短边都保留下来了，为进行第k+1 次运算做好了准备， 此步需进行 n-k-1 次比较。所以，利用此方法求第k 次的- 6 -最短边共需比较2(n-k)-1 次，即时间复杂度为O(n-k)。- 7 -三 概要分析和设计3.1概要分析通过对上述算法的分析，将从以下三方面来进行分析：(1). 输入数据的类型在本次设计

11、中，是对无向图进行操作，网中的顶点数，边数，顶点的编号及每条边的权值都是通过键盘输入的，他们的数据类型均为整型，其中，权值的范围为 032768（即“”）；(2). 输出数据的类型当用户将无向图创建成功以后，就可以通过键盘任意输入一个起点值将其对应的最小生成树的生成路径及其权值显示出来；(3). 测试数据本次设计中是通过用Prim 算法求最小生成树，分别用以下三组数据进行测试：( 一)假设在创建无向图时， 只输入一个顶点， 如图 1 所示，验证运行结果；A图 1. 单一节点的无向图( 二)假设创建的无向图如图2 所示，验证运行结果；- 8 -图 2. 网中存在权值相等的边( 三)假设创建的无向

12、图如图3 所示，验证结果；图 3，网中的权值各不相等3.2概要设计在本次设计中， 网的定义为 G=(V,E),V 表示非空顶点集 ,E 表示边集 ,其存储结构这里采用邻接矩阵的方式来存储。 1 数据类型的定义 在本设计中所涉及到- 9 -的数据类型定义如下：(1). 符号常量的定义算法中涉及到两个符号常量，定义如下：#define MAX 20 功能：用于表示网中最多顶点个数； #define INFINIT 32768 功能：用于表示权的最大值，即。(2). 结构体的定义整个算法中涉及的结构体定义如下：定义结构体 ArcNode功能：用于存放边的权值typedef structint adj

13、;/权值ArcNode;定义结构体 AdjMatrix功能：用于表示网的结构及存储方式。typedefstructintvexsMAX； /vexs表示顶点向量intvexnum,arcnum； / 分别表示图的顶点数和弧数ArcNodearcsMAXMAX ；/ 邻接矩阵AdjMatrix定义结构体 Node功能：用于表示求最小生成树时用到的辅助数组。typedef structint adjvex;/存放顶点编号int lowcost;/存放顶点权值Node;外部变量的定义算法中涉及到两个外部变量，定义如下：-10-Node closeMAX功能：存放每个顶点所连接的边所对应的权值；int

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

15、盘输入网中顶点数，若顶点个数 <=1 时，将标志变量 flag 置为 1 并显示“最小生成树不存在”，然后返回主调函数；否则，继续通过键盘输入网中的边数，通过二重for 循环初始化邻接矩阵，然后输入各个顶点的编号及每条边的权值，调用函数 Locate() 求出每条边所对应的两个顶点在顶点向量表中的位置后，将对应在邻接矩阵中的相应位置赋予权值，从而在邻接矩阵中存放了相关连的顶点之间边的权值，完成无向网的存储；三、子函数 int Minium(AdjMatrix *G,Node close)功能：是求出辅助数组 close 中权值最小的边，在其函数体中，首先将最小权值（ min）置为 INF

16、INIT （），通过 for 循环将辅助数组中的各条边的权值与 min 进行比较，最终使得 min 中存放的是当前数组 close 中最小的权值，并将其在辅助数组中的相应位置返回主调函数中；四、子函数 void prim(AdjMatrix *G,int u)-11-功能：是利用 PRIM（普里姆）算法求出无向网所对应的最小生成树，在其函数体中，首先，定义AdjMatrix*p 用于存放最小生成树中的顶点（按生成最小生成树时的顺序存放），调用函数Locate() 求出起点 u 在顶点向量表中的位置，将u 存放到 p 的顶点向量表中， 初始化初始化 U=u ，利用 for 循环对 V-U 中的顶

17、点i, 初始化 closei ，再利用 for循环找 n-1 条边 (n=G->vexnum)，其中，调用函数 Minium()求出辅助数组 close中权值最小的边 , 并将其在辅助数组中的相应位置返回到主调函数中并赋给k0，此时 closek0 中存有当前最小边 (u0, v0)的信息，将边所对应的终点放入p 的顶点向量表中，累加边的权值；然后，输出<起点终点权值 >；最后，在顶点v0 并入 U 之后 , 利用 for 循环更新closedgei；当所有的顶点v0 都纳入 U集合之后，输出最小生成树中的顶点序列及最小生成树的权值之和。五、子函数 void display(

18、AdjMatrix *G)功能：是创建的无向网所对应的邻接矩阵；六、主函数 void main()功能：是完成对上述各子函数的调用， 完成本次设计的要求， 在其函数体中，通过 while 循环可以实现重复创建网以及可以从网中的不同顶点出发求出对应的最小生成树。(4). 流程图-12-开始输入ch, 用于判断是否创建无向网Ch=“Y ”1调用 create()函数Flog=02调用 display() 函数输入起点 stst=03调用 prim() 函数4调用 minium() 函数结束图 4. 流程图上述流程图反映了整个算法中各个子函数之间的嵌套调用，从主函数开始顺序往下执行，首先调用crea

19、t()函数创建无向网并采用邻接矩阵的方式来存储；然后将该网对应的邻接矩阵通过调用display()函数输出；最后调用 prim () 函数求出该网所对应的最小生成树，并且在prim ()函数中通过嵌套调用Minium ()函数求出辅助数组close中权值最小的边，从而完成了本设计的要求。-13-四测试结果该部分是对前面任务定义中的测试数据进行验证和分析：4.1实验一只含一个顶点的无向图。图 5. 只含一个顶点的无向图4.2实验二假定创建的无向网的顶点个数>1，并且网中有些边的权值相等。-14-图 7. 运行结果分析：在上述创建的无向网中，有些顶点之间没有边相连接，所以在邻接矩阵中用表示，

20、由于是以顶点 1 作为起点生成最小生成树，所以上述运行结果对应的生成树如图 7 所示。4.3 实验三假定创建的无向网的顶点个数 >1，并且网中有些边的权值不相等。运行结果如下：-15-参考文献(1). 吴玉蓉，数据结构（ C 语言版），中国水利水电出版社，2008 年；(2). 徐孝凯，数据结构实用教程，清华大学出版社，2005 年 7 月；(3). 谭浩强， C 语言程序设计教程，高等教育出版社，2004 年 5 月。-16-附录（关键部分程序清单）#include"stdio.h"#include"string.h"#include"

21、malloc.h"#include"iostream.h"#include"iomanip.h"#define MAX 20/ 最多顶点个数#define INFINIT 32768/ 表示极大值，即typedef structint adj;/adj 是权值类型ArcNode;typedef structint vexsMAX,vexnum,arcnum;/*vexs 表示顶点向量 ;vexnum,arcnum 分别表示图的顶点数和弧数*/ArcNode arcsMAXMAX;/* 邻接矩阵 */AdjMatrix;typedef struc

22、tint adjvex;/ 存放顶点编号int lowcost;/ 存放顶点权值Node;Node closeMAX;/ 求最小生成树时的辅助数组int flag=0;/功能：标志变量，当创建网时，输入的顶点个数<=1 时，直接输出“不存在最小生成树”程序不在往后执行，否则继续往下执行int Locate(AdjMatrix *G,int V) / 求顶点位置函数int j=-1,k;for(k=0;k<G->vexnum;k+)if(G->vexsk=V)j=k;-17-break;return j;AdjMatrix *creat(AdjMatrix *G) /创建

23、无向网int i,j,k,v1,v2,weight,m=1;printf(" 请输入网中的顶点数：");scanf("%d",&G->vexnum);if(G->vexnum<=1)printf("n* 最小生成树不存在 !*n"); flag=1;return G;elseprintf(" 请输入网中的边数：");scanf("%d",&G->arcnum);for(i=0;i<G->vexnum;i+) /初始化邻接矩阵for(j=0;j&

24、lt;G->vexnum;j+)if(i=j)G->arcsij.adj=0;elseG->arcsij.adj=INFINIT;printf(" 请输入网中的顶点编号："); / 输入网中的顶点编号for(i=0;i<G->vexnum;i+)scanf("%d",&G->vexsi);printf(" 输入每条弧所对应的两个顶点及权值<格式：起点终点权值 >!n");for(k=0;k<G->arcnum;k+)printf(" 请输入第 %d 条边 :

25、",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);-18-intMinium(AdjMatrix *G,Node close)/close 中权值最小的边int i,min,k;min=INFINIT;/ 置最小权值为INFINITfor(i=0;i<G->vexnum;i+)if(closei

26、.lowcost<min&&closei.lowcost!=0)min=closei.lowcost;k=i;return k;/ 返回权值最小的边在辅助数组中的位置void prim(AdjMatrix *G ,int u)/ 普里姆算法 /从顶点 u 出发 ,按普里姆算法构造连通网 G 的最小生成树，并输出生成树的每条边int i,j,k,k0,u0,v0,s=0,n=0;AdjMatrix *p;p=(AdjMatrix *)malloc(sizeof(AdjMatrix);k=Locate(G,u);/k 为顶点 u 的位置p->vexsn+=u;close

27、k.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=Minium(G ,close);/closek0 中存有当前最小边(u0, v0) 的信息u0=closek0.lowcost;/u0 Uv0=G->vexsk0;/v0 V-Up->vexsn+=v0;/

28、 将终点放入数组中s+=closek0.lowcost;/ 求最小生成树的权值之和printf("<%d->%dt%d>n",u,v0,closek0.lowcost); /输出最小生成树的路径closek0.lowcost=0;/ 将顶点 v0 纳入 U 集合for(i=0;i<G->vexnum;i+)/在顶点 v0 并入 U 之后 ,更新 closedgei-19-if(G->arcsk0i.adj<closei.lowcost)closei.lowcost=G->arcsk0i.adj;closei.adjvex=v0

29、;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;for(i=0;i<G->vexnum;i+)printf("t%d",G->vexsi);printf("n");printf

30、(" ");for(i=0;i<G->vexnum;i+)printf(" ");printf("n");for(i=0;i<G->vexnum;i+)printf(" %d ",G->vexsi);for(j=0;j<G->vexnum;j+)if(G->arcsij.adj=INFINIT)printf("t ");elseprintf("t%d",G->arcsij.adj);printf("n"

31、);for(i=0;i<G->vexnum;i+)printf(" ");printf("n");void main()/主函数char ch;int st;-20-AdjMatrix *G ,*p;p=(AdjMatrix *)malloc(sizeof(AdjMatrix);printf("*n");printf("普里姆最小生成树算法!n");n");printf("设计 者：李浩渊 n");printf("班级： 34010105班 n");printf("指导老师：范纯龙老师n");printf("设计时间： 2015 年 1月 15 日n");printf("n*");printf("n*若创建无向网请输入'Y',否则按任意键 !*n")