构造可以使n个城市连接的最小生成树

《构造可以使n个城市连接的最小生成树》由会员分享，可在线阅读，更多相关《构造可以使n个城市连接的最小生成树（10页珍藏版）》请在装配图网上搜索。

1、精品文档，仅供学习与交流，如有侵权请联系网站删除数据结构课程设计说 明 书学 院： 信息科学与工程学院 班 级： 计算机11-2 完 成 人：姓 名： 学 号： 201101050220 姓 名： 学 号： 201101050221 指导教师： 山 东 科 技 大 学2012年12月13日课 程 设 计 任 务 书一、课程设计题目： 构造可以使n个城市连接的最小生成树 二、课程设计应解决的主要问题：（1） 邻接矩阵的构造及其存储 （2） 判断是否能够生成最小生成树 （3） 克鲁斯算法的设计 （4） 利用克鲁斯算法构造最小生成树时是否产生回路的判断 （5） 界面的设计 三、任务发出日期： 201

2、2-11-28 课程设计完成日期： 2012-12-13 小组分工说明小组编号 35 题 目： 构造可使n个城市连接的最小生成树 小组分工情况： 王 露：算法设计，void Kruskal()函数，void set ()函数，void find()函数，void Union()函数王炜程：void creat()函数，void judge()函数，int main()函数；int menu()函数，void display()函数 组长签字： 年 月 日指导教师对课程设计的评价成绩： 指导教师签字： 年 月 日 目录 一、 主要问题-5二、 基本要求-5三、 算法基本思想描述-5四、 详细设计

3、-51、数据结构的设计- 5 存储结构- 5 图的表示-62、算法的设计-6 克鲁斯卡尔算法设计-6 防止不能构成最小生成树的图-6 模块结构及功能- 7 主要模块算法描述- 7五、源程序清单-9六、测试数据及测试结果-91、开始画面- 92、输入信息- 103、数据处理- 10 （1）判断能否构成最小生成树- 10（2）遍历所有的最小生成树- 10（3）退出- 11七、课程设计总结-11八、附录-11参考书目-15构造可以使n个城市连接的最小生成树一、主要问题给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。二、基本要求（1）城

4、市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。（2）表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）（3）最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。三、算法基本思想描述 Kruskal算法思想基本描述：假设连通图N=（V，E），则令最小生成树的初始状态为只有n 个顶点而无边的非连通图T=(V, )，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量

5、上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一个连通分量上为止。四、详细设计1、 数据结构的设计 存储结构邻接矩阵存储方法（数组存储方法），利用两个数组来存储一个图，其构造原理比较简单。对于具有n个顶点的图G=(V,E),定义一个具有n个元素的一维数组VERTEX0.n-1，将图中顶点的数据信息分别存入该数组的一个数组元素中。另外，定义一个二维数组A0.n-10.n-1,该二维数组通常被称为邻接矩阵。若以顶点在VERTEX数组中的下标来代表一个顶点，则邻接矩阵中元素Aij存放顶点i到顶点j之间的关系信息，有 1当顶点i与顶点j之间有边时Aij

6、= 0当顶点i与顶点j之间无边时对于网络，有 当顶点i与顶点j之间有边时，且边上的权值为时Aij = 当顶点i与顶点j之间无边时 图的表示 用n表示城市的个数，st表示起始城市，ed表示终点城市，dis表示两城市间的距离。下面是构成该结构体的源代码： typedef struct nodeint st ;/*起点*/int ed;/*终点*/int dis ;/*距离*/ node; node p； /*p数组用来储存城市和城市间的信息*/ 2 、算法的设计 克鲁斯卡尔算法设计a. 设置计数器E，初值为0，记录已选中的边数。将所有边从小到大排序，存于p 中。b. 从p 中选择一条权值最小的边，

7、检查其加入到最小生成树中是否会构成回路，若是，则此边不加入生成树；否则，加入到生成树中，计数器E累加1。 c. 从E中删除此最小边，转b继续执行，直到k=n-1, 算法结束 d. 判断是否构成回路的方法： 设置集合S，其中存放已加入到生成树中的边所连接的顶点集合，当一条新的边要加入到生成树中时，检查此边所连接的两个顶点是否都已经在S中，若是，则表示构成回路，否则，若有一个顶点不在S中 或者两个顶点都不在S中，则不够成回路。 防止不能构成最小生成树的图为避免输入的图构成的不是连通图，设计了judge ( ) 函数来判断输入数据构成的是否为连通图，此函数的主要算法是源于普里姆算法，经过改编，形成了

8、新的函数。 模块结构及功能主程序输入城市信息退出初始化判断是否为连通图求最小生成树判断是否构成回路将能够最小生成树的边集合打印输出最小生成树及代价a) int main ( ) /主程序b) int menu ( ) /菜单函数c) void create ( ) /输入城市信息函数d) void judge ( ) /判断是否能够生成最小生成树函数e) void display( ) /打印输出f) void set ( ) /初始化pre,rank函数g) void find（ ） /判断是否构成回路函数h) void Union ( ) /将能构成最小生成树的边添加到一个集合i) voi

9、d Krushal( ) /克鲁斯算法求最小生成树 主要模块算法描述Krushal算法描述：/*下面三个函数作用是检验当一条边添加进去，是否会产生回路*/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(rankx = ranky) prey = x; rankx +;else prey =

