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

《最小耗费生成树Prim算法实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、学生实验报告学院：软件与通信工程学院课程名称：算法设计与分析专业班级：软件工程142班姓名：周平学号：学生实验报告学生姓名周平学号同组人：无实验项目最小耗费生成树Prim算法□必修☑选修□演示性实验□验证性实验☑操作性实验□综合性实验实验地点W101实验仪器台号K03指导教师尹爱华实验日期及节次5-234一、实验综述实现贪心法的下列六个算法之一：1、可切割背包问题2、单源点最短路径求解算法——Dijkstra算法3、Dijkstra算法的改进版4、最小耗费生成树Kruskal算法5、最小耗费生成树Prim算法6、最小耗费生成树Prim算法的

2、改进版要求与说明：1、各人独立完成，2、实验报告要求有：算法说明与描述、代码、数据集合（各算法1要求达到百、千级）。3、实验报告要有2-3个截图，包括导入数据、重要中间过程、最后结果等；4、额外完成所实现的算法，每完成一个加1分；5、程序要求用C语言完成，每个实验报告的代码都会被测试，对运行环境有特别要求的需要专门说明，否则，程序测试不通过责任自负；6、实验报告都有步骤分，但是，程序测试结果与实验报告结果不相符的，将被加重扣分；7、严禁抄袭——代码重复度超过90%者视作抄袭，抄袭者以0分记，可以对评审提出质疑。疑。2、实验仪器、设备或软件1

3、、个人电脑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]的

4、起点，当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;/*

5、找满足条件的最小权值边的节点minid*/for(j=2;j<=n;j++){/*边权值较小且不在生成树中*/if(lowcost[j]

6、j<=n;j++){/*发现更小的权值*/if(graph[minid][j]

7、始化图，所有节点间距离为无穷大*/for(i=1;i<=m;i++){for(j=1;j<=m;j++){graph[i][j]=MAXCOST;}}/*读取边信息*/for(k=0;k

8、stem("pause");return0;}代码说明：1、2个for循环都是从2开始的，因为一般我们默认开始就把第一个节点加入生成树，因此之后不需要再次寻找它。2、lowcos