《最小生成树的Kruskal算法实验报告》由会员分享，可在线阅读，更多相关《最小生成树的Kruskal算法实验报告（6页珍藏版）》请在装配图网上搜索。
1、大连民族学院计算机科学与工程学院实验报告实验题目：最小生成树的Kruskal算法课程名称：离散数学实验类型：演示性 验证性 操作性 设计性 综合性专业：软件工程 班级：111学生姓名：XX 学号：xx实验日期：2012 年12 月6-28 日 实验地点：金石滩校区机房201实验学时：10 学时实验成绩：指导教师： 焉德军 姜楠 2012 年 12月28 日实验原理设所给定无向连通加权图具有n个结点，m条边，首先，将各条边的权按从小 到大的顺序排序。然后依次将这些边按所给图的结构放到生成树中去。如果在放 置某一条边时，使得生成树形成回路，则删除这条边。这样，直至生成树具有 n-1 条边时，我们所
2、得到的就是一棵最小生成树。实验内容给定无向连通加权图，编程设计求出其一棵最小生成树。实验目的通过算法设计并编程实现求出给定无向连通加权图的一棵最小生成树， 加深学生对求最小生成树的 Kruskal 算法的理解。实验步骤(1) 边依小到大顺序得l ,l。12m(2) 置初值：0nS, 0ni, 1 nj。(3) 若 i=n-1,则转(6)。(4) 若生成树边集S并入一条新的边l之后产生的回路，则j+1 n j,并转(4)。j(5) 否则，i+1 ni； l nS (i)； j+1 nj,转(3)。j(6) 输出最小生成树 S。(7) 结束。具体程序的C+实现如下:#include using n
3、amespace std;const int MaxVertex = 20;const int MaxEdge = 100;const int MaxSize = 100;struct EdgeTypeint from;int to;int weight;struct EdgeGraphchar vertexMaxVertex;EdgeType edgeMaxEdge;int vertexNum;int edgeNum;int FindRoot(int parent, int v);void InputInfo();void Kruskal(EdgeGraph G)int vex1,vex2,
4、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.edgei.from;t = G.edgei.to;cout ( G.vertexf , G.vertext ) Wei
5、ght: 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 input this edge attaches two vertices subscript and its weight endl;for
6、(int j=0; j G.edgej.from G.edgej.to G.edgej.weight;Kruskal(G);int main()InputInfo();system(pause);return 0;实验过程中遇到的问题及解决过程比如不知道如何存储边集数组，以及比知道如何声明一些变量，函数和怎样去 调用Kruskal函数解决：通过设置结构体EdgeType与结构体EdgeGraph的联合来存储边集，因为在 刚开始我在主函数中用EdgeGraph声明变量G,来作为形参去调用Kruskal(G),编 译时就会警告未被初始化的G,的程序出错，后来我将Kruskal(G)在Inputln
7、fo() 中调用，因为Inputlnfo()函数中声明了变量G，并使得G初始化，从而是的程序 能正常运行。测试的图与预期生成的最小树实验记录r IDDrafthaoWDe bu gPrcjectl 3. smsFlease input uertexNum , edgeNum:E 8Flease input the information of edges：p F C B F F卩 1口耳敦戸 i nput this Riigp AttArhftR tun urfIz i rrr Riihsnpi pt snri its ur i ght rt 4 120 1 17” 19E 25卩E 2GB 1 34 4 382 46 Ue ight: 2S3)ku,B； Height： 170,5?A,F) Ueight: 192,5 ) Height： 25F.F： Ur 1ght: 2AI-k按任意避猪垓 实验总结，感想 通过这次的上机实验，加深了我对课本上的理论知识的认识与理解，然我真实的体验到 了从研究问题到解决问题的探索中产生的乐趣，并且体会到问题解决的成就感，虽然在上机 调试的时候产生了很多的错误，但经过自己查阅资料，请教同学老师而将问题一一的解决让 我体会到学习所带来的乐趣，我希望今后能又更多的理论与实践相结合的课程设计作业，而 不是单一的理论的学习。
最小生成树的Kruskal算法实验报告
