最小生成树实验总结.docx

最小生成树实验总结一、实验目的 、实验环境 1、硬件:每个学生需配备计算机一台2、软件:windows操作系统+TurboC三、实验要求 1、能够独立完成带权图的存储和最小生成树的生成四、代码#include#include#defineMAX100#defineMAXCOST0x7fffffffintgraph_hcy[MAX][MAX];intPrim_hcy(intgraph_hcy[][MAX],intn){/*lowcost_hcy[i]记录以i为终点的边的最小权值,当lowcost[i]=0时表示终点i加入生成树*/intlowcost_hcy[MAX];/*mst_hcy[i]记录对应lowcost[i]的起点,当mst[i]=0时表示起点i加入生成树*/intmst_hcy[MAX];inti,j,min,minid,sum=0;/*默认选择1号节点加入生成树,从2号节点开始初始化*/for(i=2;istructEdge{ intfrom,to,weight;//定义一个数据结构,存放点和边的关系以及边的权值}; Edgeedge[100],temp;和一个变量 inti,j,n,m;intp[100]; intseek(intx){ if(p[x]==x) returnx; elsereturnp[x]=seek(p[x]); } IntKruskal(){ intx,y,k=0;for(i=0;iight); //输出这时的边的端点和权值}k++; p[x]=y; }}intmain(){ printf("Pleaseinputthenumberofthenodesandedges:\n");scanf("%d%d",&n,&m);//输入有n个节点m条边printf("Pleaseinputtheedgesanditsweight:\n");for(i=0;iedge[j].weight){} temp=edge[i]; edge[i]=edge[j];edge[j]=temp; printf("Theminimumspanningtreeis:\n"); Kruskal();//调用Kruskal算法return0;} 其中运用seek函数找出当前端点所在集合编号。运用Kruskal函数来实现求出最小生成树的边,并且依次输出。在主函数中将各个边按照权值的大小由小到大排序。六、输入和输出及结果的分析程序要求先输入结点个数以及边的个数,然后再依次输入各边的起点终点以及权值。输出时则是输出最小生成树的边的起点终点和权值。测试用例一:老师的用例。我们应该输入:8,13然后输入123,232,383,872,762,612,141,252,534,273,472,571 其输入如图: 其输出如图: 测试用例二:输入58;然后输入121,232,342,453,512,143,521,242,如图所示: xie 数据结构与算法实验院别:年级专业:姓名:学号: 计算机科学与信息工程学院XX级空间信息与数字技术杨哲庆14XX2138 XX年12月实验8最小生成树实验最小生成树实验的主要内容和目的①使用Prim算法建立最小生成树。②使用Kruskal算法建立最小生成树。③编写一