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...