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

1）内容: 需要在某个城市 n 个居民小区之间铺设煤气管道，则在这 n 个居民小区之间只需要铺设 n-1 条管道即可。假设任意两个小区之间都可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同.选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。 2)要求： 在可能假设的 m 条管道中，选取 n—1 条管道，使得既能连通 n 个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采纳邻接表的结构。 3) 测试数据： 使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案.右侧是给出的参考解. 4）输入输出： 参考完整代码：#include ”iostream"#include "stdlib。h"#define MAX_VERTEX_NUM 20typedef float WeightType；typedef struct ArcNode{int adjvex；WeightType weight;struct ArcNode *nextarc；｝ArcNode；typedef struct VertexNode{char data;ArcNode *firstarc；}VertexNode，AdjList［MAX_VERTEX_NUM]；typedef struct {AdjList vertices;int vexnum， arcnum；int kind；}ALGraph;int LocateVex（ALGraph G, char v）｛int i；for （i = 0； i < G。vexnum; i++）｛if （G.vertices［i］.data == v）return i；｝return -1;}void CreateGraph(ALGraph ＆G）{int i， j， k;char vi, vj；WeightType weight；ArcNode ＊p，＊q;std：：cout <〈 "请输入顶点个数，边数和图的类型：\n";std：:cin >> G.vexnum 〉〉 G.arcnum 〉> G.kind；for （ i = 0； i 〈 G。vexnum； i++）{std:：cout <〈 ”请输入各个顶点:\n”；std：：cin 〉〉 G.vertices[i]。data；G。vertices[i］。firstarc = NULL；｝for ( k = 0; k < G。arcnum； k++）｛std：:cout 〈〈 "请输入两顶点和其边的权值：\n"；std:：cin 〉> 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。vertices[i].firstarc；G。vertices[i]。firstarc = p;if （G。kind == 2){q = (ArcNode*)malloc(sizeof（ArcNode））；q—〉adjvex = i；q—>weight = p->weight;q—>nextarc = G。vertices[j］.firstarc；G。vertices[j]。firstarc = q;｝}｝int MinEdge（Weig...