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

N(N10)个居民之间需要铺设煤气管道。假设任意两个居民之间都可以铺设煤气管道，但代价不同。事先将任意两个居民之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民之间铺设煤气管道所需代价最少，并希望以图形方式在屏幕上输出结果。二、需求分析在N（N10）个居民区之间铺设煤气管道所需代价最小，即求最小生成树问题。在我们的课本中介绍了两种求解方法：普利姆算法和克鲁斯卡尔算法。普利姆算法与网的变数无关，适宜求解边稠密的网的最小生成树。而克鲁斯卡尔算法正好相反，适宜求解边稀疏的最小生成树。由于在实际问题中，居民数量一般很有限，而任何两个居民区都可能有连线，即这样的图应该是边较为稠密的。因此，我们选择了普利姆算法对问题进行求解。三、总体设计普利姆算法的思想是：从连通网N={V,E}中的某一顶点U0出发，选择与它关联的具有最小权值的边(U0,v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。如此继续下去，直到网中的所有顶点都加入到生成树顶点集合U中为止。根据对模型的功能分析，该管道铺设设计应有以下模块：1、管道铺设信息的输入2、最小生成树信息的输出功能模块图：管道铺设问题最小生成树问题信息输入模块建立最小生成树并输出四、详细设计1、类定义：classedgeset//定义一条生成树的边边{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(graph&g){inti,j,k;cout请输入n居民点信息:;for(k=1;k=n;k++){cing.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代表无穷coutendl;for(k=1;k=e;k++)//输入一条边（i,j）的代价w{cout请输入一条管道及管道上的代价:;cinijw;g.a[i][j]=w;g.a[j][i]=w;}}voidgraph::print(graphg){for(inti=1;i=n;i++){for(intj=1;j=n;j++){couti到j代价为:g.a[i][j]endl;}coutendl;}}voidgraph::dfs(graphg,inti){intj;coutg.v[i];visited[i]=true;//标记表示已被访问过for(j=1;j=n;j++)if((g.a[i][j]!=9999)&&(g.a[i][j]!=0)&&(!visited[j]))dfs(g,j);}voidgraph::prim(graph&g){inti,j,k,min,g1,m,w;for(i=1;in;i++)//从顶点1出发求最小生成树的边{g.ct[i].fromvex=1;g.ct[i].endvex=i+1;g.ct[i].weight=g.a[1][i+1];}for(k=2;k=n;k++){min=9999;m=k-1;for(j=k-1;jn;j++)//找权值最小的树边if(g.ct[j].weightmin){min=g.ct[j].weight;m=j;}edgesettemp=g.ct[k-1];g.ct[k-1]=g.ct[m];g.ct[m]=temp;j=g.ct[k-1].endvex;for(i=k;in;i++){g1=g.ct[i].endvex;w=g.a[j][g1];if(wg.ct[i].weight){g.ct[i].weight=w;g.ct[i].fromvex=j;}}}}3、主函数mainvoidmain(){inti,j,m;graphg;cout****************输入信息********************************endl;g.create(g);//建立网的邻接矩阵cout****************输出信息********************************endl;g.print(g);cout***************普利姆算法求最小生成树*********************************endl;g.prim(g);//用普利姆算法求最小生成树for(i=1;in;i++){coutg.ct[i].fromvex;coutg.ct[i].endvex;coutg.ct[i].weightendl;}cout*************深度优先遍历***********************************endl;cout输入开始访问的居民点：;cinm;coutendl;cout已访问居民点:;g.dfs(g,m);coutendl;}五、程序调过程六、程序测试PrintPrimDfsMainCreate六、总结通过数据结构的课程设计使我们对所学的知识有了更好的理解，也增强了大家的动手能力。同时也发现了自己的很多不足之处，对知识的应用能力很是欠缺，应用软件的能力及编程水平与课程要求更是存在很大的差距。程序的运行结果与理论推导结果吻合，即该算法与程序设计满足课程设计要求。该程序的主要优点是简单易懂，不存在理解上的障碍，也很自然地想到这种解法。主要缺点是程序的变动性比较差，类中没有私有成员，都以公有定义！