最小生成树的Kruskal算法实验报告

1、大连民族学院 计算机科学与工程学院实验报告 实验题目： 最小生成树的Kruskal算法 课程名称： 离散数学 实验类型： 演示性 验证性 操作性 设计性 综合性 专业：软件工程 班级：111学生姓名：XX 学号：XX 实验日期：2012年12月6-28日实验地点：金石滩校区机房 201 实验学时：10学时实验成绩： 指导教师： 焉德军 姜楠 2012年12月28日 实验原理 设所给定无向连通加权图具有n个结点，m条边，首先，将各条边的权按从小 到大的顺序排序。然后依次将这些边按所给图的结构放到生成树中去。如果在放 置某一条边时，使得生成树形成回路，则删除这条边。这样，直至生成树具有 n-1条边

2、时，我们所得到的就是一棵最小生成树。 实验内容 给定无向连通加权图，编程设计求出其一棵最小生成树。 实验目的 通过算法设计并编程实现求出给定无向连通加权图的一棵最小生成树， 加深学生对求最小生成树的Kruskal算法的理解。 实验步骤 (1) 边依小到大顺序得丨1,丨2,，Im。 (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) 输出最小生成树So (7) 结束。 具体程序

3、的C+实现如下: #include using namespacestd; con sti nt MaxVertex = 20; constint MaxEdge = 100; con sti nt MaxSize = 100; struct EdgeType int from; int to; int weight; ; struct EdgeGraph char vertexMaxVertex; EdgeType edgeMaxEdge; int vertexNum; int edgeNum; ; int FindRoot( int parent, int v); void InputIn

4、fo(); void Kruskal(EdgeGraph G) int vex1,vex2,f,t; int i,num; int parentMaxVertex; for (i=0; iG.vertexNum; i+) parenti = -1; for (num =0,i=0; iG.edgeNum; i+) vex1 = FindRoot(parent, G.edgei.from); vex2 = FindRoot(parent, G.edgei.to); if(vex1 != vex2) cout ( G.edgei.from , G.edgei.to ) endl; f = G.ed

5、gei.from; t = G.edgei.to; cout ( G.vertexf , G.vertext ) Weight: G.edgei.weight endl; cout -1) t = parentt; return t; void InputInfo() EdgeGraph G; cout Please input vertexNum , edgeNum: G.vertexNum G.edgeNum; cout Please input the information of edges: endl; for (int i=0; i G.vertexi; cout Please i

6、nput this edge attaches two vertices subscript and its weight endl; for (int j=0; j G.edgej.from G.edgej.to G.edgej.weight; Kruskal(G); int main() InputInfo(); system(pause); return 0; 实验过程中遇到的问题及解决过程 比如不知道如何存储边集数组， 以及比知道如何声明一些变量， 函数和怎样去 调用Kruskal函数 解决：通过设置结构体EdgeType与结构体EdgeGrapI的联合来存储边集，因为在 刚开始我在主

7、函数中用EdgeGraph声明变量G来作为形参去调用Kruskal(G)，编 译时就会警告未被初始化的G,的程序出错，后来我将Kruskal(G)在Inputlnfo() 中调用，因为In put Info()函数中声明了变量G,并使得G初始化，从而是的程序 能正常运行。 测试的图与预期生成的最小树 实验记录 D:Drafthao.De bu gProjectl 3 ,exe Please input b8 Please input A B C D E F Please input 1 4 & 3 & 12 17 19 25 26 34 38 46 uertexNun , edgeNum: the infDPnation of edges: this edge attaches two uertices subscript and its weight Ue ight: 12 Meight: 17 Ueight: 19 Meight: 25 Ueight: 26 实验总结，感想 通过这次的上机实验， 加深了我对课本上的理论知识的认识与理解，然我真实的体验到 了从研究问题到解决问题的探索