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

广东海洋大学信息学院 课程设计报告 设计题目 网络光纤铺设的最佳方案选择 课程名称 数据结构 姓名（学号） 联系电话 专业名称 计算机科学与技术 所在班级 计科1111班 指导教师 谢仕义 教师职称 教授 起止时间 2011 年12月26日至 2012年1月6日 评定成绩 课程设计的主要内容 需要在某个城市n个居民小区之间铺设，则在这n个居民小区之间只需要铺设n-1条即可但由于地理环境不同，所需要的也不尽相同。k0作为开始点，令U={k0}，W=V-U，其中V为图中所有顶点集，然后找一个顶点在U中，另一个顶点在w中的边中最短的一条，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删除这些顶点，然后重新调整U中顶点到W中顶点的距离，使之保持最小，再重复此过程，直到W为空集。 改算法过程描述 在图G=（V，E）（V是顶点，E是边）中，从集合V中任取一个顶点，如k0放入集合U中，这时，U={k0}，集合T（E）为空。 从k0出发寻找与U中顶点相邻权值最小的边的另一顶点k1 ，并使k1加入U。即U={k0，k1}，同时将该边加入集合T（E）中。 重复（2），直到U=V为止。 这时T（E）中有n-1条边，T=（U，T（E））就是一一颗最小生成树。 模块分析 根据对模型的功能分析，该管道铺设设计可以具有以下功能： 网络光纤铺设信息的输入； 最小生成树信息的输出； 下面我们给出相应的功能模块图： 抽象数据类型分析 areanum 居民区总数（顶点总数）； edgenum 边的总数； date[ ][20] 邻接矩阵存储图结构； s 边的权值； short-way[i] 居民区i到目前生成树中所有点集U中某个居民区的路程最小值 near-area[i] U中能使其最小的居民区 4．功能分析 假设居民区分布和各居民区之间的距离如下图显示 则通过网络光纤铺设的最佳方案选择后结果如下面显示 程序开始 信息输入 输出结果 流程图和算法设计 详细算法分析 信息输入模块 //输入顶点个数和边的条数 cout请输入居民区个数：; cinareanum; coutendl; cout请输入网络光纤铺设路线的总条数：; cinedgenum; //初始化矩阵各元素值 int i,j,k; for(i=0；iareanum;i++) for(j=0;jareanum;j++) date[i][j]=INFINITY; //读入边 int from,to,s; cout请按此格式输入边和权值：i, j, k（ 表示 i 居民区到 j 居民区的距离为 k 米） ; for(i = 0; i edgenum; i++) { cinfromtom; date[from][to] = s; date[to][from] = st; } //输出邻接矩阵 for(i = 0; i areanum; i++) { for(j = 0; j areanum; j++) { coutdate[i][j]\t; } coutendl; } ②建立最小生成树并输出结果 void prim(int date[][MAXNODE],int areanum,int near_area[]) { //辅助数组short_way,near_area //short_way[i]表示居民区i到到目前生成树中所有点集U中某个居民区（点）的路程最小值 //near_city[i]表示U中能使其最小的居民区(点) int short_way [areanum]; int min; int i,j,k; //0已经放入U中 //初始化short_way 和 near_area for(i = 1; i areanum; i++) { short_way[i] = date[0][i]; near_area[i] = 0; } short_way[i]=0; near_area[0] = 0; for(i = 1; i areanum; i++) //有n-1条边要加入生成树,所以只要循环n-1次即可 { min =INFINITY; // 求生成树外顶点到生成树内顶点具有最小权值的边 j=1;k=1; while(jareanum) //确定当前具有最小权值的边及位置 { if(short_way[j]!=0 short_way[j] min)