广工数据结构课程设计最小生成树

1、课程设计课程名称 数据结构 学 院 专业班级 学 号 学生姓名 指导教师 2015年7月2日1. 需求分析 题目：最小生成树问题若要在n个城市之间建设通讯网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通讯网，是一个网的最小生成树问题。要求： （1）利用克鲁斯卡尔算法求网的最小生成树。 （2）实现并查集。以此表示构造生成树过程中的连通分量。（3） 以文本形式输出生成树中各条边以及他们的权值。输入的形式和输入值的范围：十进制数，0100。输出的形式：十进制数。程序所能达到的功能：遍历所有城市生成最小生成树。测试数据： 正确数据： 城市个数3；3个城市的邻接矩阵：(1,2,3;2,1

2、00,4;3,4,6) 输出结果：第1条路段为12，权值为2 第2条路段为13，权值为3 遍历所有城市得到最小生成树的代价为：5 错误数据：城市个数3；城市的邻接矩阵：(-2,5,1;3,0,1;3,2,1) 输出结果：输入错误，请重新输入2.概要设计 数据类型定义如下： typedef struct node int str; /*起点*/ int end; /*终点*/ int dis;/*距离*/node;node pmax,temp; /*p记录城市信息*/ int pre100,rank100;/*用于判断是否构成回路*/int n=0,arcsMAX_LNTMAX_LNT;/*n表

3、示城市个数，arcs记录城市间权值*/主程序流程如下：3.详细设计 （1）克鲁斯卡尔算法思想基本描述：假设连通图N=（V，E），则令最小生成树的初始状态为只有n 顶点而无边的非连通图T=(V, )，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一个连通分量上为止。 （2）克鲁斯卡尔算法设计：a.  设置计数器E，初值为0，记录已选中的边数。将所有边从小到大排序，存于p 中。 b. 从p 中选择一条

4、权值最小的边，检查其加入到最小生成树中是否会构成回路，若是，则此边不加入生成树；否则，加入到生成树中，计数器E累加1。c. 从E中删除此最小边，转b继续执行，直到k=n-1, 算法结束 。判断是否回路：设置集合S，其中存放已加入到生成树中的边所连接的顶点集合，当一条新的边要加入到生成树中时，检查此边所连接的两个顶点是否都已经在S中，若是，则表示构成回路，否则，若有一个顶点不在S中   或者两个顶点都不在S中，则不够成回路。/*需要的函数声明*/int   main (  )&

5、#160;            /主程序int   menu (  )            /菜单函数void  create (  )         &

6、#160; /输入城市信息函数void  judge (  )            /判断是否能够生成最小生成树函数void  display(  )          /打印输出void  set (  ) 

7、0;          /初始化pre,rank函数void  find  (  )         /判断是否构成回路函数void  Union (  )        /将能构成最小生成树的边添加到一个集合void&

8、#160; Krushal(  )       /克鲁斯算法求最小生成树/*菜单函数*/int menu( ) int m; printf(".2015年7月2日.nn"); printf(" 求最小生成树n"); printf(" _nn"); printf(" 1 输入城市之间的信息n"); printf(" 2 判断是否能构成一个最小生成树n"); printf(" 3 遍历所有城

9、市生成最小生成树n"); printf(" 0 退出n"); printf(" _nn"); printf(" 请输入所选功能0-3n"); scanf("%d",&m); if(m<0|m>3) return 4; return m; /*下面三个函数作用是检验当一条边添加进去，是否会产生回路*/void set(int x)/*初始化*/ prex = x; rankx = 0;/*找到这个点的祖先*/ int find(int x) if(x != prex) prex = fi

