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

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