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

《数据结构管道铺设施工的最佳方案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、N(N>10)个居民之间需要铺设煤气管道。假设任意两个居民之间都可以铺设煤气管道，但代价不同。事先将任意两个居民之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民之间铺设煤气管道所需代价最少，并希望以图形方式在屏幕上输出结果。二、需求分析在N（N>10）个居民区之间铺设煤气管道所需代价最小，即求最小生成树问题。在我们的课本中介绍了两种求解方法：普利姆算法和克鲁斯卡尔算法。普利姆算法与网的变数无关，适宜求解边稠密的网的最小生成树。而克鲁斯卡尔算法正好相反，适宜求解边稀疏的最小生成树。由于在实际问题中，居民数量一般很有限，而任何两个居民区都可能有连线，即这样的图应该是边较为

2、稠密的。因此，我们选择了普利姆算法对问题进行求解。三、总体设计普利姆算法的思想是：从连通网N={V,E}中的某一顶点U0出发，选择与它关联的具有最小权值的边(U0,v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。如此继续下去，直到网中的所有顶点都加入到生成树顶点集合U中为止。根据对模型的功能分析，该管道铺设设计应有以下模块：1、管道铺设信息的输入2、最小生成树信息的输出管道铺设问题功能模块图：建立最小生成树并输出信息输入模块最小生成树问题四、详细设计1、类定义：classedgese

3、t//定义一条生成树的边边{public:intfromvex;//边的起点intendvex;//边的终点intweight;//边的权值};classgraph{public:intw;intv[n+1];//存放顶点inta[n+1][n+1];//邻接矩阵edgesetct[n+1];//最小生成树的边集voidcreate(graph&g);//建立邻接矩阵voidprint(graphg);//输出邻接矩阵voiddfs(graphg,inti);//深度优先遍历voidprim(graph&g);//普利姆算法};2、类的成员函数的实现voidgraph::create(g

4、raph&g){inti,j,k;cout<<"请输入"<>g.v[k];}//输入居民点信息for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(i==j)g.a[i][j]=0;elseg.a[i][j]=9999;//9999代表无穷cout<>i>>j>>w;g.a[i][j]=w;g.a[j][i]=w;}}voidgraph::print(graphg)

5、{for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){cout<

6、w;for(i=1;i

7、g1=g.ct[i].endvex;w=g.a[j][g1];if(w