管道铺设施工的最佳方案-----------完整程序代码

1、1）内容： 需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道即可。假设任意两个小区之间都可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。 2）要求： 在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。 3) 测试数据: 使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。右侧是给出的参考解。 4）输入输出: 参考完整代码：#include iostream#include s

2、tdlib.h#define MAX_VERTEX_NUM 20typedef float WeightType;typedef struct ArcNodeint adjvex;WeightType weight;struct ArcNode *nextarc;ArcNode;typedef struct VertexNodechar data;ArcNode *firstarc;VertexNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices;int vexnum, arcnum;int kind;ALGraph;int Lo

3、cateVex(ALGraph G, char v)int i;for (i = 0; i G.vexnum; i+)if (G.verticesi.data = v)return i;return -1;void CreateGraph(ALGraph &G)int i, j, k;char vi, vj;WeightType weight;ArcNode *p,*q;std:cout G.vexnum G.arcnum G.kind;for ( i = 0; i G.vexnum; i+)std:cout G.verticesi.data;G.verticesi.firstarc = NU

4、LL;for ( k = 0; k G.arcnum; k+)std:cout vi vj weight;i = LocateVex(G, vi);j = LocateVex(G, vj);p = (ArcNode *)malloc(sizeof(ArcNode);p-adjvex = j;p-weight = weight;p-nextarc = G.verticesi.firstarc;G.verticesi.firstarc = p;if (G.kind = 2)q = (ArcNode*)malloc(sizeof(ArcNode);q-adjvex = i;q-weight = p-

5、weight;q-nextarc = G.verticesj.firstarc;G.verticesj.firstarc = q;int MinEdge(WeightType lowcost, int vexmun)int i, k;WeightType j;k = 0;while (lowcostk=0)k+;j = lowcostk;for ( i = k+1; i vexmun; i+)if (lowcosti!=0&lowcosti j)j=lowcosti;k = i;return k;void Prim(ALGraph G, int v0, int adjvex)WeightTyp

6、e lowcostMAX_VERTEX_NUM;int i, k;ArcNode *p;for ( i = 0; i adjvex = p-weight;p = p-nextarc;lowcostv0 = 0;for ( i = 0; i = G.vexnum)return;std:cout ( k , adjvexk ), lowcostkweightadjvex)adjvexp-adjvex = k;lowcostp-adjvex = p-weight;p = p-nextarc;int main()int adjvexMAX_VERTEX_NUM;ALGraph G;G.kind = 2;CreateGraph(G);Prim(G, 0, adjvex);return 0;/*测试数据9 15 2ABCDEFGHIA B 32.8A I 18.2A H 1