网络光纤铺设的最佳方案选择

《网络光纤铺设的最佳方案选择》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、广东海洋大学信息学院课程设计报告设计题目网络光纤铺设的最佳方案选择课程名称数据结构姓名（学号）联系电话专业名称计算机科学与技术所在班级计科1111班指导教师谢仕义教师职称教授起止时间2011年12月26日至2012年1月6日评定成绩一、课程设计的主要内容需要在某个城市n个居民小区之间铺设网络光纤，假设任意两个居民小区之间均需要铺设光纤，则在这n个居民小区之间只需要铺设n-1条光纤即可形成一个网络，但由于地理环境不同，所需要的代价也不尽相同。本课程设计要求事先随机生成任意居民小区之间铺设网络光纤的代价，并将代价存入文件，然后设计一个最佳方案进行光纤铺设，使得既能连通所有小区之间

2、的网络，又能使网络光纤铺设的代价最小，最终以图形形式输出所设计的最佳方案。一、功能和结构设计1.普里姆算法分析①普里姆算法思想普利姆算法的思想是：在图中人去一个定点k0作为开始点，令U={k0}，W=V-U，其中V为图中所有顶点集，然后找一个顶点在U中，另一个顶点在w中的边中最短的一条，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删除这些顶点，然后重新调整U中顶点到W中顶点的距离，使之保持最小，再重复此过程，直到W为空集。②改算法过程描述a．在图G=（V，E）（V是顶点，E是边）中，从集合V中任取一个顶点，如k0放入集合U中，这时，U={

3、k0}，集合T（E）为空。b．从k0出发寻找与U中顶点相邻权值最小的边的另一顶点k1，并使k1加入U。即U={k0，k1}，同时将该边加入集合T（E）中。c．重复（2），直到U=V为止。d．这时T（E）中有n-1条边，T=（U，T（E））就是一一颗最小生成树。2.模块分析根据对模型的功能分析，该管道铺设设计可以具有以下功能：①．网络光纤铺设信息的输入；②．最小生成树信息的输出；下面我们给出相应的功能模块图：1.抽象数据类型分析areanum居民区总数（顶点总数）；edgenum边的总数；date[][20]邻接矩阵存储图结构；s边的权值；short-way[i]居民区i到目前

4、生成树中所有点集U中某个居民区的路程最小值near-area[i]U中能使其最小的居民区4．功能分析假设居民区分布和各居民区之间的距离如下图显示则通过网络光纤铺设的最佳方案选择后结果如下面显示程序开始信息输入输出结果一、流程图和算法设计1.详细算法分析①信息输入模块//输入顶点个数和边的条数cout<<"请输入居民区个数：";cin>>areanum;cout<>edgenum;//初始化矩阵各元素值inti,j,k;for(i=0；i

5、ate[i][j]=INFINITY;//读入边intfrom,to,s;cout<<"请按此格式输入边和权值：i,j,k（表示i居民区到j居民区的距离为k米）";for(i=0;i>from>>to>>m;date[from][to]=s;date[to][from]=st;}//输出邻接矩阵for(i=0;i

6、tareanum,intnear_area[]){//辅助数组short_way,near_area//short_way[i]表示居民区i到到目前生成树中所有点集U中某个居民区（点）的路程最小值//near_city[i]表示U中能使其最小的居民区(点)intshort_way[areanum];intmin;inti,j,k;//0已经放入U中//初始化short_way和near_areafor(i=1;i

7、;for(i=1;i