数据结构课设——普里姆和克鲁斯卡尔算法

1、、儿、,刖百从学习数据结构这门课程开始，我已发现了学习算法的乐趣，在学习这门课的过程中也学到了许多计算机应用基础知识，对计算机的机体也有了一个初步的了解，又在课余时间阅读了大量有关算法设计与分析的图书，在此基础上，利用贪心算法，编写了一个用prim加深对算法设计与分析下面向大家介绍此程序所编写的，主要利用,运用以上所学知识编和kruskal算法求解最小生成树，也以此检验自己一学期所学成果，这门课程的理解，由于所学知识有限，难免有些繁琐和不完善之处，的设计原理，方法，内容及设计的结果。本程序是在windows环境下利用MicrosoftVisualC+6.0贪心算法的思想，以及数组，for语句的

2、循环，if语句的嵌套写出的prim和kruskal算法求解最小生成树，在输入其边的起始位置，种植位置以及权值后，便可分别输出此网的prim和kruskal算法最小生成树的边的起始位置，终止位置以及权值。正又2.1 设计方法和内容(1) .软件环境：MicrosoftVisualC+6.0(2) .详细设计思想：所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就仅是在某种意义上的局部最优解。优解，但对范围相当广泛的许多问题他最优解。题的一个解。是说，不从整体最优上加以考虑，他所做出的贪心算法不是对所有问题都能得到整体最能产生整体最优解或者是整体最优解的近似解贪心算法的基本思路

3、如下：1 .建立数学模型来描述问题。2 .把求解的问题分成若干个子问题。3 .对每一子问题求解，得到子问题的局部4 .把子问题的解局部最优解合成原来解问3 .Prim（普里姆）算法思想无向网的最小生成树问题此算法的思想是基于点的贪心，力求从源点到下一个点的距离最短，以此来构建临接矩阵，所以此算法的核心思想是求得源点到下一个点的最短距离，下面具体解释如何求此最短距离：在图中任取一个顶点k作为开始点，令集合U=k,集合w=V-U,其中v为图中所有顶点的集合，然后找出：一个顶点在集合U中，另一个顶点在集合W中的所有边中,U中，并从W中删去这些顶点，然持最小，在重复此过程，直到W为空过程如下：权值最短

4、的一条边，并将该边顶点全部加入集合后重新调整U中顶点到W中顶点的距离，使之保集为止，求解(a)无向网(b)u=w=f2F3,4,5闾图2T由图可知最小生成树的步骤，假设开始顶点就选为1,故首先有u=1,w=2,3,4,5。4 .kruskal(克鲁斯卡尔)算法的基本思想kruskal(克鲁斯卡尔)算法的基本思想是：将无向图的所有边按权值递增顺序排列，依次选定权值数较小的边，但要求后面选取的边不能与前面选区的边构成回路，若构成回路，则放弃该条边，然后再选后面权值较大的边，n个顶点的图中，选取n-1条边即可。注意：kruskal算法的贪心是从源点到下一个点的距离最短。prim算法的贪心是任意点到生

5、成树的距离最短，也就是边的最小。三，设计方法与内容：.Prim(普里姆)算法：假设网用邻接矩阵作存储结构，与图的邻接矩阵类似，只是将0变为无穷，1变为对应边上权值，而矩阵中对角线上的元素为0。(1)定义网中的顶点数，网的边数，这里将网的顶点数定为6个，网的边数定为10个。定义一个名为edgeset类，其数据成员fromvex,endvex,weight,分别为一条边的起点，终点和权值。(3)定义一个名为tree的类，定义了一个最小生成树边集的数组，用数组记录具有最小代价的边，找到后，将该边作为最小生成树的树边保存起来，再定义一个普里姆算法的成员函数prim(tree&t)。(4)对pr

6、im(tree&t)函数进行类外定义，分别将顶点数定义为k,边为m,权值为w,定义一个变量min,使其等于32767,即无穷大，利用for循环从顶点1出发求最小生成的数边，即设t.cti.fromvex=1。令终止点t.cti.endvex=i+1,令t.cti.weight=t.s1i+1,再利用第二个for循环找到权值最小的树边，从顶点为2开始循环，当j=k-1且小于网中总顶点数时，权值小于无穷则将此权值付给min,并令边m=j。(5)重新修改树边的距离，将原来的边用权值小的边替换，若当前边k小于n(原定边数),则令tl=t.cti.endvex,w=t.sjtl,若w<t.

