计算机科学与技术系 课程设计报告 2014-2015学年第二学期 课程 数据结构 课程设计名称 Kruskal算法求最小生成树 学生姓名 学号 专业班级 软件工程 指导教师 2014年X月 题目：设计程序完成如下功能：对给定过的网和起点，用kruskal算法的基本思想求解其所有的最小生成树 1、问题分析和任务定义 根据课设题目要求，拟将整体程序分为三大模块。以下是三个模块的大体分析：
要确定图的存储形式，通过对题目要求的具体分析。发现该题的主要操作是路径的输出，因此采用边集数组（每个元素是一个结构体，包括起点、终点和权值）和邻接矩阵比较方便以后的编程。
Kruskal算法。该算法设置了集合A，该集合一直是某最小生成树的子集。在每步决定是否把边（u,v）添加到集合A中，其添加条件是A∪{（u,v）}仍然是最小生成树的子集。我们称这样的边为A的安全边，因为可以安全地把它添加到A中而不会破坏上述条件。
2 数据结构的选择和概要设计 存储结构 定义一个结构体数组，其空间足够大，可将输入的字符串存于数组中。
struct edges {int bv; int tv; int w; }; 概要设计。
算法思想 ：
算法会先按照权重的非递减顺序对图中的边进行排序。然后从一个空子图开始，扫描这个有序表，试图把列表中的下一条边加到当前的子图中。当然，这种添加不应导致一个回路，如果产生回路，就把这条边跳过。当图的所有顶点都包含在所构造的树中以后，算法停止。
算法的基本思路是：
K r u s k a l算法每次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生成树。K r u s k a l算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边，每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃，否则，将它选入。
假设每个点都有一对标号（dj,pj）,其中d是从起源点到点j的最短路径的长度（从顶点到其本身的最短路径是零路（没有弧的路），其长度等于零）；
pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：
1）
初始化。起源点设置为：①ds=0,ps为空；
②所有其它点：di=∞,pi=？；
③标记起源点s，记k=s，其他所有点设为未标记的。
2）
k到其直接连接的未标记的点j的距离，并设置：
dj=min[dj, dk+lkj] 式中，lkj是从点k到j的直接连接距离。
3）
选取下一个点。从所有未标记的结点中，选取dj中最小的一个i：
di=min[dj, 所有未标记的点j] 点i就被选为最短路径中的一点，并设为已标记的。
4）找到点i的前一点。从已标记的点中找到直接连接到i的点j*，作为前一点，设置：
i=j* 5)标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，转到2）再继续。
而程序中求两点间最短路径算法。其主要步骤是：
① 调用dijkstra算法。
② 将path中的第“终点”元素向上回溯至起点，并显示出来。
3详细设计和编码 功能模块图 开始 输入顶点个数n 输入边数e 输入边集 显示菜单，进行选择。
求两点间最短距离 求两点间最短距离 Kruskal算法 结束 图3.1 功能模块图 流程图分析 1. 主函数 开始 输入顶点个数n 输入边数e 输入选项a a=1 调用insertsort，kruskal函数 a=2 输入v0 调用dijkstra，printpath1函数 a=3 输入v0,v1 调用dijkstra，printpath2函数 输入a=4 结束 图3.2主函数流程图 2. insertsort函数 开始 int i,j for(i=2;i<=e;i++) ge[i].w<ge[i-1].w ge[0]=ge[i]; j=i-1; ge[0].w<ge[j].w ge[j+1]=ge[j]; j--; Y ge[j+1]=ge[0]; N Y 结束 N 图3.3insertsort函数流程图 3．Kruskal函数 开始 int set[MAXE],v1,v2,i,j; for(i=1;i<n+1;i++) set[i]=0; i=1; j=1; j<=e&&i<=n-1 v1!=v2 v1=seeks(set,ge[j].bv); v2=seeks(set,ge[j].tv); printf(“(%d,%d):%d＼n“,ge[j].bv,ge[j].tv,ge[j].w); set[v1]=v2; i++; j++; Y Y 结束 N N 图3.4 Kruskal函数流程图 4 上机调试过程 调试过程 在调试程序时主要遇到一下几类问题：
1. 有时函数中一些数组中的数据无法存储。
2. 对其进行检验发现没有申请空间大小。
3. 在源程序的开头用#define定义数值大小，在使用数组时亦可知道它的空间大小。
4. 此函数中有时出现负值。
5. 对其进行检验发现在程序中∞由32767代替。若cost[u][w]==32767，那么cost[u][w]+dist[u]肯定溢出主负值，因此造成权值出现负值。
6. 但是当cost[u][w]==32767，那么dist[w]肯定不需要重新置数。所以将if（s[w]==0&&cost[u][w]+dist[u]<dist[w]）改为：if(s[w]==0&&cost[u][w]+dist[u]<dist[w]&&cost[u][w]!=32767)。问题得到解决。
程序执行过程 系统使用说明：
1. 输入的数据可以是整数，字符串（如1,2,3）；
2. 本系统可以建立带权图，并能够用Kruskal算法求改图的最小生成树。而且能够选择图上的任意一点做根结点。还能够求两点之间的最短距离。
3. 该系统会有菜单提示，进行选项：
1.kruskal 4.exit 5.测试结果及其分析 结果截图 图5.1 输入形式 图5.2 kruskal算法输出 图5.3kruskal算法输出 算法描述 1. Kruskal函数：
因为Kruskal需要一个有序的边集数组，所以要先对边集数组排序。其次，在执行中需要判断是否构成回路，因此还需另有一个判断函数seeks，在Kruskal中调用seeks。
2. dijkstra函数：
因为从一源到其余各点的最短路径共有n-1条，因此可以设一变量vnum作为计数器控制循环。该函数的关键在于dist数组的重新置数。该置数条件是：该顶点是被访问过，并且新起点到该点的权值加上新起点到源点的权值小于该点原权值。因此第一次将其设为：if（s[w]==0&&cost[u][w]+dist[u]<dist[w]）。但是在实际运行中，发现有些路径的权值为负。经过分析发现，因为在程序中∞由32767代替。若cost[u][w]==32767，那么cost[u][w]+dist[u]肯定溢出主负值，因此造成权值出现负值。但是如果cost[u][w]==32767，那么dist[w]肯定不需要重新置数。所以将条件改为：if(s[w]==0&&cost[u][w]+dist[u]<dist[w]&&cost[u][w]!=32767)。修改之后问题得到解决。
6用户使用说明 1. 打开创天中文c++软件。
2. 将写好的代码<附录部分>导入软件中并且运行。
3. 对照上述说明运行并检查程序。
7参考文献 [1]王昆仑，李红.《数据结构与算法》北京：中国铁道出版社，2006年5月 [2]严蔚敏 ，吴伟民. 《数据结构》（C语言版）.清华大学出版社.2007 [3]张德富. 《算法设计与分析》.国防工业出版社.2009 [4]朱青. 《计算机算法与程序设计》.清华大学出版社.2009 [5]徐宝文，李志. 《C程序设计语言》机械工业出版社.2004 8附 录（关键部分程序清单）
程序代码 #include“stdio.h“ #define MAXE 100 struct edges {int bv; //起点 int tv; //终点 int w;//权值 }; typedef struct edges edgeset; int seeks(int set[],int v) //顶点集，顶点v { int i; i=v; while(set[i]>0) i=set[i]; return i; } void kruskal(edgeset ge[],int n,int e) //边集，顶点数n，边数e { int set[MAXE],v1,v2,i,j,x,y=1; //输入顶点集 edgeset xy[MAXE]; for(i=1;i<n+1;i++) set[i]=0; i=1; j=1; printf(“第%d个最小生成树:＼n“,1);//判断第几个最小生成树 while(j<=e&&i<=n-1) { v1=seeks(set,ge[j].bv); //起点 v2=seeks(set,ge[j].tv); //终点 if(v1!=v2) { xy[j]=ge[j]; printf(“(%d,%d):%d＼n“,ge[j].bv,ge[j].tv,ge[j].w); set[v1]=v2; i++; //计数器（判断顶点数是否溢出）
} j++; } y++; while(ge[j-1].w==ge[j].w){ //输出所有最小生成树 printf(“第%d个最小生成树为:＼n“,y); for(x=1;x<=j-2;x++){ printf(“(%d,%d):%d＼n“,xy[x].bv,xy[x].tv,xy[x].w); } printf(“(%d,%d):%d＼n“,ge[j].bv,ge[j].tv,ge[j].w); j++; y++; } } void insertsort(edgeset ge[],int e) //对权值进行排序 { int i,j; for(i=2;i<=e;i++) if(ge[i].w<ge[i-1].w) { ge[0]=ge[i]; j=i-1; while(ge[0].w<ge[j].w) { ge[j+1]=ge[j]; j--; } ge[j+1]=ge[0]; } } main() { edgeset ge[MAXE]; int a,n,e,i; printf(“请输入顶点个数:“); scanf(“%d“,&n); printf(“请输入边的条数:“); scanf(“%d“,&e); printf(“请输入边的信息（起点，终点，权值）:＼n“); for(i=1;i<=e;i++) scanf(“%d,%d,%d“,&ge[i].bv,&ge[i].tv,&ge[i].w); printf(“在下列菜单中进行选择：＼n“); printf(“1.kruskal算法（（起点，终点）权值）：＼n“); printf(“2.exit（退出）：＼n“); scanf(“%d“,&a); while(a!=2) { switch(a) { case 1:insertsort(ge,e); kruskal(ge,n,e); break; } printf(“在下列菜单中进行选择：＼n“); printf(“1.kruskal算法（（起点，终点）权值）：＼n“); printf(“2.exit（退出）：＼n“); scanf(“%d“,&a); } return 1; } 合肥学院