普里姆算法求最小生成树

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

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

3、？吴伟民，清华大学出版社，2006C程序设计，谭浩强，清华大学出版社，2010教研室审核意见：教研室主任签字：指导教师（签名）年月日学生（签名）2015年 1月15日课程设计目的和要求课程设计目的（一）根据算法设计需要，掌握连通网的数据表示方法；（二）掌握最小生成树的Prim算法；（三）学习独立撰写报告文档。课程设计的要求在n个城市之间建立网络，只需保证连通即可，求最经济的架设方法，利用Prim算法输出n个城市之间网络图，输出n个节点的最小生成树。其中，n个城 市表示n个节点，两个城市间如果有路则用边连接，生成一个n个节点的边权树， 要求键盘输入。二实验原理分析最小生成树的定义一个有n个结点的

4、连通图的生成树是原图的极小连通子图，且包含原图中 的所有n个结点，并且有保持图连通的最少的边。最小生成树可以用（克鲁斯 卡尔）算法或（普里姆）算法求出。（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）是一条具有最

5、小权值（代价）的 边，其中u U，v V-U，则必存在一棵包含边的最小生成树。Prim算法的基本思想假设G = (V,巳是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成 树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空集。算法开始时， 首先从V中任取一个顶点(假定取 V0),将它并入U中，此时U=VO，然后只要 U是V的真子集，就从那些其一个端点已在 T中，另一个端点仍在T外的所有边 中，找一条最短(即权值最小)边，假定为(i,j )，其中Vi U,Vj (V-U),并把 该边(i,j )和顶点j分别并入T的边集TE和顶点集U,如此进行下去，每次往 生成树里并入一个顶点和

6、一条边，直到n-1次后就把所有n个顶点都并入到生成树T的顶点集中，此时U=V TE中含有n-1条边，T就是最后得到的最小生成树。 可以看出，在普利姆算法中，是采用逐步增加 U中的顶点，常称为“加点法”。为 了实现这个算法在本设计中需要设置一个辅助数组closedge，以记录从U到V-U具有最小代价的边。当辅助数组中存在两个或两个以上的最小代价的边时， 此时最小生成树的形态就不唯一，此时可以在程序中采用递归的算法思想求出每 个最小生成树。(1) .在prim算法中要解决两个问题1) 在无向网中，当从一个顶点到其他顶点时，若其边上的权值相等，贝U可能从 某一起点出发时，会得到不同的生成树，但最小生

7、成树的权值必定相等，此 时我们应该如何把所有的最小生成树求解出来；2) 每次如何从生成树T中到T外的所有边中，找出一条权值最小的边。例如，在第k次(1kn-1 )前，生成树T中已有k个顶点和k-1条边，此时T中 到T外的所有边数为k(n-k)，当然它也包括两顶点间没有直接边相连，其权 值被看作常量的边在内，从如此多的边中找出最短的边，其时间复杂度0 (k(n-k),是很费时间的，是否有好的方法能够降低查找最短边的时间复杂度。(2) .上述问题的解决方法针对1)中出现的问题，可以通过算法来实现，详情请看Prim算法的概述；针对2)中出现的问题，通过对Prim算法的分析，可以使查找最短边的时间 复

