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

学生们实证报告研究所：软件通信工程学院课程名称：算法设计和分析专业课：软件工程142课姓氏：朱平学号：学生实验报告学生姓名周平学号相同群组：无实验项目最小消费生成树Prim算法必修课示范实验验证实验操作实验综合实验实验场所W101实验仪表号码K03指导教师尹爱华实验日期和部分5-234一、实验摘要实现贪心方法的以下6种算法之一：1、可切割背包问题2、单源点最短路径求解算法Dijkstra算法3、Dijkstra算法的改进版本4、最小消费生成树Kruskal算法5、最小消费生成树Prim算法6、改进版本的最小消费生成树Prim算法要求和说明：1、各自独立完成，2、实验报告需要算法说明和说明、代码、数据集(每个算法1需要100，千个单位)。3、实验报告应包含2-3个屏幕快照，其中包括数据导入、重要的中间流程、最终结果等。4、每个完成额外添加一点的完成算法；5、程序要求以c语言完成，每个实验报告的代码都经过测试，如果对生产环境有特殊要求，则具体说明。否则，程序测试不会通过责任；6、实验报告有阶段，但程序测试结果与实验报告结果不一致，将加重减分。抄写7，代码重复90%以上的人被视为剽窃，剽窃以零分记录，可以质疑审查。怀疑。2、实验设备、设备或软件1，PC2、Microsoft Visual Studio 2015第二，实验过程(实验阶段、记录、数据、分析)实验代码为：#include#include#define MAX 100# define maxcost0x7fffffint graphMAXMAX；Int Prim(int graphMAX，int n)/* lowcosti记录以I结尾的边的最小权值，如果lowcosti=0，则将结束I添加到生成树*int lowcostMAX；/* msti记录对应于lowcosti的起点，msti=0表示将起点I添加到生成树*int MSTMAX；Int i、j、min、minid、sum=0；/*默认选择节点编号1订阅生成树，从节点编号2开始初始化*/for(I=2；I=n；I)/*最小距离初始化为从其他节点到节点1的距离*/low costI=graph1I；/*显示所有节点的起点为默认节点编号1 *MSTI=1；/*标签1节点生成树订阅*/MST1=0；/*在n个节点上配置最小生成树需要至少n-1条边*/for(I=2；I=n；I)Min=MAXCOSTminid=0；/*节点minid */for(j=2；j=n；j)/*边界权重较小，不在生成树中*/If (lowcostj min lowcostj)！=0)min=low costj；minid=j；/*生成树边的信息输出：起点、终点和权值*/printf(“% c-% c :% d n”，MST minid a-1，minid a-1，min)；/*加权*/Sum=min/*标记节点minid生成树订阅*/lowcostminid=0；/*将权重从当前节点minid更新到其他节点*/for(j=2；j=n；j)/*找到较小的权重*/If (graphminidj lowcostj)/*更新权重信息*/low costj=graphminidj；/*更新最小权值边的起点*/MSTj=minid；/*返回最小权重和*/Return sumInt main()Printf(输入点和面数：)；Int i、j、k、m、n；Int x、y、costChar chx，chyscanf(“% d % d”，m，n)；/*读取节点和边数*/getchar()；Printf(“输入有关边的信息：”)；/*所有节点之间的距离无限的初始化图*/for(I=1)；I=m；I)for(j=1)；j=m；j)graphIj=max cost；/*读取边信息*/for(k=0)；k n；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 )；return 0；代码说明：1，2 for循环从2开始。通常，默认情况下将第一个节点添加到生成树，因此以后无需再次查找。2，lowcosti记录以节点I为端点的最小边权值。默认情况下，第一个节点将添加到生成树中，因此lowcosti=graph1i，即最小边权重是从每个节点到节点1的边权重。3，msti记录与lowcosti相对应的起点，以便具有起点和终点来唯一确定边。初始化时msti=1。也就是说，每个边都从节点1开始。作者：使用以下权重图(使用Prim算法查找最小生成树)提供节点数和所有边界值。三、结论1、实验结果数据输入：7 11A B 7A D 5B C 8B D 9B E 7C E 5D E 15D F 6E F 8E G 9F G 11输出：A-D : 5D-F : 6A-B : 7B-E : 7E-C : 5E-G : 9Total:39实验结果如下：2、分析讨论Prim算法的基本思想如下：首先获取v中的任意顶点(假定v1)，然后将生成树t设置为仅具有一个节点v1的树。也就是说，U= v1 ；然后，如果u是v的真正子集，则寻找一个端点全部在t上，另一个端点从t外部的边最短(即权重最小)的边。假设满足条件的最短边是(vi，vj)，则该边和t上