10、nd(prex); return prex; /*将这两个数添加到一个集合里去*/ void Union(int x,int y) x = find(x); y = find(y); if(rankx >= ranky) prey = x; rankx +; else prey = x;/*克鲁斯算法求最小生成树*/void Kruskal( ) int ans = 0,i,j,k = 0; /*ans用来记录生成最小树的权总值*/ int index; int count = 0; /*记录打印边的条数*/ for(i = 1;i <= n;i +) /*初始化数组prex,ra

11、nkx*/ set(i); for(i = 1;i <= n;i +) for(j = i + 1;j <= n;j +) p+k.str = i; pk.end = j; pk.dis = arcsij; /*先把所有城市之间的路段看成一个边*/ for(i=1;i<=k;i+) /*把所有的边按从小到大进行排序*/ index=i; for(j=i+1;j<=k;j+) if(pj.dis <pindex.dis) index=j; temp=pindex; pindex=pi; pi=temp; for(i = 1;i <= k;i +) if(fin

12、d(pi.str) != find(pi.end)/*如果这两点连接在一起不构成一个回路，则执行下面操作*/ printf("t第%d条路段为：%d-%d,权值为%dn",+ count,pi.str,pi.end,pi.dis);/*将这条边的起点、终点打印出来*/ ans += pi.dis; /*说明这条路段要用*/ Union(pi.str,pi.end); printf("t遍历所有城市得到最小生成树的代价为: %dnn",ans);/*输入城市信息*/ void create( ) int i,j; printf("请输入城市的个数

13、（130）:n"); scanf("%d",&n); if(n<=0|n>30) printf("输入错误，请重新输入n");return ; printf("输入%d个城市存储边(带权)的数组（数值范围：1-99，用100表示，）:n",n); for(i = 1;i <= n;i +) for(j = 1;j <= n;j +) scanf("%d",&arcsij); if(arcsij<1|arcsij>100) printf("输入错

14、误，请重新输入n"); return ; for(i=0;i<n;i+) for(j=0;j<i;j+) if(arcsij!=arcsji) /*判断矩阵是否对称*/ printf("输入错误，请重新输入n"); return ;/*显示生成的最小生成树*/void display( ) if(n = 0) printf("这里没有城市之间的信息n"); return; printf("遍历所有城市得到最小生成树为：nnn"); Kruskal( );/*判断是否能够生成最小生成树*/void judge( )

15、 int close100,low100,i,j,ans = 0;/*closej表示离j最近的顶点，lowj表示离j最短的距离*/ int use100; use1 = 1; for(i = 2;i <= n;i +) lowi = arcs1i; /*初始化*/ closei = 1; usei = 0; for(i = 1;i < n;i +) int min = 100000000,k = 0; for(j = 2;j <= n;j +) if(usej = 0 && min > lowj)/*找到最小的low值，并记录*/ min = lowj

16、; k = j; for(j = 2;j <= n;j +) if(usej = 0 && lowj > arcskj) lowj = arcskj; /*修改low值和close值*/ closej = k; ans += arcsclosekk; if(ans >= 100000000) printf("不能构成最小生成树n"); else printf("能构成最小生成树n");/*主函数*/void main() while(1) switch( menu( ) ) case 1:create( );break;

17、/*输入城市信息*/ case 2:judge( );break;/*判断是否能够生成最小生成树*/ case 3:display( );break; /*显示生成的最小生成树*/ case 0:exit( ); default: printf("输入错误，请重新选择。n"); break; 4.调试分析本课程设计重点在于生成最小生成树算法。克鲁斯卡尔算法将图中边按其权值由小到大的次序顺序选取,若选边后不形成回路,则保留作为一条边,若形成回路则除去，依次选够(n-1)条边,即得最小生成树。在克鲁斯卡尔算法中，图的存贮结构采用边集数组,且权值相等的边在数组中排列次序可以是任意

18、的，该方法对于边相对比较多的不是很实用。本课程设计为求最小生成树，先要构造一个结构体，再用邻接矩阵的形式表现出来。城市间的距离网使用邻接矩阵表示，邻接矩阵存储方法（数组存储方法），利用两个数组来存储一个图。用a i j数组，利用邻接矩阵方式来储存城市与城市间信息 。5.用户使用说明 按顺序依次输入城市之间的信息，判断是否能构成一个最小生成树，再生成遍历所有城市的最小生成树。如果输入过程中出现错误，需重新输入。城市存储边(带权)矩阵中的用100表示，矩阵必须对称。6.测试结果7. 源代码#include<stdio.h>#include <stri

19、ng.h> #include <stdlib.h>#define max 100#define MAX_LNT 30typedef struct node /*构造一个结构体，两个城市可以看成起点和终点，之间的道路可以看成一个边*/ int str; /*起点*/ int end; /*终点*/ int dis;/*距离*/node;node pmax,temp; /*p记录城市信息*/ int pre100,rank100;/*用于判断是否构成回路*/int n=0,arcsMAX_LNTMAX_LNT;/*n表示城市个数，arcs记录城市间权值*/int menu( )

20、/*菜单函数*/ int m; printf(".2015年7月2日.nn"); printf(" 求最小生成树n"); printf(" _nn"); printf(" 1 输入城市之间的信息n"); printf(" 2 判断是否能构成一个最小生成树n"); printf(" 3 遍历所有城市生成最小生成树n"); printf(" 0 退出n"); printf(" _nn"); printf(" 请输入所选功能0-3n

21、"); scanf("%d",&m); if(m<0|m>3) return 4; return m; /*下面三个函数作用是检验当一条边添加进去，是否会产生回路*/void set(int x)/*初始化*/ prex = x; rankx = 0; int find(int x)/*找到这个点的祖先*/ if(x != prex) prex = find(prex); return prex; void Union(int x,int y)/*将这两个添加到一个集合里去*/ x = find(x); y = find(y); if(rank

22、x >= ranky) prey = x; rankx +; else prey = x;/*克鲁斯算法求最小生成树*/void Kruskal( ) int ans = 0,i,j,k = 0; /*ans用来记录生成最小树的权总值*/ int index; int count = 0; /*记录打印边的条数*/ for(i = 1;i <= n;i +) /*初始化数组prex,rankx*/ set(i); for(i = 1;i <= n;i +) for(j = i + 1;j <= n;j +) p+k.str = i; pk.end = j; pk.dis

23、 = arcsij; /*先把所有城市之间的路段看成一个边*/ for(i=1;i<=k;i+) /*把所有的边按从小到大进行排序*/ index=i; for(j=i+1;j<=k;j+) if(pj.dis <pindex.dis) index=j; temp=pindex; pindex=pi; pi=temp; for(i = 1;i <= k;i +) if(find(pi.str) != find(pi.end)/*如果这两点连接在一起不构成一个回路，则执行下面操作*/ printf("t第%d条路段为：%d-%d,权值为%dn",+ c

24、ount,pi.str,pi.end,pi.dis);/*将这条边的起点、终点打印出来*/ ans += pi.dis; /*说明这条路段要用*/ Union(pi.str,pi.end); printf("t遍历所有城市得到最小生成树的代价为: %dnn",ans);/*输入城市信息*/ void create( ) int i,j; printf("请输入城市的个数（130）:n"); scanf("%d",&n); if(n<=0|n>30) printf("输入错误，请重新输入n");r

25、eturn ; printf("输入%d个城市存储边(带权)的数组（数值范围：1-99，用100表示，）:n",n); for(i = 1;i <= n;i +) for(j = 1;j <= n;j +) scanf("%d",&arcsij); if(arcsij<1|arcsij>100) printf("输入错误，请重新输入n"); return ; for(i=0;i<n;i+) for(j=0;j<i;j+) if(arcsij!=arcsji) /*判断矩阵是否对称*/ printf("输入错误，请重新输入n"); return ;/*显示生成的最小生成树*/ void display( ) if(n = 0) printf("这里没有城市之间的信息n"); re