《贪心算法设计实验报告》由会员分享，可在线阅读，更多相关《贪心算法设计实验报告（15页珍藏版）》请在金锄头文库上搜索。
1、湖北工业大学计算机学院网络工程系2009 年编制1 算法设计技巧与分析课程实验报告实验名称贪心算法的运用实验序号姓名系院专业班级学号实验日期指导教师成绩一、实验目的1. 掌握贪心算法的基本概念和两个基本要素2. 熟练掌握贪心算法解决问题的基本步骤3. 学会利用贪心算法解决实际问题二、实验内容与要求1，实现贪心算法的经典运用- Kruskal 算法（最小生成树）2，实现贪心算法的经典运用-Prim 算法（最小生成树）三、实验设备地点：科技楼网络实验室602 硬件环境：Intel Pentium Processor 1.8G ， 512M 内存 ，windows 操作系统软件环境：VC+6.0 五
2、、实验步骤1.用 Kruskal 算法实现最小生成树算法描述 ：假设WN=(V,E) 是一个含有n 个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有n 棵树的一个森林。之后，从网的边集E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有n-1 条边为止。湖北工业大学计算机学院网络
3、工程系2009 年编制2 下面给出c 语言代码实现及说明本程序对树的存储主要是以边为存储对象，即边的结构体里面有这样几个参数：1，边的权值。 2，边的一个顶点。3，边的另一个顶点。4，边是否属于生成树的一条边（即最小生成树边标志）。由该程序的存储结构决定了该算法比较适用于边稀疏的情形，至于边稠密的情况会在下面的Prim算法中给出。在 Kruskal 算法中有两个比较重要的部分1，对边按权重排序。2，对一条边加入子树后是否会产生回路的判断即判断边的两个节点是否在同一个树中（集合里）对于问题1：可以有各种排序算法，读者可以自行选择自己喜欢的排序算法来替换代码中的排序算法。 （本处使用选择排序算法（
4、效率较低），读者可以自己修改为快速排序或者是对排序）下面主要讲解解决问题2，解决这个问题一般借用不相交集的思想，即在本程序中每次以同集合中所有点的编号最小的数来标识本集合。（对于根节点即标号最小的节点则标记为0）例如对于上图实例，下面给出详细的不相交集的维护过程（给出前几步的详细说明）a,初始状态（ ABCDEFG 分别在数组的第1，2，3，4， 5，6，7）0 号位空置（均为0）b,选择第一条边A-D( 将 D 的标记改为1)（因为 AD 最短）对表进行维护（维护后仍同上表，因为还没有两个集合合并）C，选择第二条边C-E （修改上表）对上表进行维护（任同上表，因为还没有两个集合合并）D，选择
5、第三条边（D-F ）(根据条件DF 两点不再同一集合，改边可选) 然后就合并DF 两点所在的集合D 的前去是1，即 A 标记为 0，E 的标记也为0，合并因为61所以表修改如下0 A B C D E F G 0 0 0 0 0 0 0 0 0 A B C D E F G 0 0 0 0 1 0 0 0 0 A B C D E F G 0 0 0 0 1 0 0 0 0 A B C D E F G 0 0 0 0 1 3 0 0 0 A B C D E F G 0 0 0 0 1 3 0 0 0 A B C D E F G 0 0 0 0 1 3 1 0 湖北工业大学计算机学院网络工程系2009
6、 年编制3 以后几步均如上判断两点是否在一个集合从而判断改边是否可取，并维护上表下面附上源代码/* Kruskal 算法的实现09 网一殷赛0910322113 输入：图G(用结构体数组来存储每条边，包含每条边的节点）输出：图G 的最小生成树树*/ #include #include typedef struct Edge char dot_1; char dot_2; int weight; int leap; Edge; Edge* selectionsort(Edge *array,int n)/ 选择排序（对边按权重由高到低排序） int i,j,min,temp; for(i=0;i
7、arrayj.weight) min=j; if(min!=i) temp=arrayi.weight; 湖北工业大学计算机学院网络工程系2009 年编制4 arrayi.weight=arraymin.weight; arraymin.weight=temp; temp=arrayi.dot_1; arrayi.dot_1=arraymin.dot_1; arraymin.dot_1=temp; temp=arrayi.dot_2; arrayi.dot_2=arraymin.dot_2; arraymin.dot_2=temp; return array; Edge *Kruskal(Ed
8、ge *Graph,int num_e,int *V,int num_v)/ 克鲁斯卡尔算法实现 int m,n,test; int i,j,t,k; for(i=0;iV1n) V1V1m=V1n; else V1V1n=V1m; /维护不相交集k=1;/ 对每个节点都检查是否为标记合格节点while(kn) V1m=n; else V1n=m; /维护不相交集k=1; while(k #include #define INF 32767 /* Prim 算法最重要的部分在于从可以挑选的边中间挑选出最小值并且对加入后会产生回路的边标记为不可选（此代码中将该边权值标记为INF 即无穷大）每选中
9、一条边就会加入一个点（就必须对与该点连接的边进行维护，即多产生回路边标记为无穷）找最小边则是从上三角中所有可选的行和列中选择选中的树边则标记为-1（其权值从下三角读出）湖北工业大学计算机学院网络工程系2009 年编制11 */ void Prim(int *Graph,int num_v)/转化为对上三角的维护 int i,j,leap=0,temp; int m,n,min; int *a=(int *)malloc(sizeof(int)*num_v); for(i=0;iGraphij m=j; n=i; temp=0; for(j=0;jGraphji 湖北工业大学计算机学院网络工程系
10、2009 年编制12 m=j; n=i; temp=1; if(temp=0)/ 为了区别出是在行还是在列中搜索到的元素Graphnm=-1; else Graphmn=-1; for(i=0;i0) Graphim=INF; for(i=m+1;i0) Graphmi=INF; am=1; /* for(i=0;inum_v;i+)/检查矩阵中在那些行（列）可以选择最小值（即那些列和行是候选行和列）printf(“%-4d“,ai); 湖北工业大学计算机学院网络工程系2009 年编制13 printf(“n“);*/ /* for(i=0;inum_v;i+)/检验对上三角的维护，和下三角是
11、否修改了（下三角保存了原树和用于输出最小生成树） for(j=0;jnum_v;j+) printf(“%-4dt“,Graphij); printf(“n“); */ leap+; void main() int i,j; int num_v,num_e; int *Graph=NULL; char *V=NULL; char ch_1,ch_2; int weight; int m,n; printf(“ 请输入图的顶点数：“); scanf(“%d“, V=(char*)malloc(sizeof(char)*num_v); Graph=(int*)malloc(sizeof(int*)
12、*num_v);/动态生成二维数组用来存储图（邻接矩阵）for(i=0;inum_v;i+) Graphi=(int*)malloc(sizeof(int)*num_v); for(i=0;inum_v;i+)/初始化矩阵for(j=0;jnum_v;j+) 湖北工业大学计算机学院网络工程系2009 年编制14 Graphij=INF; for(i=0;inum_v;i+) Graphii=0; for(i=0;inum_v;i+) printf(“ 请输入第 %d 个顶点 :“,i+1); scanf(“ %c“, printf(“ 请输入图的边数：“); scanf(“%d“, for(i
13、=0;inum_e;i+) printf(“ 请输入第 %d 条边的顶点和权值:“,i+1); scanf(“ %c %c%d“, for(j=0;jnum_v;j+) if(Vj=ch_1) m=j; if(Vj=ch_2) n=j; Graphmn=weight; Graphnm=weight; /以上是对图用邻接矩阵存储/- Prim(Graph,num_v); printf(“ 最小生成树如下：n“); 湖北工业大学计算机学院网络工程系2009 年编制15 printf(“ 顶点 - 顶点 - 权值 n“); weight=0; for(i=0;inum_v;i+) for(j=i+1;jnum_v;j+) if(Graphij=-1) printf(“ %-2c - %-2c - %-2dn“,Vi,Vj,Graphji); weight=weight+Graphji; printf(“ 最小生成树的权重是：%dn“,weight); 六、实验结果与分析Kruskal 算法适用于边稀疏的情形，而Prim 算法适用于边稠密的情形
