最小生成树地课程设计

《最小生成树地课程设计》由会员分享，可在线阅读，更多相关《最小生成树地课程设计（17页珍藏版）》请在装配图网上搜索。

1、word数据结构与算法课程设计报告课程设计题目： 构造可以使n个城市连接的最小生成树专业班级： 信息与计算科学1001班 姓 名： 学 号： 设计室号： 理学院机房 设计时间： 2011-12-26 批阅时间： 指导教师： 成 绩： 构造可以使n个城市连接的最小生成树主要任务：给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。设计该程序的根本要求：1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，假如两个城市之间不存在道路，如此将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包

2、括了哪些城市间的道路，并显示得到的最小生成树的代价。2、表示城市间距离网的邻接矩阵要求至少6个城市，10条边3、最小生成树中包括的边与其权值，并显示得到的最小生成树的代价。总体设计1 该程序的主要功能：能实现根据输入城市的信息可以判断该城市间的距离网是否构成最小生成树，遍历城市生成最小生成树，通过计算得到最小生成树的代价。 2 该城市间的距离网用邻接矩阵表示 3 用克鲁斯卡尔Kruskal算法建立最小生成树详细设计说明 1 该程序的主要功能：能实现根据输入城市的信息可以判断出该城市间的距离网是否构成最小生成树，遍历城市生成最小生成树，通过计算得到最小生成树的代价。 该程序的模块结构功能图与主要

3、函数如下： 开始 输入城市信息是否为连通图？ 求最小生成树初始化是否构成回路？将最小生成树边集合打印出最小生成树的权值与最小生成树的代价退出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 ( ) /将能构成最小生成树的边添加到一个集合l void K

4、rushal( ) /克鲁斯算法求最小生成树体会确定程序功能设计出总体流程对整个设计进展非常重要，明确要完成设计需要的程序算法，为整个设计流程划出大纲，可以使整个设计思路更加简单明了。2构造结构体此题为求最小生成树，先要构造一个结构体，再用邻接矩阵的形式表现出来。#define max 20#define MAX_LNT 10typedef struct node /*构造一个结构体，两个城市可以看成起点和终点，之间的道路可以看成一个边*/int str; /*起点*/int end; /*终点*/int dis;/*距离*/node;node pmax,temp;/*p记录城市信息*/int

5、 pre100,rank100;/*用于判断是否构成回路*/int n=0,arcsMAX_LNTMAX_LNT;/*n表示城市个数，arcs记录城市间权值*/3初始化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 +

6、; else prey = x; 该城市间的距离网使用邻接矩阵表示，邻接矩阵存储方法数组存储方法，利用两个数组来存储一个图。用a i j数组，利用邻接矩阵方式来储存城市与城市间信息 。void create( )/*输入城市信息*/int i,j;printf(请输入城市的个数:n);scanf(%d,&n); printf(输入%d个城市的邻接矩阵:n,n);for(i = 1;i = n;i +)for(j = 1;j = n;j +)scanf(%d,&arcsij);3 算法设计1克鲁斯卡尔算法思想根本描述：假设连通图N=V，E，如此令最小生成树的初始状态为只有n 顶点而无边的非连通图

7、T=(V, )，图中每个顶点自成一个连通分量。在E中选择代价最小的边，假如该边依附的顶点落在T中不同的连通分量上，如此将此边参加到T中，否如此舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一个连通分量上为止。2克鲁斯卡尔算法设计a. 设置计数器E，初值为0，记录已选中的边数。将所有边从小到大排序，存于p 中。b. 从p 中选择一条权值最小的边，检查其参加到最小生成树中是否会构成回路，假如是，如此此边不参加生成树；否如此，参加到生成树中，计数器E累加1。 c. 从E中删除此最小边，转b继续执行，直到k=n-1, 算法完毕d. 判断是否构成回路的方法： void Kruskal

8、( ) 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 = arcsij; /*先把所有城市之间的路段看成一个边*/for(i=1;i=k;i+)/*把所有的边按从小到大进展排序*/index=i;for(j=i+1;j=k;j+) if(pj.di

9、s 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,+ count,pi.str,pi.end,pi.dis);/*将这条边的起点、终点打印出来*/ans += pi.dis;/*说明这条路段要用*/Union(pi.str,pi.end); printf(t遍历所有城市得到最小生成树的代价为: %dnn,ans);设置集合

