贪心算法设计实验报告.pdf

《贪心算法设计实验报告.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、湖北工业大学计算机学院《算法设计技巧与分析》课程实验报告实验名称贪心算法的运用实验序号姓名系院专业班级学号实验日期指导教师成绩一、实验目的1.掌握贪心算法的基本概念和两个基本要素2.熟练掌握贪心算法解决问题的基本步骤3.学会利用贪心算法解决实际问题二、实验内容与要求1，实现贪心算法的经典运用-------Kruskal算法（最小生成树）2，实现贪心算法的经典运用-------Prim算法（最小生成树）三、实验设备地点：科技楼网络实验室602硬件环境：IntelPentiumProcessor1.8G，512M

2、内存，windows操作系统软件环境：VC++6.0五、实验步骤1.用Kruskal算法实现最小生成树算法描述：假设WN=(V,{E})是一个含有n个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有n棵树的一个森林。之后，从网的边集E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可

3、取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有n-1条边为止。1网络工程系·2009年编制湖北工业大学计算机学院下面给出c语言代码实现及说明本程序对树的存储主要是以边为存储对象，即边的结构体里面有这样几个参数：1，边的权值。2，边的一个顶点。3，边的另一个顶点。4，边是否属于生成树的一条边（即最小生成树边标志）。由该程序的存储结构决定了该算法比较适用于边稀疏的情形，至于边稠密的情况会在下面的Prim算法中给出。在Kruskal算法中有两个比较重要的部分1，对边按权重排序。

4、2，对一条边加入子树后是否会产生回路的判断即判断边的两个节点是否在同一个树中（集合里）对于问题1：可以有各种排序算法，读者可以自行选择自己喜欢的排序算法来替换代码中的排序算法。（本处使用选择排序算法（效率较低），读者可以自己修改为快速排序或者是对排序）下面主要讲解解决问题2，解决这个问题一般借用不相交集的思想，即在本程序中每次以同集合中所有点的编号最小的数来标识本集合。（对于根节点即标号最小的节点则标记为0）例如对于上图实例，下面给出详细的不相交集的维护过程（给出前几步的详细说明）a,初始状态（ABCDEFG

5、分别在数组的第1，2，3，4，5，6，7）0号位空置（均为0）0ABCDEFG00000000b,选择第一条边A---D(将D的标记改为1)（因为AD最短）0ABCDEFG00001000对表进行维护（维护后仍同上表，因为还没有两个集合合并）0ABCDEFG00001000C，选择第二条边C----E（修改上表）0ABCDEFG00001300对上表进行维护（任同上表，因为还没有两个集合合并）0ABCDEFG00001300D，选择第三条边（D-----F）(根据条件DF两点不再同一集合，改边可选)然后就合并

6、DF两点所在的集合D的前去是1，即A标记为0，E的标记也为0，合并因为6>1所以表修改如下0ABCDEFG000013102网络工程系·2009年编制湖北工业大学计算机学院以后几步均如上判断两点是否在一个集合从而判断改边是否可取，并维护上表下面附上源代码/**************************************************************************************************Kruskal算法的实现09网一殷赛0910322113输入：

7、图G(用结构体数组来存储每条边，包含每条边的节点）输出：图G的最小生成树树***************************************************************************************************/#include#includetypedefstructEdge{chardot_1;chardot_2;intweight;intleap;}Edge;Edge*selectionsort(Edge

8、*array,intn)//选择排序（对边按权重由高到低排序）{inti,j,min,temp;for(i=0;iarray[j].weight)min=j;if(min!=i){temp=array[i].weight;3网络工程系·2009年编制湖北工业大学计算机学院array[i].wei