数据结构管道铺设施工的最佳方案.doc

N(N10)个居民之间需要铺设煤气管道。假设任意两个居民之间都可以铺设煤气管道，但代价不同。事先将任意两个居民之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民之间铺设煤气管道所需代价最少，并希望以图形方式在屏幕上输出结果。二、需求分析在N（N10）个居民区之间铺设煤气管道所需代价最小，即求最小生成树问题。在我们的课本中介绍了两种求解方法：普利姆算法和克鲁斯卡尔算法。普利姆算法与网的变数无关，适宜求解边稠密的网的最小生成树。而克鲁斯卡尔算法正好相反，适宜求解边稀疏的最小生成树。由于在实际问题中，居民数量一般很有限，而任何两个居民区都可能有连线，即这样的图应该是边较为稠密的。因此，我们选择了普利姆算法对问题进行求解。三、总体设计普利姆算法的思想是：从连通网N=V,E中的某一顶点U0出发，选择与它关联的具有最小权值的边(U0,v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。如此继续下去，直到网中的所有顶点都加入到生成树顶点集合U中为止。根据对模型的功能分析，该管道铺设设计应有以下模块：1、 管道铺设信息的输入2、 最小生成树信息的输出管道铺设问题功能模块图：建立最小生成树并输出信息输入模块最小生成树问题 四、详细设计 1、类定义：class edgeset /定义一条生成树的边边public:int fromvex; /边的起点int endvex; /边的终点int weight; /边的权值;class graphpublic:int w;int vn+1; /存放顶点int an+1n+1; /邻接矩阵edgeset ctn+1; /最小生成树的边集 void create(graph &g);/建立邻接矩阵void print(graph g); /输出邻接矩阵void dfs(graph g,int i); /深度优先遍历void prim(graph &g); /普利姆算法;2、类的成员函数的实现void graph:create(graph &g)int i,j,k; cout请输入n居民点信息:; for(k=1;kg.vk; /输入居民点信息for(i=1;i=n;i+)for(j=1;j=n;j+) if(i=j)g.aij=0; else g.aij=9999; /9999代表无穷 coutendl;for(k=1;k=e;k+) /输入一条边（i,j）的代价wcoutijw;g.aij=w;g.aji=w;void graph:print(graph g)for(int i=1;i=n;i+)for(int j=1;j=n;j+)couti到j代价为:g.aijendl; coutendl;void graph:dfs(graph g,int i)int j;coutg.vi ;visitedi=true; /标记表示已被访问过for(j=1;j=n;j+)if(g.aij!=9999)&(g.aij!=0)&(!visitedj)dfs(g,j);void graph:prim(graph &g)int i,j,k,min,g1,m,w;for(i=1;in;i+) /从顶点1出发求最小生成树的边g.cti.fromvex=1;g.cti.endvex=i+1;g.cti.weight=g.a1i+1;for(k=2;k=n;k+)min=9999;m=k-1;for(j=k-1;jn;j+) /找权值最小的树边if(g.ctj.weightmin)min=g.ctj.weight;m=j;edgeset temp=g.ctk-1;g.ctk-1=g.ctm;g.ctm=temp;j=g.ctk-1.endvex;for(i=k;in;i+)g1=g.cti.endvex;w=g.ajg1;if(wg.cti.weight)g.cti.weight=w;g.cti.fromvex=j;3、主函数mainvoid main()int i,j,m;graph g;cout*输入信息*endl; g.create(g); /建立网的邻接矩阵cout*输出信息*endl; g.print(g);cout*普利姆算法求最小生成树*endl;g.prim(g);/用普利姆算法求最小生成树for(i=1;in;i+)coutg.cti.fromvex ;coutg.cti.endvex ;coutg.cti.weightendl; cout*深度优先遍历*endl;coutm;coutendl;cout已访问居民点:; g.dfs(g,m); coutendl;五、程序调过程CreateMainPrintPrimDfs六、程序测试六、总结通过数据结构的课程设计使我们对所学的知识有了更好的理解，也增强了大家的动手能力。同时也发现了自己的很多不足之处，对知识的应用能力很是欠缺，应用软件的能力及编程水平与课程要求更