最小生树课程设计.docVIP

工学系课程设计报告 设 计 题 目：最小生成树 系 别： 专 业 (方 向)： 年 级、 班： 学 生 姓 名： 学 生 学 号： 指 导 教 师： 年 月日 目录 一、系统开发的背景 1 二、系统分析与设计 1 （一） 系统功能要求 1 （二） 系统模块结构设计 1 三、系统的设计与实现 2 (一) 输入城市信息：create ( ) 2 （二） 判断是否能够生成最小生成树：judge( ) 2 （三） 求最小生成树：Kruskal( ) 3 四、系统测试 4 （一） 测试int menu ( )函数 4 （二） 测试void create ( )函数 4 （三） 测试void judge( )函数 5 （四） 测试void Kruskal( )函数 5 （五） 测试exit( )函数 5 五、总结 6 六、附件（代码、图表） 6 最小生成树 一、系统开发的背景 为了在保证连通即可的n个城市之间建设网络，求出最经济的架设方法，因此设计了这个程序PRIM算法和kruskal算法的基本思想求解出所有的最小生成树。存储结构可自行选择； 系统模块结构设计 通过对系统功能的分析，最小生成树功能如图1所示。 图1 最小生成树功能图 通过上图的功能分析，把整个系统划分为4个模块： 输入城市信息，该模块主要实现：输入城市的个数以及输入城市之间的邻接矩阵，借助函数create( )来实现； 判断是否生成模块，该模块主要实现判断是否能够生成最小生成树，借助函数judge ( )来实现； 3、 求最小生成树模块，该模块主要实现显示所输入城市之间各路段的权值，求出最小生成树，借助函数Kruskal( )来实现； 4、 退出模块，该模块主要实现终止正在执行的程序exit( )来实现； 三、系统的设计与实现 输入城市信息：create ( ) 分析：首先输入城市的基本信息。 该模块的具体代码如下所示： 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,arcs[i][j]); } } （二） 判断是否能够生成最小生成树：judge( ) 该模块的具体代码如下所示： void judge() { int close[100],low[100],i,j,ans=0; int use[100]; use[1]=1; for(i=2;i=n;i++) { low[i]=arcs[1][i]; close[i]=1; use[i]=0; } for(i=1;in;i++) { int min=100000000,k=0; for(j=2;j=n;j++) { if(use[j]==0minlow[j]) { min=low[j]; k=j; } } for(j=2;j=n;j++) { if(use[j]==0low[j]arcs[k][j]) { low[j]=arcs[k][j]; close[j]=k; } }ans+=arcs[close[k]][k]; } if(ans=100000000) printf(不能构成最小生成树\n); else printf(能构成最小生成树\n); } （三） 求最小生成树：Kruskal( ) 该模块的具体代码如下所示： void Kruskal() { int ans=0,i,j,k=0; int index; int count=0; for(i=1;i=n;i++) set(i); for(i=1;i=n;i++) { for(j=i+1;j=n;j++) { p[++k].str=i; p[k].end=j; p[k].dis=arcs[i][j]; } } for(i=1;i=k;i+