7、cti.weight,则令t.cti.weight=w,t.cti.fromvex=j。(6)最后利用for循环键入每条边的起始点，终结点及边上的权值。2.kruskal算法：(1)定义网中的顶点数，网的边数，这里将网的顶点数定为6个，网的边数定为10个。(2)定义一个名为edgeset2的类，其数据成员fromvex,endvex,weight,分别为一条边的起点，终点和权值。(3)定义一个名为tree2的类，定义了一个最小生成树边集的数组，用edgesetge2e+1存放网中所有的边，定义一个s2n+1n+1,s为一个集合，一行元素si0sin表示一个集合，若sit=1。则表示顶点t属于该

8、集合，否则不属于该集合，再定义一个普里姆算法的成员函数kruskal(tree2&t2)。(4)对kruskal(tree2&t2)函数进行类外定义，定义k并设初值为1用来统计生成树的边数，定义d并设初值为1用来表示待扫描边的下标位置，定义两个变量m1,m2用来记录一条边的两个顶点所在集合的序号，如果t2.ge2d.fromvex=j且t2.s2ij=1，贝U令m1=i,若t2.ge2d.endvex=j且t2.s2ij=1贝U令m2=i,最后判断m1是否等于m2,若不等于则令t2.c2k=t2.ge2d,k自力口，求出一条边后，合并两个集合，另一个集合设置为空。(6)最后利用

9、for循环键入每条边的起始点，终结点及边上的权值，要求输入的网中的边上的权值必须为从大到小排列，调用kruskal(t)循环输出一条边的起始点，终结点及边上的权值。设计流程图定义生攵据成员fromvex,endvex,weight,分别条边的起点，终点和权值。z定义网中的顶点数n=6,网的边数e=10Kruskal算法VPrim算法从顶点1出发求最小生成树的边定义了一个最小生成树边集的数组，用edgesetge2e+1存放网中所有的边先找权值最小的树边，然后重新修改树边的距离，原来的边用权值较小的边取代定义一个s2n+1n+1,s为一个集合一行元素si0sin表示一个集合，若sit=1。则表示

10、顶点t属于该集合，否则不属于该集合最后利用for循环键入每条边的定义k并设初值为1用来统计生成树的起始点，终结点及边上的权值边数，定义d并设初值为1用来表示待扫描边的下标位置，定义两个变量Im1,m2用来记录一条边的两个顶点所在图2-2设计结论Prim算法：在图中任取一个顶点v为图中所有顶点的集合，然后找出：一个顶点在集合U中，另一个顶点在集合W中k作为开始点，令集合U=k,集合w=V-U,其中的所有边中，权值最短的一条边，并将该边顶点全部加入集合U中，并从W中删去这些顶点，然后重新调整U中顶点到W中顶点的距离，使之保持最小，在重复此过程，直到W为空集为止Kruskal算法：将无向图的所有边按

11、权值递增顺序排列，依次选定权值数较小的边，但要求后面选取的边不能与前面选区的边构成回路，若构成回路，则放弃该条边，然后再选后面权值较大的边，n个顶点的图中，选取n-1条边即可。其中两个算法的贪心思想有本质的区别：kruskal算法的贪心是从源点到下一个点的距离最短。而prim算法的贪心是任意点到生成树的距离最短，也就是边的最小。有关说明程序运行刚开始会出现一个界面：*请选择一种算法*.prim算法求解最小生成树.kruskal算法求解最小生成树此时便可输入用户想要选择的数值，回车然后进入如(图一或图二)的界面。(2)接着根据提示输输入一条边的起始点，终结点及边上的权值，如(图三)界面(3)重复

12、步骤(2)十次。(5)即可显示此算法下的最小生成树。如(图四)界面。致谢这次课程设计实训老师给我了很大的帮助，让我发现了自身的不足之处，在实际操作过程中犯的一些错误，同时还有有意外的收获。在具体操作中对这学期所学的数据结构的理论知识得到巩固，达到实训的基本目的，同时也认识到在以后的上机中应更加注意自己曾犯的错误，也发现上机实训的重要作用，特别是对数组和邻接矩阵有了深刻的理解。通过实际操作，学会数据结构程序编程的基本步骤、基本方法，开发了自己的逻辑思维能力，培养了分析问题、解决问题的能力。在此感谢学院领导，老师们给我们提供了这样一个良好的平台，让我们学有所用，把我们所学的理论知识与实践结合，锻炼

13、了自己动手操作的能力，希望自己以后有机会多进行这样的实训，培养自身独立思考问题的能力，提高实际操作水平。参考文献1李根强C+吸据结构2005年1月第一版中国水利水电出版社2侯识忠数据结构算法程序集页。页018602-01/tp谭浩强C程序设计2005年7月第三版清华大学出版社1-378顾仁高级C+语言程序设计技巧与实例1995年11月第一版机械工业出版社1-462陈明数据结构（C+版）2005年3月第一版清华大学出版社020923-01/tp谭浩强C+面向对象程序设计2006年1月第一版清华大学出版社1-288页7王晓东数据结构C+诩言2005年7月第一版清华大学出版社附录:*prirn算法*

