贪心算法实验(最小生成树).doc

《贪心算法实验(最小生成树).doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法分析与设计实验报告第一次附加实验姓名学号班级时间12.12上午地点工训楼309实验名称贪心算法实验(最小生成树)实验目的通过上机实验，要求掌握贪心算法的思想，利用prim算法求解最小生成树并实现。实验原理设G=(V,E)是连通带权图，V={1,2,…,n}。构造G的最小生成树的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件iÎS，jÎV-S，且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。实验步骤（1）用邻接矩阵表示无向图，并进行初

2、始化，同时选择源点放在集合s中；（2）选取候选集中距离最短的顶点，把其加入终点集合中；（3）以该顶点为新考虑的中间顶点，修改候选集中个顶点距离，若经过该点后，各点到达源点距离比原来距离短，则修改距离；（4）重复以上2、3步，直到所有候选集中都被加入到终点集中。关键代码template//参数为结点个数n，和无向带权图中各结点之间的距离c[][N+1]voidPrim(intn,Typec[][N+1]){Typelowcost[N+1];//记录c[j][closest]的最小权值intclosest[N+1];//V-S中点j在中的最临接顶点bool

3、s[N+1];//标记各结点是否已经放入集合s中s[1]=true;//初始化s[i],lowcost[i],closest[i]for(inti=2;i<=n;i++){lowcost[i]=c[1][i];closest[i]=1;s[i]=false;}for(inti=1;i

4、in的值j=k;}}cout<

5、这个已经生成的树的最短距离，而Kruskal算法是每次都选择最短的边加入到生成树集合中，其实两种算法其思想是不同的，所以两种算法的时间复杂度也是不同的，Prim算法的时间复杂度是O（n^2）,而Kruskal算法的时间复杂度是O（nlogn）,相比来讲，在时间上Kruskal更好一点。实验心得最小生成树在之前的数据结构中也是学过的，可是当时学的时候，也许是不够努力，学的模模糊糊的，也没有将Prim算法和Kruskal算法搞清楚，只是能简单的利用知识做题，却不能很清楚地讲明白这两种算法的原理差别，更别说是编程设计了，那就根本想都不要想，完全不知所措，在之前的数据结构中，很多涉

6、及到图的实现，尤其那些代码实在是晦涩难懂，搞得我实在不想学习，后来在算法课上学到的东西就有点不同了，也许是经过时间的打磨，感觉到现在的代码没有那么难懂了，也终于弄明白了两者的区别，感觉好多了。实验得分助教签名附录：完整代码（贪心法）//贪心算法最小生成树prim算法#include#include#include#include#includeusingnamespacestd;#defineinf9999;//定义无限大的值constintN=6;template

7、//模板定义voidPrim(intn,Typec[][N+1]);intmain(){intc[N+1][N+1];cout<<"连通带权图的矩阵为："<>c[i][j];}}cout<<"Prim算法最小生成树选边次序如下："<