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

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

ID:58182648

大小:209.50 KB

页数:9页

时间:2020-04-26

最小耗费生成树Prim算法实验报告.doc_第1页
最小耗费生成树Prim算法实验报告.doc_第2页
最小耗费生成树Prim算法实验报告.doc_第3页
最小耗费生成树Prim算法实验报告.doc_第4页
最小耗费生成树Prim算法实验报告.doc_第5页
资源描述:

《最小耗费生成树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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。