14、#include<iostream.h>constintn=6;/网中顶点数constinte=10;/网中边数classedgeset/定义一条生成树的边的类public:intfromvex;/边的起点intendvex;/边的终点intweight;/边的权值classtreepublic:intsn+1n+1;/edgesetctn+1;/voidprim(tree&t);/;voidtree:prim(tree&t)inti,j,k,min,tl,m,w;前权值for(i=1;i<n;i+)/网的邻接矩阵最小生成树的边集普里姆算法/k为当前顶点数，m

15、为当前边数，w为当从顶点1出发求最小生成树的边t.cti.fromvex=1;t.cti.endvex=i+1;t.cti.weight=t.s1i+1;for(k=2;k<=n;k+)min=32767;m=k-1;for(j=k-1;j<n;j+)/if(t.ctj.weight<min)min=t.ctj.weight;找权值最小的树边m=j;edgesettemp=t.ctk-1;t.ctk-1=t.ctm;t.ctm=temp;j=t.ctk-1.endvex;for(i=k;i<n;i+)/重新修改树边的距离tl=t.cti.endvex;w=t.sjtl;

16、/原来的边用权值较小的边取代t.cti.weight=w;t.cti.fromvex=j;)/*kruskal算法*classedgeset2public:intfromvex;intendvex;intweight;);classtree2/public:edgesetc2n;/edgesetge2e+1;/ints2n+1n+1;/s/voidkruska(tree2&t2););定义生成树存放生成树的边存放网中所有边为一个集合，一行元素si0sin表示一个集合若sit=1。则表示顶点t属于该集合，否则不属于voidtree2:kruska(tree2&t2)inti,j;

17、for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(i=j)t2.s2ij=1;elset2.s2ij=0;intk=1;/统计生成树的边数intd=1;/表示待扫描边的下标位置intm1,m2;/记录一条边的两个顶点所在集合的序号while(k<n)for(i=1;i<=n;i+)for(j=1;j<=n;j+)if(t2.ge2d.fromvex=j)&&(t2.s2ij=1)m1=i;if(t2.ge2d.endvex=j)&&(t2.s2ij=1)m2=i;if(m1!=m2)t2.c2k=t2.ge2d;

18、k+;求出一条边后，合并两个集合另一个集合设置为空for(j=1;j<=n;j+)t2.s2m1j=t2.s2m1j|t2.s2m2j;/t2.s2m2j=0;/d+;*"<<endl;"<<endl;voidmain()intz;for(z=1;z<=3;z+)cout<<"*请选择一种算法"<<endl;cout<<"1.prim算法求解最小生成树cout<<"2.kruskal算法求解最小生成树cin>>z;if(z=1)intj,w

19、;treet;cout<<"prim算法求最小生成树"<<endl;cout<<"请连续输入网的10条边"<<endl;for(inti=1;i<=n;i+)for(intj=1;j<=n;j+)if(i=j)t.sij=0;elset.sij=32767;/若(i,j)边上无权值，用32767来代替无穷for(intk=1;k<=e;k+)/建立网的邻接矩阵cout<<"请输入一条边的起始点，终结点及边上的权值:cin>>i>>j>&g

20、t;w;cout<<endl;t.sij=w;t.sji=w;)t.prim(t);/用普里姆算法求最小生成树cout<<"此算法构造出的最小生成树的起始边，终止边以及权值如下："<<endl;for(i=1;i<n;i+)/输出n-1条生成树的边cout<<t.cti.fromvex<<""cout<<t.cti.endvex<<""cout<<t.cti.weight<<endl;)else/kruskaltree2t

21、2;cout<<"kruskal算法求最小生成树"<<endl;cout<<"请连续输入网的10条边(按权值从小到大的顺序<<endl;for(inti=1;i<=e;i+)cout<<"输入一条边的起始边，终止边以及权值："cin>>t2.ge2i.fromvex>>t2.ge2i.endvex>>t2.ge2i.weight;cout<<endl;:"<<endl;)t2.kruska(t2);cout<<"此算法构造出的最小生成树的起始边，终止边以及权值如下for(i=1;i<n;i+)cout<<t2.c2i.fromvex<<""cout<<t2.c2i.endvex<<""cout<<t2.c2i.weight<<endl;)力:俄的文档1数据结构"即储存文件口如凶匚即1点皿H-LJ_uj，jjfcjuj，jj，jU"X5-*TjI!|“廿jjfcj