Kruskal算法求最小生成树

1、精选优质文档-倾情为你奉上计算机科学与工程学院实验报告实验题目： Kruskal算法求最小生成树 课程名称： 离散数学 实验类型： 设计性 专业： 软件工程 班级： 学生姓名： 学号： 实验日期： 2011 年 12 月 8 日 实验地点： 实验学时： 实验成绩：指导教师： 年 月 日实验题目 Kruskal算法求最小生成树实验原理设所给定无向连通加权图具有n个结点，m条边，首先，将各条边的权按从小到大的顺序排序。然后依次将这些边按所给图的结构放到生成树中去。如果在放置某一条边时，使得生成树形成回路，则删除这条边。这样，直至生成树具有n-1条边时，我们所得到的就是一棵最小生成树。实验步骤（1）

2、 边依小到大顺序得l1，l2，lm。（2） 置初值：S，0i，1j。（3） 若i=n-1，则转（6）。（4） 若生成树边集S并入一条新的边lj之后产生的回路，则j+1j，并转（4）。（5） 否则，i+1i；ljS（i）；j+1j，转（3）。（6） 输出最小生成树S。（7） 结束。实验中遇到的问题及解决办法(1) 出现回路:在前几次测试时,总会出现回路,经过动态跟踪检查出是在合并两个连通分量时没有考虑该结点是否同时在两个连通分量中，导致合并后形成回路。解决办法是增加一个寻找顶点的双亲直到根结点，如果根结点相同表明会形成回路不添加该边。(2) 生成的并不是最小生成树：原因在于开始手动排序权值后输入

3、的边，一旦不按权值由小到大输入边，就不会产生最小生成树。解决办法，增加一个以权值为关键值的排序函数，将边排序，然后再调用最小生成树函数。问题得以解决。(3) 出现多边的情况，即在此形成回路：动态跟踪得知，忽略了最小生成树的一条重要特征：最后所剩边数应为 顶点数-1 增加一个if判断语句结束循环后问题解决。程序清单及运行结果 #include <iostream>using namespace std;const int MaxVertex = 20; /图中最大顶点数const int MaxEdge = 100; /图中最大边数int FindRoot(int parent,in

4、t v);struct EdgeType int from; /边的起点int to; /边的终点int weight; /权值;struct EdgeGraphchar vertexMaxVertex; /顶点的数据类型为 charEdgeType edgeMaxEdge; /存放边的数组int vertexNum; /图的顶点数int edgeNum; /图的边数int parentMaxVertex;void Sort(EdgeType ed,int E)/权值排序int i,j;EdgeType p;for(i=0; i<E; +i)/趟次for(j=0;j<E-i-1;

5、+j)/没趟比较次数if(edj.weight >= edj+1.weight)p = edj+1;edj+1 = edj;edj = p;/最小生成树代码实现主体部分void Kruskal(EdgeGraph G)int parentMaxVertex;int i;int num; int vex1;int vex2;for (i=0; i<G.vertexNum; i+)parenti = -1;for (num = 0,i = 0; i<G.edgeNum; i+) vex1 = FindRoot(parent,G.edgei.from); vex2 = FindRo

6、ot(parent,G.edgei.to); if (vex1 != vex2) cout << "(" <<G.vertex G.edgei.from <<" "<< G.vertexG.edgei.to << ")" << endl; /输出生成的边 parentvex2 = vex1 ; num+; if (num = G.vertexNum-1) return ; /求顶点的双亲一直到根int FindRoot(int parent,int v)while

7、 (parentv != -1) if (parentv > -1) v = parentv; return v;/主函数int main(int argc ,char *argv) EdgeGraph eg;char x,y; cout <<""<<endl;cout <<"请输入图的顶点数，和边数： "<<endl;cout <<" "cin >> eg.vertexNum >> eg.edgeNum; cout <<"

8、请输入各顶点的值： "<<endl;cout <<" "for (int j =0; j<eg.vertexNum; j+)cin >>eg.vertexj;cout <<"请分别输入"<<eg.edgeNum<<"条边各边的起点，终点，及其权值： "<<endl;for (int i=0;i<eg.edgeNum;i+)cout <<" "cin >>x>>y>>

9、;eg.edgei.weight;for(int m= 0;m<eg.vertexNum;m+)if(eg.vertexm=x)eg.edgei.from= m; if(eg.vertexm=y) eg.edgei.to= m; Sort(eg.edge,eg.edgeNum);cout <<"最小生成树为："<<endl;Kruskal(eg);return 0;程序运行示例： 实验总结此次的设计是自己对已学知识的一个总结和升华，我在此过程中不但应用了所学的知识，而且还结合数据结构等书籍，以完成设计的需要，在设计的过程中我深深体会到，为了实现一个模块的代码、为了一个设计的实现思想、经常绞尽脑汁来达到设计所要达到目的的艰辛，而且通过这次的实验，我也发现了自己还有很多地方有待