8、杂度降低到0(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的最短边为（j,t），否则原有最短边保持不变，这样， 就把第k次后从T中到T外每一顶点t的各一条最短边都保

9、留下来了，为进行第 k+1次运算做好了准备，此步需进行n-k-1次比较。所以，利用此方法求第k次的 最短边共需比较2（n-k）-1次，即时间复杂度为0（n-k）。三概要分析和设计概要分析通过对上述算法的分析，将从以下三方面来进行分析：(1) .输入数据的类型在本次设计中，是对无向图进行操作，网中的顶点数，边数，顶点的编号及 每条边的权值都是通过键盘输入的，他们的数据类型均为整型，其中，权值的范 围为 032768 (即“W);(2) .输出数据的类型当用户将无向图创建成功以后，就可以通过键盘任意输入一个起点值将其对 应的最小生成树的生成路径及其权值显示出来；(3) .测试数据本次设计中是通过用

10、 Prim算法求最小生成树，分别用以下三组数据进行测 试：(一) 假设在创建无向图时，只输入一个顶点，如图1所示，验证运行结果;图1.单一节点的无向图(二) 假设创建的无向图如图2所示，验证运行结果;图2.网中存在权值相等的边在本次设计中，网的定义为G=(V,E),V表示非空顶点集,E表示边集，其存储结 构这里采用邻接矩阵的方式来存储。1 数据类型的定义 在本设计中所涉及到 的数据类型定义如下：(1) .符号常量的定义算法中涉及到两个符号常量，定义如下：#define MAX 20 功能：用于表示网中最多顶点个数；#define INFINIT 32768 功能：用于表示权的最大值，即(2)

11、.结构体的定义整个算法中涉及的结构体定义如下:? 定义结构体ArcNode功能：用于存放边的权值typedef structint adj;程图上述流程图反映了整个算法中各个子函数之间的嵌套调用，从主函数开始顺 序往下执行，首先调用creat()函数创建无向网并采用邻接矩阵的方式来存储;prim ()函数Mi nium ()然后将该网对应的邻接矩阵通过调用 display。函数输出；最后调用 求出该网所对应的最小生成树，并且在 prim ()函数中通过嵌套调用 函数求出辅助数组close中权值最小的边，从而完成了本设计的要求四测试结果该部分是对前面任务定义中的测试数据进行验证和分析:4.1 实

12、验一只含一个顶点的无向图Il ?斟*专話* Xeh ug Jrrr.M, M 丈兰二-* 4 =亡疋*甘餐氏報因蜀*出耳啊笛国!巴土1严刨电丸直：M 苗辄 人 屮也 训応仲 此妊*聲*.1*屛严岂生TV中圧：2,賂1I jj h生庶樹不存罕F 守*卜电*W.IW*f 扌色匕创邂元向网请林 甲* 出 訓 呛丄 辛 国片皿*i州卄“辅*甘卄:洋愉入两中的帀点弱图5.只含一个顶点的无向图4.2 实验二假定创建的无向网的顶点个数1，并且网中有些边的权值相等。图7.运行结果分析：在上述创建的无向网中，有些顶点之间没有边相连接，所以在邻接矩 阵中用表示，由于是以顶点1作为起点生成最小生成树，所以上述运行结

13、果对 应的生成树如图7所示。实验三假定创建的无向网的顶点个数1,并且网中有些边的权值不相等。运行结果 如下：菊J T& 占 1一二剎星音里姐負去从捉启1出岌眉小生融的密径如下f起点-渎点収渲2163E466115LS 晶小主成搁中的確点序列为;I 1234 b 5最小生成制的枝磴打口知汕i魏绩舗LL起点，舌則瑜丿退出、一参考文献(1) .吴玉蓉，数据结构(C语言版)，中国水利水电出版社，2008年;(2) .徐孝凯，数据结构实用教程，清华大学出版社，2005年7月；(3) .谭浩强，C语言程序设计教程，高等教育出版社，2004年5月。附 录（关键部分程序清单）#include#include#

14、include#include#include#define MAX 20 dj=O;elseG-arcsij.adj=INFINIT;printf(请输入网中的顶点编号：);dj=weight;G_arcsji.adj=weight;return(G);int Minium(AdjMatrix *G ,Node close)owcostarcski.adj;for(j=1;jv=G-vexnum-1;j+)owcost;owcost;owcost); owcost=0;djvclosei.lowcost) closei.lowcost=G-arcsk0i.adj;closei.adjvex=

15、v0;printf(n最小生成树中的顶点序列为：);for(i=0;ivexnum;i+)printf( %d ,p-vexsi);printf(n);printf(n最小生成树的权值之和为：dn,s);void display(AdjMatrix *G) dj=INFINIT)if(st=O)elseprintf(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(size

16、of(AdjMatrix);printf(*n);printf(普里姆最小生成树算法！n）;);printf（设 计者：李浩渊n）;printf（班 级：班 n）;printf（指导老师：范纯龙老师 n）;printf（设计时间：2015年1月15日n）;printf(n*printf(n*若创建无向网请输入Y,否则按任J键!*scanf(%c, &ch);while(1)if(ch=Y|ch=y)G=creat(p);if(flag=0)printf(n*该无向网所对应的邻接矩阵如下*n);display(G);printf(请输入起点:);scanf(%d,&st);while(1)els

17、ebreak;if(stG-vexnum)printf(”输入起点有错请重新输入!n);elseprintf(利用普里姆算法从起点%d岀发,最小生成树的路径如printf(n*n);printf(终点 权值 nn);prim(G,st);printf(n*n);printf（请继续输入起点，否则输入0退出）;继续创建无向网请输入Y,否则按任意scanf(%d, &st);printf(n*键!*);scanf(%c, &ch);flag=0;elsebreak;课程设计总结和体会:在整个课程设计的过程中，首先，应该根据课题的要求对题意进行分析， 将所遇到的问题进行归纳和总结，在本设计中，题意要求对给定的网和起点， 用PRIM算法的基本思想求解出所有的最小生成树，我们应该了解关于网的一些 基本概念和生成树与最小生成树之间有何区别和联系，