Kruskal算法求最小生成树doc

1、荆楚理工学院课程设计成果 学院:_计算机工程学院_ 班 级: 14计算机科学与技术一班 学生姓名: 陈志杰 学 号: 设计地点（单位）_B5101_ _设计题目:克鲁斯卡尔算法求最小生成树_ 完成日期： 2015年 1月 6日 指导教师评语: _ _ _ _ 成绩(五级记分制):_ _ _ 教师签名:_ _数据结构课程设计评分表班级 计科一班姓名陈志杰 指导教师李素若 题目：克鲁斯卡尔算法求最小生成树评分标准评分标准分数权重评分的依据得分AC选题10选题符合大纲要求，题目较新颖，工作量大选题基本符合大纲要求，工作量适中 工作态度10态度端正，能主动认真完

2、成各个环节的工作，不迟到早退，出勤好。能够完成各环节基本工作，出勤较好。 系统设计20能正确描述总体系统框架图，主要函数有正确的流程图。能基本正确描述总体系统框架图，主要函数基本能给出流程图。 独立解决问题的能力10具有独立分析、解决问题能力，有一定的创造性，能够独立完成数据库及相关软件的设计与调试工作，程序结构合理，逻辑严谨，功能完善。有一定的分析、解决问题能力。能够在老师指导下完成软件的设计与调试工作，程序功能较完善。 答辨问题回答20能准确回答老师提出的问题能基本准确回答老师提出的问题 程序运行情况10程序运行正确、界面清晰，测试数据设计合理。程序

3、运行正确、界面较清晰，能给出合适的测试数据。 课程设计论文20格式规范，层次清晰，设计思想明确，解决问题方法合理，体会深刻。格式较规范，设计思想基本明确，解决问题方法较合理。 总分 指导教师（签字）：注：介于A和C之间为B级，低于C为D级和E级。按各项指标打分后，总分在90100为优，8089为良，7079为中，6069为及格，60分以下为不及格。目 录1 需求分析11.1系统目标11.2主体功能11.3开发环境12 概要设计12.1功能模块划分12.2 系统流程图23 详细设计33.1 数据结构33.2 模块设计34测试34.1 测试数据34.2测试分析45总结

4、与体会65.1总结：65.2体会：6参考文献7附录 全部代码81 需求分析 1.1系统目标Kruskal算法是一种按照网中边的权值递增的顺序构造最小生成树的方法。其基本思想是：首先选取全部的n个顶点，将其看成n个连通分量；然后按照网中边的权值由小到大的顺序，不断的选取当前未被选取的边集中权值最小的边。依照生成树的概念，n个结点的生成树有n-1条边，故反复上述过程，直到选取了n-1条边为止，就构成了一棵最小生成树。1.2主体功能在城市规划设计中，假设有n个城市之间建立通信网，则连通n个城市只需n-1条线路。这里自然考虑怎样建立这n-1条路是总费用最省。把这n个城市抽象成一个连通网，网的顶点表示各