10、S，其中存放已参加到生成树中的边所连接的顶点集合，当一条新的边要参加到生成树中时，检查此边所连接的两个顶点是否都已经在S中，假如是，如此表示构成回路，否如此，假如有一个顶点不在S中或者两个顶点都不在S中，如此不够成回路。void judge( )/*判断是否能够生成最小生成树*/ 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

11、 = 1;i n;i +) int min = 100000000,k = 0; for(j = 2;j lowj)/*找到最小的low值，并记录*/min = lowj;k = j; for(j = 2;j arcskj)lowj = arcskj; /*修改low值和close值*/ closej = k; ans += arcsclosekk; if(ans = 100000000) printf(不能构成最小生成树n); else printf(能构成最小生成树n);克鲁斯卡尔算法(Kruskals algorithm)是两个经典的最小生成树算法的较为简单理解的一个。这里面充分表现了贪

12、心算法的精髓。克鲁斯卡尔算法生成最小生成树的过程3防止不能构成最小生成树的图为防止输入的图构成的不是连通图，设计了judge ( ) 函数来判断输入数据构成的是否为连通图，此函数的主要算法是源于普里姆PRIM算法，经过改编，形成了新的函数。4主函数的设计int main( ) /*主函数*/ while(1) switch( menu( ) ) case 1:create( );break;/*输入城市信息*/ case 2:judge( );break;/*判断是否能够生成最小生成树*/ case 3:display( );break; /*显示生成的最小生成树*/ case 4:exit(

13、 0 ); return 0;调试与测试211以一个6个城市、10条边的网络图为例进展测试 1663 20115196 45 22 14 9 18网络图GE =邻接矩阵生成界面输入城市间信息判断是否生成最小生成树遍历所有城市最小生成树退出程序源代码#include #include #include #define max 20#define MAX_LNT 10typedef struct node /*构造一个结构体，两个城市可以看成起点和终点，之间的道路可以看成一个边*/int str; /*起点*/int end; /*终点*/int dis;/*距离*/node;node pmax,

14、temp;/*p记录城市信息*/int pre100,rank100;/*用于判断是否构成回路*/int n=0,arcsMAX_LNTMAX_LNT;/*n表示城市个数，arcs记录城市间权值*/int menu( ) /*菜单函数*/ int m;printf(.2011年12月29日.nn);printf( 求最小生成树n);printf( _nn);printf( 1 输入城市之间的信息n);printf( 2 判断是否能构成一个最小生成树n);printf( 3 遍历所有城市生成最小生成树n);printf( 4 退出n);printf( _nn);printf( 请输入所选功能1-

15、4n);system(color A);/*改变界面颜色的，对程序没什么影响*/scanf(%d,&m);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(rankx = ranky) prey =

16、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 = arcsij; /*先把所有城市之间的路段看成一个边*/for(i=1;i=k;i+)/*把所有的边按从小到大进

17、展排序*/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,+ count,pi.str,pi.end,pi.dis);/*将这条边的起点、终点打印出来*/ans += pi.dis;/*说明这条路段要用*/Union(pi.str,pi.end); pr

18、intf(t遍历所有城市得到最小生成树的代价为: %dnn,ans);void create( )/*输入城市信息*/int i,j;printf(请输入城市的个数:n);scanf(%d,&n); printf(输入%d个城市的邻接矩阵:n,n);for(i = 1;i = n;i +)for(j = 1;j = n;j +)scanf(%d,&arcsij);void display( )/*显示生成的最小生成树*/if(n = 0)printf(这里没有城市之间的信息n);return; printf(遍历所有城市得到最小生成树为：nnn); Kruskal( );void judge(

19、 )/*判断是否能够生成最小生成树*/ 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 lowj)/*找到最小的low值，并记录*/min = lowj;k = j; for(j = 2;j arcskj)lowj = ar

20、cskj; /*修改low值和close值*/ closej = k; ans += arcsclosekk; if(ans = 100000000) 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;17 / 17