荆楚理工学院课程设计成果学院:_______计算机工程学院__________ 班级: 14计算机科学与技术一班学生姓名: 志杰学号: 2014407020137设计地点（单位）_____B5101_________ ____________设计题目:克鲁斯卡尔算法求最小生成树__________________________________完成日期：2015年1月6日指导教师评语: ______________ ____________________________________________________________________________________________________________ ___________________________________________________________________________________________ ___________________________ __________ _成绩(五级记分制):_____ _ __________教师签名:__________ _______________注：介于A和C之间为B级，低于C为D级和E级。

按各项指标打分后，总分在90～100为优，80～89为良，70～79为中，60～69为及格，60分以下为不及格。

目录1 需求分析 (1)1.1系统目标 (1)1.2主体功能 (1)1.3开发环境 (1)2 概要设计 (1)2.1功能模块划分 (1)2.2 系统流程图 (2)3 详细设计 (3)3.1 数据结构 (3)3.2 模块设计 (3)4测试 (3)4.1 测试数据 (3)4.2测试分析 (4)5总结与体会 (6)5.1总结： (6)5.2体会： (6)参考文献 (7)附录全部代码 (8)1 需求分析1.1系统目标Kruskal算法是一种按照网中边的权值递增的顺序构造最小生成树的方法。

其基本思想是：首先选取全部的n个顶点，将其看成n个连通分量；然后按照网中边的权值由小到大的顺序，不断的选取当前未被选取的边集中权值最小的边。

依照生成树的概念，n 个结点的生成树有n-1条边，故反复上述过程，直到选取了n-1条边为止，就构成了一棵最小生成树。

1.2主体功能在城市规划设计中，假设有n个城市之间建立通信网，则连通n个城市只需n-1条线路。

这里自然考虑怎样建立这n-1条路是总费用最省。

把这n个城市抽象成一个连通网，网的顶点表示各个城市，顶点与顶点之间的边表示通信线路，各个城市之间的通讯线路看作边，相应的建设花费作为边的权，这样就构成了一个网络。

由于在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.5GB显卡：4MB显存以上的PCI、AGP显卡声卡：最新的PCI声卡CD-ROM：8x以上CD-ROM2 概要设计2.1功能模块划分运行程序后，程序在存中申请图g的邻接矩阵表示空间，存放作为用整型数组表示的顶点、边、权值的数据。

程序运行过程中调用存放在存放在ESP寄存器中的数据，寄存器中存放着数据、地址和函数传递的中间结果。

Kruskal算法在调用寄存器中的整型数据，对边上的权值进行冒泡排序，将权值小的边放在数组的上面，然后在进行一次循环打印，循环过程中调用vset辅助数组的数据进行比较，两个数据不相等就将该边打印出来，不断进行这个过程直至打印出n-1条边（即顶点数减一的次数）。

具体的功能流程图如下图2.1功能流程图所示。

图2.1 功能流程图2.2 系统流程图输入网图的信息后，将网图的边、顶点、边上的权值记录在一个邻接矩阵中，在后面的kruskal算法中直接扫描邻接矩阵，将边的信息存放在算法定义的边集数组中。

图2.2 系统流程图3详细设计3.1 数据结构在Kruskal算法中的数据存放和调用采用整型变量，设置邻接矩阵的最大顶点数，设置图的顶点信息为字符，设置边上权值为整型，定义邻接矩阵图的顶点信息表还有图的顶点数和边数。

Kruskal算法中有一个辅助数组，这里的存放的顶点信息的一维数组vexs的类型是用VertexType类型来表示的，这里把它定义成字符，在实际应用中可以根据需要把它重新定义为其他系统预定义类型或结构类型。

此外，邻接矩阵edges的类型用EdgeType 类型表示，这里把它定义为整型。

在实际应用中，若权值的类型是其他数据类型，则只需简单修改即可。

3.2 模块设计1.CreateMGraph创建一个邻接矩阵存储的图。

在提示下输入无向图的顶点数和边数，然后再输入各个顶点的信息，也就是顶点的编号，再输入顶点数组编号的下标表示的边和边上的权值，这中间非网图的边的权值为1。

2.Kruskal算法在扫描到邻接矩阵存放的信息后，用冒泡排序将边上的权值从小到大排列。

定义一个辅助数组，该数组是用来判断生成树中是否会出现回路，也就是生成正确的最小生成树。

判断边的连通分量编号不相等，将这条边打印出来，并将连通分量编号修改。

循环顶点数减一次，将最小生成树打印出来。

4测试4.1 测试数据主要的测试过程有两个：1. 对邻接矩阵的输入和存放。

克鲁斯卡尔算法运行，得出最小生成树。

2. 克鲁斯卡尔算法对存放的邻接矩阵的调用。

输入图的信息后算法得到正确结果。

调试阶段最重要的还是耐性和细心。

要有足够的耐性去对待令人烦躁的错误，一步步细心的调试，就会查出错误的所在。

我们进行调试、测试是为了让我们的代码、程序更加健壮，质量更高。

