最小生树课程设计.docVIP

  1. 1、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。。
  2. 2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  3. 3、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  4. 4、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  5. 5、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  6. 6、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  7. 7、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
最小生树课程设计

工学系课程设计报告 设 计 题 目:最小生成树 系 别: 专 业 (方 向): 年 级、 班: 学 生 姓 名: 学 生 学 号: 指 导 教 师: 年 月日 目录 一、系统开发的背景 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+

文档评论(0)

3471161553 + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档