1、贪心算法实验最小生成树算法分析与设计实验报告第一次附加实验姓名学号班级时间12.12上午地点工训楼309实验名称贪心算法实验(最小生成树)实验目的通过上机实验，要求掌握贪心算法的思想，利用 prim算法求解最小生成树并实现。实验原理设G=(V,E)是连通带权图， V=1,2, ，nG。的最小生成树的 Prim算法的基本思想是：首先置S=1，然后，只要S是V的真子集，就作如下的贪心 选择：选取满足条件i S, j V-S，且ci j最小的边，将顶点j添加到S中。 这个过程一直进行到 S=V时为止。在这个过程中选取到的所有边恰好构成 G的一棵最小生成树。实验步骤(1 )用邻接矩阵表示无向图，并进行
2、初始化，冋时选择源点放在集合 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; /标记各结点是否已经放入集合s中s
3、1= true ;/ 初始化 si,lowcosti,closestifor (i nt i=2;i=n ;i+)lowcosti=c1i;closesti=1;si= false ;for (i nt i=1;i n ;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;coutvvjvv closestjendl; / 输出 j和最邻近 j的
4、点sj= true ;/ 将j添加到集合s中for (int k=2;k=n;k+)if(cjklowcostk)&(!sk) /s 集合放进 j 后更新各结点的lowcost的值lowcostk=cjk;closestk=j;输入较小的有向带权图结果：测试结果 1 F 弭 1(5斂心舜法胪 1 lt gin exo连通带权图的姮畛厂99習7 6 5 9999 9999 999 G 9999 3 99991 5 ? S 6 45 5 9999 29999 9 6 9999 9999 9沖9汕沾4 2 6些汕甘山”算法最/ J、生成侖扌选边次序如F:2 16 34 6n *The t ime i
5、s M.UU2F青按任意犍雄绫实验分析再求最小生成树的实验中， 有两种算法：一种是Prim算法，一种是Kruskal 算法。在两种算法中，我们可以比较 Prim算法，是通过集合 S中的点来更新 另一个集合的点距这个已经生成的树的最短距离， 而Kruskal算法是每次都选择最短的边加入到生成树集合中， 其实两种算法其思想是不同的， 所以两种算 法的时间复杂度也是不同的， Prim算法的时间复杂度是 0 (nA2 )，而Kruskal 算法的时间复杂度是 0 (nlogn ),相比来讲，在时间上 Kruskal更好一点。实验心得最小生成树在之前的数据结构中也是学过的， 可是当时学的时候， 也许是不
6、够努力，学的模模糊糊的，也没有将 Prim算法和Kruskal算法搞清楚，只是能简单的利用知识做题， 却不能很清楚地讲明白这两种算法的原理差别， 更别说是编程设计了， 那就根本想都不要想， 完全不知所措，在之前的数据结构中，很多涉及到图的实现， 尤其那些代码实在是晦涩难懂， 搞得我实在不想学习，后来在算法课上学到的东西就有点不同了， 也许是经过时间的打磨， 感觉到现在的代码没有那么难懂了，也终于弄明白了两者的区别，感觉好多了。实验得分助教签名附录：完整代码(贪心法)/贪心算法 最小生成树prim算法#include #inelude #inelude #inelude #include usi
7、ng namespace std;#define inf 9999; /定义无限大的值const int N=6;template / 模板定义void Prim( int n,Type cN+1);int mai n()int cN+1N+1;cout 连通带权图的矩阵为：endl;for (int i=1;i=N;i+) / 输入邻接矩阵for (int j=1;jcij;cout Prim 算法最小生成树选边次序如下： endl;clock_t start,end,over; / 计算程序运行时间的算法start=clock();end=clock();over=end-start;st
8、art=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 lowcostN+1; / 记录cjclosest的最小权值int closestN+1; /V-S中点j在s中的最临接顶点bool sN+1; /标记
9、各结点是否已经放入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 最小的顶点 jif (lowcostkmin)&(!sk) / 如果 k 的 lowcost 比min 小并且 k结点没有被访问min=lowcostk; / 更新 min 的值j=k;coutvvjvv closestjvvendl; / 输出 j和最邻近 j的点sj= true ; / 将j添加到 s 中for (int k=2;k=n;k+)if (cjklowcostk)&(!sk) /s 集合放进 j 后更新各结点的lowcost 的值lowcostk=cjk;closestk=j;