所以，我们不要畏惧报错，这是个学习进步的过程。

3.调试过程中的输入数据。

第一组测试数据见表4-1。

表4-1 调试数据权值50 60 40 65 52 45 50 30 42 70 顶点i 1 2 4 3 3 6 4 5 6 5第二组测试数据：表4-2 调试数据权值 1 1 1 1 1 1 顶点i 1 2 3 4 3 4 顶点j 0 0 0 0 1 2 第三组数据：表4-3 调试数据权值 1 6 4 2 5 3 顶点i 1 2 3 2 3 3 顶点j 0 0 0 1 1 24.2测试分析1.第一组数据测试结果运行程序后输入图的信息。

按照提示的格式输入，输入成功如下图4.1所示。

图4.1 输入图的信息后的界面输完信息后，程序运行得到最小生成树的结果。

图4.2 求得的最小生成树2.第二组数据测试结果运行程序后输入图的信息。

按照提示的格式输入，输入成功如下图4.3所示。

图4.3 输入图的信息后的界面输完信息后，程序运行得到最小生成树的结果。

图4.4 求得的最小生成树3.第三组数据测试结果运行程序后输入图的信息。

按照提示的格式输入，输入成功如下图4.5所示。

图4.5 输入图的信息后的界面输完信息后，程序运行得到最小生成树的结果。

图4.6求得的最小生成树5总结与体会5.1总结：克鲁斯卡尔算法中的核心思想就是逐个在边的集合中找到最小的边，如果满足条件就将其构造，最后生成一个最小生成树。

它首先是一系列的顶点集合，并没有边，然后我们从邻接矩阵中寻找最小的边，看看它是否和现有的边连接成一个环，如果连接成环，则舍弃，另外取其它的边。

如果不连接成环，则接受这个边，并把其纳入集合中。

5.2体会：在编程序过程中虽然遇到了很多问题，但也使我学到了很多东西，在编制程序过程中我学到了在编程的开始需要总体设计一下自己的程序需要哪些大的模块，并想好所要用到的知识及算法，在编程过程中，特别是要画图时需要找出坐标，并研究各坐标各结点之间连线的规律，通过几句判断语句来实现多条连线问题，在编程过好还要反复调试程序，找出其中的漏洞并加以改正，在此次编程过程中就存在这样的问题，在经过反复修改后，终于可将漏洞扫除，正确的输出结果。

参考文献[1]素若，万华，游明坤. 数据结构. 北京：中国水利水电出版社，2014.[2]严蔚敏，吴伟民.数据结构（C语言版）. 北京：清华大学出版社，2014.[3]素若，任正云，赖玲.C语言程序设计. 北京:：中国水利水电出版社，2014.[4]邓文华.数据结构（C语言版）. 北京：清华大学出版社，2011.附录全部代码#include<stdio.h>#include<stdlib.h>#define MaxVerNum 100 //设置邻接矩阵的最大顶点数typedef char VertexType; //设置图的顶点信息为整型typedef int EdgeType; //设置边上权值为整型typedef struct{VertexType vexs[MaxVerNum]; //图的顶点信息表EdgeType edge[MaxVerNum][MaxVerNum];//图的邻接矩阵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->vexs[i]));}for(i=0;i<g->n;i++) //将邻接矩阵数组初始化for(j=0;j<g->n;j++)g->edge[i][j]=0;//图的遍历算法初始化该值为0for(k=0;k<g->e;k++){printf("输入边的两个顶点号的下标，权值w(非网图权值为1)(格式为*,*,*):\n");scanf("%d,%d,%d",&i,&j,&w);g->edge[i][j]=w;g->edge[j][i]=w;}}void kruskal(MGraph *g){int i,j,k,s1,s2,num,vest[MaxVerNum];//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->edge[i][j]&&i<j){edge[k].u=i;edge[k].v=j;edge[k].w=g->edge[i][j];k++;}for(j=1;j<k;j++)//对边集权值采用冒泡排序for(i=0;i<k-j;i++)if(edge[i].w>edge[i+1].w){t=edge[i];edge[i]=edge[i+1];edge[i+1]=t;}for(i=0;i<g->e;i++)vest[i]=i;//初始化G中各顶点的vset值num=1;//构造生成树的第几条边，从1开始j=0;//从边集数组下标0开始处理while(num<g->n)//循环n-1次，构造n-1条边{v1=edge[j].u;v2=edge[j].v;//取边的两个顶点号s1=vest[v1];s2=vest[v2];//分别求两个顶点的连通分量的编号if(s1!=s2){printf("(%c,%c)--weight=%d\n",g->vexs[v1],g->vexs[v2],edge[j].w);num++;for(i=0;i<g->n;i++)if(vest[i]==s2)vest[i]=s1;//将vset值为s2的顶点的vset值改为s1}j++;}}void main(){MGraph *g=(MGraph*)malloc(sizeof(MGraph)); //申请图g的邻接矩阵表示空间CreateMGraph(g);kruskal(g);system("PAUSE");getchar();}。