5图的最小生成树(贪心策略).doc

5图的最小生成树(贪心策略).doc天津商业大学学生实验报告学院名称信息工程学院年级、专业、班计科1303班学号20134390姓名吴雪婷同组姓名无课程名称算法分析与设计实验项目名称图的最小生成树(贪心策略)指导教师杨亮实验类型验证□J 综合口 设计口 创新口成绩开课实验室:403机房开课时间2015年3月1日实验报告2015年4月14日实验报告内容一般包括以下几个内容:1、目的要求2、仪器用具及材料(仪器名称及主要规格、用具名称)3、实验内容及原理(简单但要抓住要点,写出依据原理)4、操作方法与实验步骤5、数据图表格(照片)6、实验过程原始记录7数据处理及结果(按实验要求处理数据、结论)8、讨论(对实验中存在的问题、进一步的想法等进行讨论)一、实验目的通过编程实现最小生成树,增强对贪心策略的理解。二、实验内容编程用Prim方法和Kruskal方法求解最小生成树,并完成实验报告(要求粘贴代码和实验结果截图)。三、实验步骤和过程当求解最优化问题是,虽然动态规划的方法可以求解,但是使用贪心策略实现起来要更加容易,所以贪心策略就是每次只构造局部最优解,而这个局部最优解却可以得到最后的全局最优解。用來求解最小生成树的两种方法都使用了贪心的策略。实验代码://图的最小生成树#inelude<>tiinclude<>ttdefineMAX100iidefineMAXCOST0x7fffffffintgraph[MAX][MAX];intPrim(intgraph[][MAX],intn){/*lowcost[i]记录以i为终点的边的最小权值,当lowcost[i]=0时表示终点i加入牛成树*/intlowcost[MAX];/*mst[i]记录对应lowcost[i]的起点,当mst[i]=0时表示起点i加入生成树*/intmst[MAX];int i, j, min, minid, sum 二0;/*默认选择1号节点加入生成树,从2号节点开始初始化*/for (i = 2;i <=n; i++)/*最短距离初始化为其他节点到1号节点的距离*/lowcost[i]二graph[l][i];/*标记所有节点的起点皆为默认的1号节点*/mst[i] = 1;}/*标记1号节点加入生成树*/mst[1]二0;/*n个节点至少需要n-1条边构成最小生成树*/for(i二2;i<=n;i++){min二MAXCOST;minid= 0;/*找满足条件的最小权值边的节点minid*/for(j= 2;j<=n;j++)/*边权值较小且不在生成树中*/if(lowcost[j]<min&&flowcost[j] !=0)Xmin=lowcost[j];minid二j;}}/*输出生成树边的信息:起点,终点,权值*/printf(,?%c -%c: %d\n〃,■Tmst[minid]+,A'/*累加权值*/1,minid+ 'A'1,min)sum+=min;/*标记节点minid加入生成树*/lowcost[minid]= 0;/*更新当前节点minid到其他节点的权值*/for(j= 2;j<=n;j++){/*发现更小的权值*/if(graph[minid][j] <lowcost[j]){/*更新权值信息*/lowcost[j]二graph[minid][j];/*更新最小