1、算法设计技巧与分析课程实验报告实验名称贪心算法的运用实验序号姓名系院专业班级学号实验口期指导教师成绩一、实验目的掌握贪心算法的基本概念和两个基本要素熟练掌握贪心算法解决问题的基本步骤学会利用贪心算法解决实际问题二、实验内容与要求1，实现贪心算法的经典运用Krnskal算法（最小生成树）2,实现贪心算法的经典运用Pnm算法（最小生成树）三、实验设备地点：科技楼网络实验室602硬件环境：IntelPentiumProcessor1.8G,512M内存，windows操作系统软件环境：VC+6.0五、实验步骤用Kiuskal算法实现最小生成树算法描述：假设WN=（V,E）是一
2、个含有n个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有a棵树的一个森林。之后，从网的边集E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图,也就是说，将这两个顶点分别所在的两棵树合成一棵树：反之，若该条边的两个顶点己落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有n-1条边为止。G下面给出C语言代码实现及说明本程序对树的存储主要是以边为存储对象，即边的结构体里面有这样几个参数：1,边的权值。
3、2,边的一个顶点。3,边的另一个顶点。4,边是否属于生成树的一条边（即最小生成树边标志）。由该程序的存储结构决定了该算法比较适用于边稀疏的情形，至于边稠密的情况会在卜.面的Pnm算法中给出。在Kiwskal算法中有两个比较重要的部分1,对边按权重排序。2,对一条边加入子树后是否会产生回路的判断即判断边的两个节点是否在同一个树中（集合里）对于问题1：可以有各种排序算法，读者可以自行选择自己喜欢的排序算法来替换代码中的排序算法。（本处使用选择排序算法（效率较低），读者可以自己修改为快速排序或者是对排序）下面主要讲解解决问题2,解决这个问题一般借用不相交集的思想，即在本程序中每次以同集合
4、中所有点的编号最小的数来标识本集合。（对于根节点即标号最小的节点则标记为0）例如对于上图实例，下面给出详细的不相交集的维护过程（给出前几步的详细说明）a,初始状态（ABCDEFG分别在数组的第1,2,3,4,5,6,7）0号位空置（均为0）0ABCDEFG0b,选择第一彳0条边A-D（将0D的标记改0为1）（因为0D最短）0000ABCDEFG0000I000对表进行维护（维护后仍同上表，因为还没有两个集合合并）0ABCDEFG0000I000C,选择第二条边C-E（修改上表）0ABCDEFG0000I300对上表进行维护（任同上表，因为还没有两个集合合并）0ABCDEFG0
5、000I300D,选择第三条边（D-F）（根据条件DF两点不再同一集合，改边可选）然后就合并DF两点所在的集合D的前去是1,即A标记为0,E的标记也为0,合并因为61所以表修改如下0ABcDEFG00001310以后几步均如上判断两点是否在一个集合从而判断改边是否可取，并维护上表下面附上源代码Kiuskal算法的实现09网一殷赛0910322113输入：图G（用结构体数组来存储每条边，包含每条边的节点）输出：图G的最小生成树树*：$：*：$：*：$：*：$：*：$：*：$：*：$：*：$：*：$：*：$：*：$：*：$：*：$：*左*左*：$：*：$：*：$：*/#iiiclude
6、#iiicludetypedefstiuctEdge(chardot_l;chardot_2;intweight;intleap;Edge;Edge*selectioiisort(Edge*arrayintn)选择排序(对边按权重由高到低排序)(intijminjemp;fbi(i=0;in;i+)nun=i;fbr(j=i+lJaiTayj.weight)mm=j;iRmni!=i)temp=anayi.weight;airayi.weight=arraynini.weight;aiTayfnun.weight=temp;temp=anayi.d
7、ot_1;airayi.dot_1=aiTayinin.dot_1;arraymin.dot_1=temp;temp=anayi.dot_2;arrayi.dot_2=arrayniindot_2;arraymin.dot_2=temp;letuinairay;Edge*Kinskal(Edge*Graph,iiitnum_num_v)/克鲁斯卡尔算法实现(intm.njest;mtfoi(i=O;inum_e;i+)fbr(j=l;jnum_v+1;j+)if(Giaphi.dod=V0j)m=j;if(Graphi.do
8、t_2=V0j)n=J；if(V1m!=V1n&m!=V1n&n!=V1m)/Z如果边的两个顶点不再一个集合则边是生成树的边(注意首节点的标记和集合里非首节点的标记不同)Graphi.leap=l;if(Vln=O)JIif(nVln)VlVlm=Vln;elseVlVln=Vlm;)维护不相交集k=l;对每个节点都检查是否为标记合格节点while(knum_v+1)一样的(即标记符合标准的节点)(t=Vlk;wlule(Vlt!=O)(t=Vlt;Vlk=t;)k+;if(V1m=0&V1n=0)/如果边的两个顶点是两个集合的首节点则可以合并Graphi.
9、leap=l;Vlm=n;elseVln=m;维护不相交集k=l；while(knum_v+1)if(Vlk!=O)(t=Vlk;wlule(Vlt!=O)(t=Vlt;k+;/*printf(”不相交集的情况：iiH);fbr(test=1;testnum_v+1;test+)pnntf(”4c”,V0test);fbr(test=1;testnum_v+1;test+)printf(,l%-4dfV1test);returnGraph;voidniainQ(intiJ,num_vjium_e,cost=0;Edge*Graph=NULL;int*V=N
10、ULL;pnntf(”请输入土中有多少个顶点!n”)；scanf(n%d,&num_v);V=(mt*)malloc(sizeof(iiit*)*2);fbr(i=0;i2;i+)Vi=(iiit*)malloc(sizeof(mt)*(num_v+1);fbr(i=0;i2;i+)Rr(j=O；jvnum_v+l；j+)Vij=O;fbr(i=1;inum_v+l;i+)pnntf(”请输入第1个顶点二1);scanff%c,&VOi);printfC请输入图中有多少条边!n)；scanf(n%d,&num_e);Giaph=(Edge*)malloc(sizeof(Edge)
11、*num_e);fbr(i=O;inum_e;i+)pnntf(”请输入第1条边的权值和两个顶点！n”,i+l);scanf(n%d%c%c”.&Graphi.weight,&Graphi.dot_l,&Graphi.dot_2);Graphi.leap=O:Graph=selectionsoit(Graphjium_e);以上部分是存储图/Graph=Kiiiskal(Graph.num_e,V；num_v);printf(构成最小生成树的边和顶点分别是：)；pnntf(”顶点1顶点2边山”)；fbr(i=O;inum_e;i+)if(Graphi.leap=1)printR
12、”%c%c%dn,Graphi.dot_LGraphi.dot_2,Graphi.weight);cost=cost+Graphi.weight;printf(”最小生成树的权值是:%dn,cost);请输入土中有多少个顶点*7敏入篡1个顶京圄$入患6j-顶修F请辙入图中有参少条边？11请输入第i条边的权值和两个顶点！5AD请输入第2条边的权值和两个顶点！AB请输入第3条边的权值和两个顶点！9BD请输入第4条边的权值和两个顶点！BC请输入第5条边的权值和两个顶点！BE请输入第6条边的权值和两个顶点!SCE请输入第条边的权值和两个顶点！帝塞第8条边的权值和两个顶点
13、!整备人第9条边的权值和两个顶点!EF请输入第博条边的权值和两个顶点!EG请输入第11条边的权值和两个顶点!11FG构成最、生成树的边和点分别是;A-CA-C-D一B-A-最泉星成树的权值是：3PressanykeytocontinueDEFEBG用Prun算法实现最小生成树算法描述：假设V是图中顶点的集合,E是图中边的集合,TE为最小生成树中的边的集合，则prmi算法通过以下步骤可以得到最小生成树：1：初始化:U=u0,TE=f此步骤设立一个只有结点u0的结点集U和一个空的边集TE作为最小生成树的初始形态，在随后的算法执行中，这个形态会不断的发生变化
14、,直到得到最小生成树为止。2:在所有uGU,vev-U的边(u,v)GE中，找一条权最小的边(u0,v0),将此边加进集合TE中，并将此边的非U中顶点加入U中。此步骤的功能是在边集E中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和V-U中，其次边的权要最小。找到这条边以后，把这条边放到边集TE中，并把这条边上不在U中的那个顶点加入到U中。这一步骤在算法中应执行多次,每执行一次，集合TE和U都将发生变化，分别增加一条边和一个顶点,因此,TE和U是两个动态的集合,这一点在理解算法时要密切注意。3:如果U=V,则算法结束;否则重复步骤2。可以把本步骤看成循环终止
15、条件。我们可以算出当U=V时，步骤2共执行了n-1次（设n为图中顶点的数目）,TE中也增加了n-1条边，这n-1条边就是需要求出的最小生成树的边（图任如上图）下面给出具体c语言代码和详解该代码的存储结构是邻接矩阵上三角用来存储最小生成树的边，树边用-1标记，下三角用来存储原图，方便输出最小生成树上图的最后邻接矩阵如下：（具体实现和解释见代码）（INF代表无穷，即不相邻）0-1INF-1INFINFINF70INFINF-1INFINFINF80INF-1INFINF59INF0INF-1INFINF75150INF-1INFINFINF680INFINFINFINFINF9110/
16、*09网一殷赛0910322113Prun算法的实现输入：图G输出：图G的最小生成树*/#iiiclude#iiiclude#defiiieINF32767*Pnm算法最重要的部分在于从可以挑选的边中间挑选出最小值并且对加入后会产生回路的边标记为不可选（此代码中将该边权值标记为INF即无穷大）每选中一条边就会加入一个点（就必须对与该点连接的边进行维护，即多产生回路边标记为无穷）找最小边则是从上三角中所有可选的行和列中选择选中的树边则标记为1（其权值从下三角读出）**/voidPrim(int*Graph.iiitnum_v)/转化为对上三角的维护(intiJJeap=
17、Ojemp;intm,njiiin;int*a=(int*)malloc(sizeof(int)*num_v);for(i=0;inum_v;i+)ai=0；a0=l;wliile(leap!=num_v-l)nun=INF:foi(i=0;inum_v;i+)/搜索上三角中的最小值/Iif(ai=l)/Ifbr(j=i+ljGraphi0&Graphi0O)(nun=GraphiIj;m=j;n=i；tenip=0;)for(j=OjviJ+)列中搜索if(minGraphji&Graphji0)nun=Graphji;m=j;n=i;tenip=l;)if(temp=O
18、)为了区别出是在行还是在列中搜索到的元素Graphnm=-1;elseGraphmn=-1;for(i=0;i0)fGraphfim=INF;for(i=m+l;i0)fGraphmi=INF:am=l;/*foi（i=0;inum.v;i+）/检查矩阵中在那些行（列）可以选择最小值（即那些列和行是候选行和列）/*for(i=0;inum_v;i+)/检验对上三角的维护，和下三角是否修改了(下三角保存了原树和用于输出最小生成树)Ifbr(j=0;jnum_vj+)pnntff%4dt”,Graphij);pnntf(nnM);*/leap+;voidmain。(intij;int
19、num_v4ium_e;int*Graph=NULL;char*V=NULL;charch_l,ch_2;intweight;intm.n;printf(请输入图的顶点数：)；scanf(n%d,&num_v);V=(chai*)nialloc(sizeof(char)*num_v);Graph=(mt*)malloc(sizeof(mt*)*num_v)-J!动态生成维数组用来存储图(邻接矩阵)fbr(i=O;inum_v;i-H-)Graphi=(mt*)malloc(sizeof(int)*num-v);for(i=0;inum_v;i+)/初始化矩阵Graphij=INF;fbr(i=O;inum_v;i-H-)Graphii=O;fbr(i=O;inum_v;i-H-)pnntf(”请输入第1个顶点:”,i+1);scanff%c”,&Vi);pnntf(请输入图的边数：”)；scanf(%d,&num_e);fbr(i=O;inum_e;i-H-)pnntf(”请输入第1条边的顶点和权值二i+1);scan町%c%c%d”.&ch_l,&ch_2,&weight);fbr(j=0;jnum_vj+