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

N(N10)个居民之间需要铺设煤气管道。假设任意两个居民之间都可以铺设煤气管道，但代价不同。事先将任意两个居民之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民之间铺设煤气管道所需代价最少，并希望以图形方式在屏幕上输出结果。 二、需求分析 在N（N10）个居民区之间铺设煤气管道所需代价最小，即求最小生成树问题。在我们的课本中介绍了两种求解方法：普利姆算法和克鲁斯卡尔算法。普利姆算法与网的变数无关，适宜求解边稠密的网的最小生成树。而克鲁斯卡尔算法正好相反，适宜求解边稀疏的最小生成树。 由于在实际问题中，居民数量一般很有限，而任何两个居民区都可能有连线， 即这样的图应该是边较为稠密的。因此，我们选择了普利姆算法对问题进行求解。 三、总体设计 普利姆算法的思想是：从连通网N={V,E}中的某一顶点U0出发，选择与它关联的具有最小权值的边(U0,v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合U中。如此继续下去，直到网中的所有顶点都加入到生成树顶点集合U中为止。 根据对模型的功能分析，该管道铺设设计应有以下模块： 管道铺设信息的输入 最小生成树信息的输出 功能模块图： 四、详细设计 1、类定义： class edgeset //定义一条生成树的边边 { public: int fromvex; //边的起点 int endvex; //边的终点 int weight; //边的权值 }; class graph { public: int w; int v[n+1]; //存放顶点 int a[n+1][n+1]; //邻接矩阵 edgeset ct[n+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;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; else g.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; } } void graph::print(graph g) { for(int i=1;i=n;i++) { for(int j=1;j=n;j++) { couti到j代价为:g.a[i][j]endl; } coutendl; } } void graph::dfs(graph g,int i) { int j; 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); } void graph::prim(graph g) { int i,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; } edgeset temp=g.ct[k-1]; g.ct[k-1]=g.ct[m]; g.ct[m]=temp;