最小耗费生成树Prim算法实验报告.doc

学生实验报告学院:软件与通信工程学院课程名称:算法设计与分析专业班级:软件工程142班姓名:周平学号:学生实验报告学生姓名周平学号同组人:无实验项目最小耗费生成树Prim算法□必修☑选修□演示性实验□验证性实验☑操作性实验□综合性实验实验地点W101实验仪器台号K03指导教师尹爱华实验日期及节次5-234一、实验综述实现贪心法的下列六个算法之一:1、可切割背包问题2、单源点最短路径求解算法——Dijkstra算法3、Dijkstra算法的改进版4、最小耗费生成树Kruskal算法5、最小耗费生成树Prim算法6、最小耗费生成树Prim算法的改进版要求与说明:1、各人独立完成,2、实验报告要求有:算法说明与描述、代码、数据集合(各算法1要求达到百、千级)。3、实验报告要有2-3个截图,包括导入数据、重要中间过程、最后结果等;4、额外完成所实现的算法,每完成一个加1分;5、程序要求用C语言完成,每个实验报告的代码都会被测试,对运行环境有特别要求的需要专门说明,否则,程序测试不通过责任自负;6、实验报告都有步骤分,但是,程序测试结果与实验报告结果不相符的,将被加重扣分;7、严禁抄袭——代码重复度超过90%者视作抄袭,抄袭者以0分记,可以对评审提出质疑。疑。2、实验仪器、设备或软件1、个人电脑2、MicrosoftVisualStudio2015二、实验过程(实验步骤、记录、数据、分析)实验代码如下:#include<>#include<>#defineMAX100#defineMAXCOST0x7fffffffintgraph[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]; inti,j,min,minid,sum=0; /*默认选择1号节点加入生成树,从2号节点开始初始化*/ for(i=2;i<=n;i++) { /*最短距离初始化为其他节点到1号节点的距离*/ lowcost[i]=graph[1][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&&lowcost[j]!=0) { min=lowcost[j]; minid=j; } } /*输出生成树边的信息:起点,终点,权值*/ printf("%c-%c:%d\n",mst[minid]+'A'-1,minid+'A'-1,min); /*累加权值*/ sum+=min; /*标记节点minid加入生成树*/ lowcost[minid]=0; /*更新当前节点minid到其他节点的权值*/ for(j