贪心算法设计实验报告

湖北工业大学计算机学院网络工程系·2009年编制1《算法设计技巧与分析》课程实验报告实验名称贪心算法的运用实验序号姓名系院专业班级学号实验日期指导教师成绩一、实验目的1.掌握贪心算法的基本概念和两个基本要素2.熟练掌握贪心算法解决问题的基本步骤3.学会利用贪心算法解决实际问题二、实验内容与要求1，实现贪心算法的经典运用-------Kruskal算法（最小生成树）2，实现贪心算法的经典运用-------Prim算法（最小生成树）三、实验设备地点：科技楼网络实验室602硬件环境：IntelPentiumProcessor1.8G，512M内存，windows操作系统软件环境：VC++6.0五、实验步骤1.用Kruskal算法实现最小生成树算法描述：假设WN=(V,{E})是一个含有n个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有n棵树的一个森林。之后，从网的边集E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有n-1条边为止。湖北工业大学计算机学院网络工程系·2009年编制2下面给出c语言代码实现及说明本程序对树的存储主要是以边为存储对象，即边的结构体里面有这样几个参数：1，边的权值。2，边的一个顶点。3，边的另一个顶点。4，边是否属于生成树的一条边（即最小生成树边标志）。由该程序的存储结构决定了该算法比较适用于边稀疏的情形，至于边稠密的情况会在下面的Prim算法中给出。在Kruskal算法中有两个比较重要的部分1，对边按权重排序。2，对一条边加入子树后是否会产生回路的判断即判断边的两个节点是否在同一个树中（集合里）对于问题1：可以有各种排序算法，读者可以自行选择自己喜欢的排序算法来替换代码中的排序算法。（本处使用选择排序算法（效率较低），读者可以自己修改为快速排序或者是对排序）下面主要讲解解决问题2，解决这个问题一般借用不相交集的思想，即在本程序中每次以同集合中所有点的编号最小的数来标识本集合。（对于根节点即标号最小的节点则标记为0）例如对于上图实例，下面给出详细的不相交集的维护过程（给出前几步的详细说明）a,初始状态（ABCDEFG分别在数组的第1，2，3，4，5，6，7）0号位空置（均为0）b,选择第一条边A---D(将D的标记改为1)（因为AD最短）对表进行维护（维护后仍同上表，因为还没有两个集合合并）C，选择第二条边C----E（修改上表）对上表进行维护（任同上表，因为还没有两个集合合并）D，选择第三条边（D-----F）(根据条件DF两点不再同一集合，改边可选)然后就合并DF两点所在的集合D的前去是1，即A标记为0，E的标记也为0，合并因为61所以表修改如下0ABCDEFG000000000ABCDEFG000010000ABCDEFG000010000ABCDEFG000013000ABCDEFG000013000ABCDEFG00001310湖北工业大学计算机学院网络工程系·2009年编制3以后几步均如上判断两点是否在一个集合从而判断改边是否可取，并维护上表下面附上源代码/**************************************************************************************************Kruskal算法的实现09网一殷赛0910322113输入：图G(用结构体数组来存储每条边，包含每条边的节点）输出：图G的最小生成树树***************************************************************************************************/#includestdio.h#includestdlib.htypedefstructEdge{chardot_1;chardot_2;intweight;intleap;}Edge;Edge*selectionsort(Edge*array,intn)//选择排序（对边按权重由高到低排序）{inti,j,min,temp;for(i=0;in;i++){min=i;for(j=i+1;jn;j++)if(array[min].weightarray[j].weight)min=j;if(min!=i){temp=array[i].weight;湖北工业大学计算机学院网络工程系·2009年编制4array[i].weight=array[min].weight;array[min].weight=temp;temp=array[i].dot_1;array[i].dot_1=array[min].dot_1;array[min].dot_1=temp;temp=array[i].dot_2;array[i].dot_2=array[min].dot_2;array[min].dot_2=temp;}}returnarray;}Edge*Kruskal(Edge*Graph,intnum_e,int**V,intnum_v)//克鲁斯卡尔算法实现{intm,n,test;inti,j,t,k;for(i=0;inum_e;i++){for(j=1;jnum_v+1;j++){if(Graph[i].dot_1==V[0][j])m=j;if(Graph[i].dot_2==V[0][j])n=j;}if(V[1][m]!=V[1][n]&&m!=V[1][n]&&n!=V[1][m])//如果边的两个顶点不再一个集合则边是生成树的边(注意首节点的标记和集合里非首节点的标记不同)湖北工业大学计算机学院网络工程系·2009年编制5{Graph[i].leap=1;if(V[1][n]==0){if(nV[1][m])V[1][V[1][m]]=n;elseV[1][n]=V[1][m];}else{if(V[1][m]==0){if(mV[1][n])V[1][V[1][n]]=m;elseV[1][m]=V[1][n];}else{if(V[1][m]V[1][n])V[1][V[1][m]]=V[1][n];elseV[1][V[1][n]]=V[1][m];}}//维护不相交集k=1;//对每个节点都检查是否为标记合格节点while(knum_v+1){if(V[1][k]!=0)//只要标记不为0都进行整理,只不过有些节点的标记整理前后是湖北工业大学计算机学院网络工程系·2009年编制6一样的(即标记符合标准的节点){t=V[1][k];while(V[1][t]!=0){t=V[1][t];}V[1][k]=t;}k++;}}if(V[1][m]==0&&V[1][n]==0)//如果边的两个顶点是两个集合的首节点则可以合并{Graph[i].leap=1;if(mn)V[1][m]=n;elseV[1][n]=m;//维护不相交集k=1;while(knum_v+1){if(V[1][k]!=0){t=V[1][k];while(V[1][t]!=0){t=V[1][t];}V[1][k]=t;湖北工业大学计算机学院网络工程系·2009年编制7}k++;}}/*printf(不相交集的情况：\n);for(test=1;testnum_v+1;test++)printf(%-4c,V[0][test]);printf(\n);for(test=1;testnum_v+1;test++)printf(%-4d,V[1][test]);printf(\n);*/}returnGraph;}voidmain(){inti,j,num_v,num_e,cost=0;Edge*Graph=NULL;int**V=NULL;printf(请输入土中有多少个顶点!\n);scanf(%d,&num_v);V=(int**)malloc(sizeof(int*)*2);for(i=0;i2;i++)V[i]=(int*)malloc(sizeof(int)*(num_v+1));for(i=0;i2;i++)for(j=0;jnum_v+1;j++)V[i][j]=0;for(i=1;inum_v+1;i++)湖北工业大学计算机学院网络工程系·2009年编制8{printf(请输入第%d个顶点:,i);scanf(%c,&V[0][i]);}printf(请输入图中有多少条边!\n);scanf(%d,&num_e);Graph=(Edge*)malloc(sizeof(Edge)*num_e);for(i=0;inum_e;i++){printf(请输入第%d条边的权值和两个顶点！\n,i+1);scanf(%d%c%c,&Graph[i].weight,&Graph[i].dot_1,&Graph[i].dot_2);Graph[i].leap=0;}Graph=selectionsort(Graph,num_e);//以上部分是存储图//--------------------------------------------------------------------------------------------------Graph=Kruskal(Graph,num_e,V,num_v);printf(构成最小生成树的边和顶点分别是：\n);printf(顶点1------------顶点2-------------边\n);for(i=0;inum_e;i++){if(Graph[i].leap==1){printf(%c------------%c-------------%d\n,Graph[i].dot_1,Graph[i].dot_2,Graph[i].weight);cost=cost+Graph[i].weight;}}printf(最小生成树的权值是：%d\n,cost);}湖北工业大学计算机学院网络工程系·2009年编制92.用Prim算法实现最小生成树算法描述：假设V是图中顶点的集合,E是图中边的集合,TE为最小生成树中的边的集合,则prim算法通过以下步骤可以得到最小生成树:1:初始化:U={u0},TE={f}。此步骤设立一个只有结点u0的结点集U和一个空的边集TE作为最小生成树的初始形态,在随后的算法执行中,这个形态会不断的发生变化,直到得到最小生成树为止。2:在所有u∈U,v∈V－U的边(u,v)∈E中,找一条权最小的边(u0,v0)，将此边加进集合TE中，并将此边的非U中顶点加入U中。此步骤的功能是在边集E中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和V－U中,其次边的权要最小。找到这条边以后,把这条边放到边集TE中,并把这条边上不在U中的那个顶点加入到U中。这一步骤在算法中应执行多次,每执行一次,集合TE和U都将发生变化,分别增加一条边和一个顶点,因此,TE和U是两个动态的集合,这一点在理解算法时要密切注意。湖北工业大学计算机学院网络工程系·2009年编制103:如果U=V,则算法结束;否则重复步骤2。可以把本步骤看成循环终止条件。我们可以算出当U=V时,步骤2共执行了n－1次(设n为图中顶点的数目),TE中也增加了n－1条边,这n－1条边就是需要求出的最小生成树的边（图任如上图）下面给出具体c语言代码和详解该代码的存储结构是邻接矩阵上三角用来存储最小生成树的边，树边用-1标记，下三角用来存储原图，方便输出最小生成树上图的最后邻接矩阵如下：（具体实现和解释见代码）(INF代表无穷