最小生成树实验总结.docxVIP

最小生成树实验总结 　　一、实验目的　　1．使学生熟悉最小生成树的意义和相应算法2．掌握带权图的存储结构二、实验环境　　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算法建立最小生成树。　　③编写一个能对邻接矩阵中的边进行自小到大的存储在数组中的算法；　　代码　　(MGraph类的声明)　　#if!defined(AFX_MGRAPH_H__FDC762FA_D8BE_473C_B917_CAE3F__INCLUDED_)#defineAFX_MGRAPH_H__FDC762FA_D8BE_473C_B917_CAE3F__INCLUDED_　　#if_MSC_VER1000#pragmaonce　　#endif//_MSC_VER1000　　constintMax=20;//图中最多顶点的个数constintMaxSide=100;//图中最多的边数constintinfinite=9999;//infinite假设为无限大　　structelement//辅助结构体element{intlowcost;//候选最短边的邻接点intadjvex;//候选最短边的权值};　　structEdgeType//辅助结构体EdgeType{intfrom,to;//边依附的两个顶点intweight;//边上的权值};　　templateclassMGraph{