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

《最小生成树的Kruskal算法实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、stream>usingnamespacestd;constintMaxVertex=20;constintMaxEdge=100;constintMaxSize=100;structEdgeType{intfrom;intto;intweight;};structEdgeGraph{charvertex[MaxVertex];EdgeTypeedge[MaxEdge];intvertexNum;intedgeNum;};intFindRoot(intparent[],intv);voidInputInfo();voidKruskal(EdgeGraph

4、G){intvex1,vex2,f,t;inti,num;intparent[MaxVertex];for(i=0;i

5、m;t=G.edge[i].to;cout<<"("<-1){t=parent[t];}returnt;}voidInputInfo(){EdgeGraphG;cou

6、t<<"PleaseinputvertexNum,edgeNum:"<>G.vertexNum>>G.edgeNum;cout<<"Pleaseinputtheinformationofedges:"<>G.vertex[i];}cout<<"Pleaseinputthisedgeattachestwoverticessubscriptanditsweight"<>G.edge[j

7、].from>>G.edge[j].to>>G.edge[j].weight;}Kruskal(G);}intmain(){InputInfo();system("pause");return0;}实验过程中遇到的问题及解决过程比如不知道如何存储边集数组，以及比知道如何声明一些变量，函数和怎样去调用Kruskal函数……解决：通过设置结构体EdgeType与结构体EdgeGraph的联合来存储边集，因为在刚开始我在主函数中用EdgeGraph声明变量G，来作为形参去调用Kruskal(G)，编译时就会警告未被初始化的G，的程序出错，后来我将Kruskal

8、(G)在InputInfo()中调用，因为InputInfo()函数中声明了变量