Kruskal算法求最小生成树

计算机科学与工程学院实验报告实验题目：Kruskal算法求最小生成树课程名称：离散数学实验类型：设计性专业：软件工程班级：学生姓名：学号：实验日期：2011年12月8日实验地点：实验学时：实验成绩：指导教师：年月日[实验题目]Kruskal算法求最小生成树[实验原理]设所给定无向连通加权图具有n个结点，m条边，首先，将各条边的权按从小到大的顺序排序。然后依次将这些边按所给图的结构放到生成树中去。如果在放置某一条边时，使得生成树形成回路，则删除这条边。这样，直至生成树具有n-1条边时，我们所得到的就是一棵最小生成树。[实验步骤]（1）边依小到大顺序得l1，l2，…，lm。（2）置初值：S，0i，1j。（3）若i=n-1，则转（6）。（4）若生成树边集S并入一条新的边lj之后产生的回路，则j+1j，并转（4）。（5）否则，i+1i；ljS（i）；j+1j，转（3）。（6）输出最小生成树S。（7）结束。[实验中遇到的问题及解决办法](1)出现回路:在前几次测试时,总会出现回路,经过动态跟踪检查出是在合并两个连通分量时没有考虑该结点是否同时在两个连通分量中，导致合并后形成回路。解决办法是增加一个寻找顶点的双亲直到根结点，如果根结点相同表明会形成回路不添加该边。(2)生成的并不是最小生成树：原因在于开始手动排序权值后输入的边，一旦不按权值由小到大输入边，就不会产生最小生成树。解决办法，增加一个以权值为关键值的排序函数，将边排序，然后再调用最小生成树函数。问题得以解决。(3)出现多边的情况，即在此形成回路：动态跟踪得知，忽略了最小生成树的一条重要特征：最后所剩边数应为顶点数-1增加一个if判断语句结束循环后问题解决。[程序清单及运行结果]#includeiostreamusingnamespacestd;constintMaxVertex=20;//图中最大顶点数constintMaxEdge=100;//图中最大边数intFindRoot(intparent[],intv);structEdgeType{intfrom;//边的起点intto;//边的终点intweight;//权值};structEdgeGraph{charvertex[MaxVertex];//顶点的数据类型为‘char’EdgeTypeedge[MaxEdge];//存放边的数组intvertexNum;//图的顶点数intedgeNum;//图的边数intparent[MaxVertex];};voidSort(EdgeTypeed[],intE)//权值排序{inti,j;EdgeTypep;for(i=0;iE;++i)//趟次for(j=0;jE-i-1;++j)//没趟比较次数if(ed[j].weight=ed[j+1].weight){p=ed[j+1];ed[j+1]=ed[j];ed[j]=p;}}//最小生成树代码实现主体部分voidKruskal(EdgeGraphG){intparent[MaxVertex];inti;intnum;intvex1;intvex2;for(i=0;iG.vertexNum;i++){parent[i]=-1;}for(num=0,i=0;iG.edgeNum;i++){vex1=FindRoot(parent,G.edge[i].from);vex2=FindRoot(parent,G.edge[i].to);if(vex1!=vex2){cout(G.vertex[G.edge[i].from]G.vertex[G.edge[i].to])endl;//输出生成的边parent[vex2]=vex1;num++;if(num==G.vertexNum-1){return;}}}}//求顶点的双亲一直到根intFindRoot(intparent[],intv){while(parent[v]!=-1){if(parent[v]-1){v=parent[v];}}returnv;}//主函数intmain(intargc,char*argv[]){EdgeGrapheg;charx,y;cout﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊endl;cout﹡﹡请输入图的顶点数，和边数：endl;cout→;cineg.vertexNumeg.edgeNum;cout请输入各顶点的值：endl;cout→;for(intj=0;jeg.vertexNum;j++){cineg.vertex[j];}cout请分别输入eg.edgeNum条边各边的起点，终点，及其权值：endl;for(inti=0;ieg.edgeNum;i++){cout→;cinxyeg.edge[i].weight;for(intm=0;meg.vertexNum;m++){if(eg.vertex[m]==x){eg.edge[i].from=m;}if(eg.vertex[m]==y){eg.edge[i].to=m;}}}Sort(eg.edge,eg.edgeNum);cout最小生成树为：endl;Kruskal(eg);return0;}程序运行示例：[实验总结]此次的设计是自己对已学知识的一个总结和升华，我在此过程中不但应用了所学的知识，而且还结合数据结构等书籍，以完成设计的需要，在设计的过程中我深深体会到，为了实现一个模块的代码、为了一个设计的实现思想、经常绞尽脑汁来达到设计所要达到目的的艰辛，而且通过这次的实验，我也发现了自己还有很多地方有待提高，平时基本知识掌握不牢，导致设计实验过程中走了很多弯路，再有还是不够细心，在此次实验过程中，我曾为了一个误写的变量，调试了三个小时。这不得不说是一个小小的教训。由于我的能力所限，所以设计过程中难免有缺点和不足的地方，代码健壮性较差，还有很大的提升空间，我一定会再次改进。