图的最小生成树的实现(Kruskal算法)

1、数据结构课程设计设计说明书图的最小生成树的实现（Kruskal算法）学生姓名学号班级成绩指导教师计算机科学与技术系2011年3月4日数据结构课程设计评阅书题目图的最小生成树的实现（Kruskal算法）学生姓名学号指导教师评语及成绩成绩：教师签名：年月曰答辩教师评语及成绩成绩：教师签名：年月曰教研室意见总成绩：室主任签名：年月曰注：指导教师成绩60%，答辩成绩40%，总成绩合成后按五级制记入。摘要设计了一种图的最小生成树的实现程序。本程序的算法按照克鲁斯卡尔算法的思想，采用图的邻接矩阵法存储图的顶点和边。纳入权值最小的边作为最小生成树的一部分，如遇回路则舍弃准备纳入的边，直到图的所有顶点被遍历。

2、该程序采用VC+作为软件开发环境，简单易行又节省时间。关键词：图;最小生成树；克鲁斯卡目录TOC o 1-5 h z HYPERLINK l bookmark2 课题描述1 HYPERLINK l bookmark4 问题分析和任务定义2 HYPERLINK l bookmark6 逻辑设计3 HYPERLINK l bookmark8 流程图4 HYPERLINK l bookmark10 程序编码7 HYPERLINK l bookmark12 程序调试结果11 HYPERLINK l bookmark14 结果分析13 HYPERLINK l bookmark16 总结14参考文献15

3、课题描述本次课程设计题目是：图的最小生成树的实现（Kruskal算法）。要求按照克鲁斯卡尔的算法思想编写一个新的程序，实现图的最小生成树的生成。Kruskal算法就是把所有的边按权值从小到大排序，然后依次把各个点加入到最小树的集合中去，但是在加入的过程中不能有回路。自主完成程序的编译与调试，画出流程图，并对此次课程设计过程中出现的问题和自己掌握的东西做一个详细的分析总结。问题分析和任务定义本课题涉及图的创建，存储及最小生成树问题。所谓最小生成树，就是给定一个无向图，挑选若干条边，连成一个树行图（无圈），使得所选边的权至和最小。该程序的算法是生成图的最小生成数，而且算法必须遵循克鲁斯卡尔思想，即

4、纳入图中权值最小的边作为最小生成树的一部分，继续纳入权值次小的边，直到图中所有顶点被遍历，如纳入边的过程中构成回路则舍弃该边，否则纳入。逻辑设计该程序主要由六大块组成，包括构造最小生成树数组、排序、交换权值、构造最小生成树、查找、还有主函数。如下图3.1所示：图的最小生成树的实现（Kruskal算法）构造最小生成树数组交换权值构造最小生成树图3.1程序模块图1 4流程图该程序的流程图如图4.1所示：i=1T.ivexnumjvexnumJ+l+i=1iarcnumYI+-Y-J=1SidebySideNiprintf（”邻接矩阵为:n）;inti,j,n,m;beginG-Aarqijtl.a

5、djhGarcji.adj=O:SidebySide图4.1流程图 1)图4.2流程图Yf=parentf;returnf; 5程序编码#include#include#defineM20#defineMAX20typedefstructintbegin;intend;intweight;edge;typedefstructintadj;intweight;AdjMatrixMAXMAX;typedefstructAdjMatrixarc;intvexnum,arcnum;MGraph;voidCreatGraph(MGraph*);/函数申明voidsort(edge*,MGraph*);v

6、oidMiniSpanTree(MGraph*);intFind(int*,int);voidSwapn(edge*,int,int);voidCreatGraph(MGraph*G)/构件图inti,j,n,m;printf(请输入边数和顶点数:)；scanf(%d%d,&G-arcnum,&G-vexnum);for(i=1;ivexnum;i+)/初始化图for(j=1;jvexnum;j+)G-arcij.adj=G-arcji.adj=0;for(i=1;i=G-arcnum;i+)/输入边和权值printf(n请输入有边的2个顶点)；scanf(%d%d,&n,&m);while(

7、n0|nG-vexnum|marcnm.adj=G-arcmn.adj=1;getchar();printf(n请输入%d与宀之间的权值：，n,m);scanf(%d,&G-arcnm.weight);printf(邻接矩阵为：n);for(i=1;ivexnum;i+)for(j=1;jvexnum;j+)printf(%d,G-arcij.adj);printf(n);voidsort(edgeedges,MGraph*G)/对权值进行排序inti,j;for(i=1;iarcnum;i+)for(j=i+1;jarcnum;j+)if(edgesi.weightedgesj.weight

8、)Swapn(edges,i,j);printf(权排序之后的为：n);for(i=1;iarcnum;i+)edgesi.end,printf(%dn,edgesi.begin,edgesi.weight);voidSwapn(edge*edges,inti,intj)/交换权值以及头和尾inttemp;temp=edgesi.begin;edgesi.begin=edgesj.begin;edgesj.begin=temp;temp=edgesi.end;edgesi.end=edgesj.end;edgesj.end=temp;temp=edgesi.weight;edgesi.weig

9、ht=edgesj.weight;edgesj.weight=temp;voidMiniSpanTree(MGraph*G)/生成最小生成树inti,j,n,m;intk=1;intparentM;edgeedgesM;for(i=1;ivexnum;i+)for(j=i+1;jvexnum;j+)if(G-arcij.adj=1)edgesk.begin=i;edgesk.end=j;edgesk.weight=G-arcij.weight;k+;sort(edges,G);for(i=1;iarcnum;i+)parenti=0;printf(最小生成树为：n);for(i=1;i=G-a

10、rcnum;i+)/核心部分n=Find(parent,edgesi.begin);m=Find(parent,edgesi.end);if(n!=m)parentn=m;edgesi.end,printf(0)f=parentf;returnf;intmain(void)/主函数MGraph*G;G=(MGraph*)malloc(sizeof(MGraph);if(G=NULL)printf(memoryallcationfailed,goodbye);exit(1);CreatGraph(G);MiniSpanTree(G);system(pause);return0; 6程序调试结果程

11、序调试结果如图6.1，图6.2所示：图6.1结果运行图图6.2结果运行图7结果分析程序运行过程中出现的问题主要有：调试过程中必须以正确的格式输入图的顶点，以及边的相关信息。必须要把与一个顶点相关的所有边输入结束再换下一个顶点，不能按任意方式输入。否则将造成程序调试出错，无法达到预期的目的。该程序是以邻接矩阵的方法创建和存储图的信息，必须要熟悉并掌握邻接矩阵的相关知识，才能有效减少编程过程中出现不必要的麻烦和错误。克鲁斯卡尔算法的时间复杂度为O(eloge).8总结Kruskal算法就是把所有的边按权值从小到大排序，然后依次把各个点加入到最小树的集合中去，但是在加入的过程中要判断是否有回路。唯一困难的问题就是这个，怎么判断有没有回路？用一个简单的标记方法。开辟一个新数组，大小和图中点的个数一样多，并初始化为点的对应标号。这个数组是记录该点已经在哪颗树当中。开始的时候自然是自己独立的一颗树，在每次加入一条边的时候，判断这条边的2个点在数组中记录的树时候是一样的，如果一样，那就说明是在同一颗树中，如果加入了会有回路，所以这条边不能加入。而如果不同，那就把这2个点中其中一个点的权值变成另一个点的权值，表示在同一颗树中，这样，便解决了该问题。经过两个