10、 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.st = i;pk.ed = j;pk.dis = aij; /*先把所有城市之间的路段看成一个边*/for(i=1;i=k;i+)/*把所有的边按从小到大进行排序*/index=i;for(j=i+1;j=k;j+

11、) if(pj.dis pindex.dis) index=j;temp=pindex;pindex=pi;pi=temp;for(i = 1;i = k;i +)if(find(pi.st) != find(pi.ed)/*如果这两点连接在一起不构成一个回路，则执行下面操作*/printf(t第%d条路段为：%d-%d,权值为%dn,+ count,pi.st,pi.ed,pi.dis);/*将这条边的起点、终点打印出来*/ans += pi.dis;/*说明这条路段要用*/Union(pi.st,pi.ed);printf(t遍历所有城市得到最小生成树的代价为: %dnn,ans);五、源

12、程序清单（详见附录）六、测试数据及测试结果11以一个6个城市、10条边的网络图为例进行测试 1611 20115196 11 22 14 9 18网络图GE = 邻接矩阵1、开始画面 2、输入信息 设置两顶点之间无边时权值为10000003、数据处理(1)、判断能否构成最小生成树（2）、遍历所有城市生成最小生成数2116 63115 65418生成的最小生成树（3）、退出七、课程设计总结通过最小生成树的学习，我学会了树的多种存储结构和遍历方法，最小生成树的设计可以应用于我们生活中。我们可以把生活中遇到的实际问题转化为一种算法问题来进行解决。八、附录源程序：#include #include #

13、include typedef struct node /*构造一个结构体，两个城市可以看成起点和终点，之间的道路可以看成一个边*/int st; /*起点*/int ed; /*终点*/int dis;/*距离*/node;node p1000,temp;/*p记录城市信息*/int pre1000,rank1000;/*用于判断是否构成回路*/int n=0,a100100;/*n表示城市个数，a记录城市间权值*/int menu( ) /*菜单函数*/int m;printf( 求最小生成树n);printf( _nn);printf( 1 输入城市之间的信息n);printf( 2 判

14、断是否能构成一个最小生成树n);printf( 3 遍历所有城市生成最小生成树n);printf( 4 退出n);printf( _nn);printf( 请输入所选功能-4n);scanf(%d,&m);return m;/*下面三个函数作用是检验当一条边添加进去，是否会产生回路*/void set(int x)/*初始化*/prex = x;int find(int x)/*找到这个点的祖先*/if(x != prex) prex = find(prex);return prex;void Union(int x,int y)/*将这两个添加到一个集合里去*/x = find(x);y =

15、 find(y); 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.st = i;pk.ed = j;pk.dis = aij; /*先把所有城市之间的路段看成一个边*/for(i=1;i=k;i+)/*把所有的边按从小到大进行排序*/index=i;

16、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.st) != find(pi.ed)/*如果这两点连接在一起不构成一个回路，则执行下面操作*/printf(t第%d条路段为：%d-%d,权值为%dn,+ count,pi.st,pi.ed,pi.dis);/*将这条边的起点、终点打印出来*/ans += pi.dis;/*说明这条路段要用*/Union(pi.st,pi.ed);printf(t遍历所有城市得到最小生成树的代价

17、为: %dnn,ans);void create( )/*输入城市信息*/int i,j;if(n != 0) char str100; printf(是否要确定输入新的城市之间的信息? (y/n) ?n); scanf(%s,str); if(strcmp(str,n) = 0 )return ;printf(请输入城市的个数:n);scanf(%d,&n); printf(输入%d个城市的邻接矩阵:n,n);for(i = 1;i = n;i +)for(j = 1;j = n;j +)scanf(%d,&aij);void display( )/*显示生成的最小生成树*/if(n = 0

18、)printf(这里没有城市之间的信息n);return; printf(遍历所有城市得到最小生成树为：nnn); Kruskal( );void judge( )/*判断是否能够生成最小生成树*/ int close100,low100,i,j,ans = 0;/*closej表示离j最近的顶点，lowj表示离j最短的距离*/ int use100; use1 = 1; for(i = 2;i = n;i +) lowi = a1i; /*初始化*/ closei = 1; usei = 0; for(i = 1;i n;i +) int min = 1000000,k = 0; for(j

19、 = 2;j lowj)/*找到最小的low值，并记录*/min = lowj;k = j; for(j = 2;j akj)lowj = akj; /*修改low值和close值*/ closej = k; if(aclosekk=1000000) count=1; if(count=1) printf(不能构成最小生成树n); else printf(能构成最小生成树n);int main( ) /*主函数*/ while(1) switch( menu( ) ) case 1:create( );break;/*输入城市信息*/ case 2:judge( );break;/*判断是否能够生成最小生成树*/ case 3:display( );break; /*显示生成的最小生成树*/ case 4:exit( 0 ); return 0;参考书目1数据结构 严蔚敏，吴伟民 清华大学出版社2数据结构习题与解析 严蔚敏，吴伟民 清华大学出版社3Data Structures and Algorithm Analysis in C: Second Edition, Mark Allen Weiss, Person4C语言课程设计案例精编，郭翠英，中国水利出版社【精品文档】第 - 10 - 页