5、个城市，顶点与顶点之间的边表示通信线路，各个城市之间的通讯线路看作边，相应的建设花费作为边的权，这样就构成了一个网络。由于在n个城市之间，可行线路有(n*(n-1)/2条，那么，如果选择其中的n-1条线路(边)在n个城市间建成全都能相互通讯的网，并且总的建设花费为最小？这就是求该网络的最小生成树问题。本程序的目的是要建立一棵生成树使总费用最少。 1.3开发环境装有Windows 7操作系统的PC机vc+6.0，奔腾4 1.0GHz以上的处理器，编写的程序需要在32MB的内存中运行。推荐在以下基本配置电脑中运行：CPU Intel MMX 233MHz 内存：64MB 硬盘空间：1.5

6、GB 显卡：4MB显存以上的PCI、AGP显卡声卡：最新的PCI声卡 CD-ROM：8x以上CD-ROM2 概要设计2.1功能模块划分运行程序后，程序在内存中申请图g的邻接矩阵表示空间，存放作为用整型数组表示的顶点、边、权值的数据。程序运行过程中调用存放在存放在ESP寄存器中的数据，寄存器中存放着数据、地址和函数传递的中间结果。Kruskal算法在调用寄存器中的整型数据，对边上的权值进行冒泡排序，将权值小的边放在数组的上面，然后在进行一次循环打印，循环过程中调用vset辅助数组的数据进行比较，两个数据不相等就将该边打印出来，不断进行这个过程直至打印出n-1条边（即顶点数减一的次数）。具体的功能

7、流程图如下图2.1功能流程图所示。图2.1 功能流程图2.2 系统流程图输入网图的信息后，将网图的边、顶点、边上的权值记录在一个邻接矩阵中，在后面的kruskal算法中直接扫描邻接矩阵，将边的信息存放在算法定义的边集数组中。图2.2 系统流程图3详细设计3.1 数据结构在Kruskal算法中的数据存放和调用采用整型变量，设置邻接矩阵的最大顶点数，设置图的顶点信息为字符，设置边上权值为整型，定义邻接矩阵图的顶点信息表还有图的顶点数和边数。Kruskal算法中有一个辅助数组，这里的存放的顶点信息的一维数组vexs的类型是用VertexType类型来表示的，这里把它定义成字符，在实际应用中可以根据需

8、要把它重新定义为其他系统预定义类型或结构类型。此外，邻接矩阵edges的类型用EdgeType类型表示，这里把它定义为整型。在实际应用中，若权值的类型是其他数据类型，则只需简单修改即可。3.2 模块设计1. CreateMGraph创建一个邻接矩阵存储的图。在提示下输入无向图的顶点数和边数，然后再输入各个顶点的信息，也就是顶点的编号，再输入顶点数组编号的下标表示的边和边上的权值，这中间非网图的边的权值为1。2.Kruskal算法在扫描到邻接矩阵存放的信息后，用冒泡排序将边上的权值从小到大排列。定义一个辅助数组，该数组是用来判断生成树中是否会出现回路，也就是生成正确的最小生成树。判断边的连通分量

9、编号不相等，将这条边打印出来，并将连通分量编号修改。循环顶点数减一次，将最小生成树打印出来。4 测试4.1 测试数据主要的测试过程有两个：1. 对邻接矩阵的输入和存放。克鲁斯卡尔算法运行，得出最小生成树。2. 克鲁斯卡尔算法对存放的邻接矩阵的调用。输入图的信息后算法得到正确结果。调试阶段最重要的还是耐性和细心。要有足够的耐性去对待令人烦躁的错误，一步步细心的调试，就会查出错误的所在。我们进行调试、测试是为了让我们的代码、程序更加健壮，质量更高。所以，我们不要畏惧报错，这是个学习进步的过程。3.调试过程中的输入数据。第一组测试数据见表4-1。表4-1 调试数据权值5060406552455030

10、4270顶点i1243364565顶点j0011223334第二组测试数据：表4-2 调试数据权值111111顶点i123434顶点j000012 第三组数据：表4-3 调试数据权值164253顶点i123233顶点j000112 4.2测试分析1.第一组数据测试结果运行程序后输入图的信息。按照提示的格式输入，输入成功如下图4.1所示。 图4.1 输入图的信息后的界面输完信息后，程序运行得到最小生成树的结果。图4.2 求得的最小生成树2.第二组数据测试结果运行程序后输入图的信息。按照提示的格式输入，输入成功如下图4.3所示。 图4.3 输入图的信息后的界面输完信息后，程序运行得到最小生成树的结

11、果。图4.4 求得的最小生成树3.第三组数据测试结果运行程序后输入图的信息。按照提示的格式输入，输入成功如下图4.5所示。图4.5 输入图的信息后的界面输完信息后，程序运行得到最小生成树的结果。图4.6求得的最小生成树5 总结与体会5.1总结：克鲁斯卡尔算法中的核心思想就是逐个在边的集合中找到最小的边，如果满足条件就将其构造，最后生成一个最小生成树。它首先是一系列的顶点集合，并没有边，然后我们从邻接矩阵中寻找最小的边，看看它是否和现有的边连接成一个环，如果连接成环，则舍弃，另外取其它的边。如果不连接成环，则接受这个边，并把其纳入集合中。5.2体会：在编程序过程中虽然遇到了很多问题，但也使我学到

12、了很多东西，在编制程序过程中我学到了在编程的开始需要总体设计一下自己的程序需要哪些大的模块，并想好所要用到的知识及算法，在编程过程中，特别是要画图时需要找出坐标，并研究各坐标各结点之间连线的规律，通过几句判断语句来实现多条连线问题，在编程过好还要反复调试程序，找出其中的漏洞并加以改正，在此次编程过程中就存在这样的问题，在经过反复修改后，终于可将漏洞扫除，正确的输出结果。参考文献1李素若，陈万华，游明坤. 数据结构. 北京：中国水利水电出版社，2014. 2 严蔚敏，吴伟民.数据结构（C语言版）. 北京：清华大学出版社，2014.3李素若，任正云，赖玲.C语言程序设计.  北

13、京:：中国水利水电出版社， 2014.4邓文华.数据结构（C语言版）. 北京：清华大学出版社，2011.附录 全部代码#include<stdio.h>#include<stdlib.h>#define MaxVerNum 100 /设置邻接矩阵的最大顶点数typedef char VertexType; /设置图的顶点信息为整型typedef int EdgeType; /设置边上权值为整型typedef structVertexType vexsMaxVerNum; /图的顶点信息表EdgeType edgeMaxVerNumMaxVerNum;/图的邻接

14、矩阵int n,e; /图的顶点数和边数MGraph; /图的邻接矩阵表示结构定义void CreateMGraph(MGraph *g)/建立图g的邻接矩阵表示int i,j,k,w;printf("输入顶点数和边数(格式为:顶点数,边数)n"); scanf("%d,%d",&g->n,&g->e); printf("输入顶点的信息:n"); for(i=0;i<g->n;i+) getchar();scanf("%c",&(g->vexsi); for(i

15、=0;i<g->n;i+) /将邻接矩阵数组初始化 for(j=0;j<g->n;j+) g->edgeij=0;/图的遍历算法初始化该值为0 for(k=0;k<g->e;k+) printf("输入边的两个顶点号的下标，权值w(非网图权值为1)(格式为*,*,*):n"); scanf("%d,%d,%d",&i,&j,&w); g->edgeij=w; g->edgeji=w; void kruskal(MGraph *g) int i,j,k,s1,s2,num,ves

16、tMaxVerNum;/vset辅助数组 int v1,v2; struct edgeType/定义边信息结构 int u,v;/每条边两个顶点的数组下标号 int w;/权值 t,*edge; edge=(struct edgeType *)malloc(g->e*sizeof(struct edgeType); k=0; for(i=0;i<g->n;i+)/扫描邻接矩阵，将边信息存储到边集数组 for(j=0;j<g->n;j+) if(g->edgeij&&i<j) edgek.u=i;edgek.v=j; edgek.w=g-

17、>edgeij; k+; for(j=1;j<k;j+)/对边集权值采用冒泡排序 for(i=0;i<k-j;i+) if(edgei.w>edgei+1.w) t=edgei; edgei=edgei+1; edgei+1=t; for(i=0;i<g->e;i+)vesti=i;/初始化G中各顶点的vset值 num=1;/构造生成树的第几条边，从1开始 j=0;/从边集数组下标0开始处理 while(num<g->n)/循环n-1次，构造n-1条边 v1=edgej.u;v2=edgej.v;/取边的两个顶点号 s1=vestv1;s2=vestv2;/分别求两个顶点的连通分量的编号 if(s1!=s2) printf("(%c,