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

天津商业大学学生实验报告 开课实验室： 403 机房 开课时间 2015年 3 月 1日 实验报告 2015年 4月 14 日 学院名称信息工程学院年级、专业、班计科1303班学号20134390姓名吴雪婷同组姓名 无课程名称算法分析与设计实验项目名称图的最小生成树（贪心策略）指导教师杨亮实验类型 验证 综合 设计 创新成绩实验报告内容一般包括以下几个内容：1、目的要求 2、仪器用具及材料（仪器名称及主要规格、用具名称） 3、实验内容及原理（简单但要抓住要点，写出依据原理） 4、操作方法与实验步骤 5、数据图表格（照片） 6、实验过程原始记录 7数据处理及结果（按实验要求处理数据、结论） 8、讨论（对实验中存在的问题、进一步的想法等进行讨论）一、实验目的通过编程实现最小生成树，增强对贪心策略的理解 。二、实验内容编程用 Prim 方法和 Kruskal 方法求解最小生成树，并完成实验报告（要求粘贴代码和实验结果截图） 。三、实验步骤和过程当求解最优化问题是，虽然动态规划的方法可以求解，但是使用贪心策略实现起来要更加容易，所以贪心策略就是每次只构造局部最优解，而这个局部最优解却可以得到最后的全局最优解。 用来求解最小生成树的两种方法都使用了贪心的策略。实验代码：/图的最小生成树#include#include#defineMAX100#defineMAXCOST0x7fffffffintgraphMAXMAX;intPrim(intgraphMAX,intn)/*lowcosti记录以i为终点的边的最小权值，当lowcosti=0时表示终点i加入生成树*/intlowcostMAX;/*msti记录对应lowcosti的起点，当msti=0时表示起点i加入生成树*/intmstMAX;inti,j,min,minid,sum=0;/*默认选择1号节点加入生成树，从2号节点开始初始化*/for(i=2;i=n;i+)/*最短距离初始化为其他节点到1号节点的距离*/lowcosti=graph1i;/*标记所有节点的起点皆为默认的1号节点*/msti=1;/*标记1号节点加入生成树*/mst1=0;/*n个节点至少需要n-1条边构成最小生成树*/for(i=2;i=n;i+)min=MAXCOST;minid=0;/*找满足条件的最小权值边的节点minid*/for(j=2;j=n;j+)/*边权值较小且不在生成树中*/if(lowcostjmin&lowcostj!=0)min=lowcostj;minid=j;/*输出生成树边的信息:起点，终点，权值*/printf(%c-%c:%dn,mstminid+A-1,minid+A-1,min);/*累加权值*/sum+=min;/*标记节点minid加入生成树*/lowcostminid=0;/*更新当前节点minid到其他节点的权值*/for(j=2;j=n;j+)/*发现更小的权值*/if(graphminidjlowcostj)/*更新权值信息*/lowcostj=graphminidj;/*更新最小权值边的起点*/mstj=minid;/*返回最小权值和*/returnsum;intmain()inti,j,k,m,n;intx,y,cost;charchx,chy;/*读取节点和边的数目*/scanf(%d%d,&m,&n);getchar();/*初始化图，所有节点间距离为无穷大*/for(i=1;i=m;i+)for(j=1;j=m;j+)graphij=MAXCOST;/*读取边信息*/for(k=0;kn;k+)scanf(%c%c%d,&chx,&chy,&cost);getchar();i=chx-A+1;j=chy-A+1;graphij=cost;graphji=cost;/*求解最小生成树*/cost=Prim(graph,m);/*输出最小权值和*/printf(Total:%dn,cost);/system(pause);return0; 实验截图：注1.每个实验项目一份实验报告。2.实验报告第一页学生必须使用规定的实验报告纸书