《贪心算法实验(最小生成树).pdf》由会员分享，可在线阅读，更多相关《贪心算法实验(最小生成树).pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、算法分析与设计实验报告算法分析与设计实验报告第第 一一 次附加实验次附加实验姓名时间学号地点班级工训楼 30912.12 上午实验名称贪心算法实验( (最小生成树) )实验目的通过上机实验，要求掌握贪心算法的思想，利用prim 算法求解最小生成树并实现。实验原理设 G=(V,E)是连通带权图，V=1,2,n。构造 G 的最小生成树的 Prim 算法的基本思想是：首先置S=1，然后，只要S 是 V 的真子集，就作如下的贪心选择：选取满足条件 i S，j V-S，且cij最小的边，将顶点j 添加到 S 中。这个过程一直进行到 S=V 时为止。在这个过程中选取到的所有边恰好构成 G 的一棵最小生成树
2、。（1）用邻接矩阵表示无向图，并进行初始化，同时选择源点放在集合s 中；（2）选取候选集中距离最短的顶点，把其加入终点集合中；（3）以该顶点为新考虑的中间顶点，修改候选集中个顶点距离，若经过该点后，各点到达源点距离比原来距离短，则修改距离；（4）重复以上 2、3 步，直到所有候选集中都被加入到终点集中。实验步骤关键代码template/参数为结点个数n，和无向带权图中各结点之间的距离cN+1void Prim(int n,Type cN+1)Type lowcostN+1;/记录cjclosest的最小权值int closestN+1;/V-S中点j在中的最临接顶点bool sN+1;/标记各
3、结点是否已经放入集合s中s1=true;/初始化si,lowcosti,closestifor(int i=2;i=n;i+)lowcosti=c1i;closesti=1;si=false;1 / 5for(int i=1;in;i+)Type min=inf;int j=1;for(int k=2;k=n;k+)/找出V-S中是lowcost最小的顶点jif(lowcostkmin)&(!sk)/如果k的lowcost比min小并且k结点没有被访问min=lowcostk;/更新min的值j=k;coutj closestjendl;/输出j和最邻近j的点sj=true;/将j添加到集合s
4、中for(int k=2;k=n;k+)if(cjklowcostk)&(!sk)/s集合放进j后更新各结点的lowcost的值lowcostk=cjk;closestk=j;输入较小的有向带权图结果：测试结果2 / 5实验分析再求最小生成树的实验中， 有两种算法： 一种是Prim算法， 一种是Kruskal算法。在两种算法中，我们可以比较Prim 算法，是通过集合 S 中的点来更新另一个集合的点距这个已经生成的树的最短距离， 而 Kruskal 算法是每次都选择最短的边加入到生成树集合中， 其实两种算法其思想是不同的， 所以两种算法的时间复杂度也是不同的，Prim 算法的时间复杂度是 O（n
5、2）,而 Kruskal算法的时间复杂度是 O（nlogn）,相比来讲，在时间上Kruskal 更好一点。实验心得最小生成树在之前的数据结构中也是学过的， 可是当时学的时候， 也许是不够努力，学的模模糊糊的，也没有将Prim 算法和 Kruskal 算法搞清楚，只是能简单的利用知识做题， 却不能很清楚地讲明白这两种算法的原理差别， 更别说是编程设计了，那就根本想都不要想， 完全不知所措，在之前的数据结构中，很多涉及到图的实现，尤其那些代码实在是晦涩难懂， 搞得我实在不想学习，后来在算法课上学到的东西就有点不同了， 也许是经过时间的打磨， 感觉到现在的代码没有那么难懂了，也终于弄明白了两者的区别
6、，感觉好多了。实验得分助教签名附录：附录：完整代码（贪心法）完整代码（贪心法）/贪心算法最小生成树prim算法#include#include#include#include#includeusing namespace std;#define inf 9999;/定义无限大的值const int N=6;template/模板定义void Prim(int n,Type cN+1);int main()int cN+1N+1;cout连通带权图的矩阵为：endl;for(int i=1;i=N;i+)/输入邻接矩阵for(int j=1;jcij;coutPrim算法最小生成树选边次序如下：
7、endl;clock_t start,end,over;/计算程序运行时间的算法start=clock();end=clock();over=end-start;start=clock();Prim(N,c);/调用Prim算法函数end=clock();printf(The time is %6.3f,(double)(end-start-over)/CLK_TCK); /显示运行时间coutendl;system(pause);return 0;template/参数为结点个数n，和无向带权图中各结点之间的距离cN+1void Prim(int n,Type cN+1)Type lowco
8、stN+1;/记录cjclosest的最小权值int closestN+1;/V-S中点j在s中的最临接顶点bool sN+1;/标记各结点是否已经放入S集合s1=true;/初始化si,lowcosti,closestifor(int i=2;i=n;i+)lowcosti=c1i;closesti=1;si=false;for(int i=1;in;i+)Type min=inf;int j=1;for(int k=2;k=n;k+)/找出V-S中是lowcost最小的顶点j4 / 5if(lowcostkmin)&(!sk)/如果k的lowcost比min小并且k结点没有被访问min=lowcostk;/更新min的值j=k;coutj closestjendl;/输出j和最邻近j的点sj=true;/将j添加到s中for(int k=2;k=n;k+)if(cjklowcostk)&(!sk)/s集合放进j后更新各结点的lowcost的值lowcostk=cjk;closestk=j;5 / 5