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

1）内容:
需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道即可。假设任意两个小区之间都可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同.选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。
2)要求：
在可能假设的m条管道中，选取n—1条管道，使得既能连通n个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。
3) 测试数据：
使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案.右侧是给出的参考解.
4）输入输出：
参考
代码：
#include ”iostream"
#include "stdlib。h"
#define MAX_VERTEX_NUM 20
typedef 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*)mallocsizeof（ArcNode））；
q—〉adjvex = i；
q—>weight = p->weight;
q—>nextarc = G。vertices[j］.firstarc；
G。vertices[j]。firstarc = q;
｝
}
｝
int MinEdge（WeightType lowcost[］， int vexmun)
｛
int i, k;
WeightType j;
k = 0；
while (lowcost[k]==0）
｛
k++；
}
j = lowcost[k];
for （ i = k+1； i < vexmun； i++)
{
if （lowcost[i]!=0＆&lowcost［i］ < j)
｛
j=lowcost［i];
k = i;
｝
｝
return k；
｝
void Prim(ALGraph G, int v0， int adjvex［])
{
WeightType lowcost[MAX_VERTEX_NUM];
int i, k；
ArcNode *p;
for ( i = 0； i 〈 G.vexnum; i++）
｛
if （i!=v0)
｛
lowcost[i］ = 999;
adjvex［i］ = v0；
}
}
p = G.vertices[v0］。firstarc;
while （p）
{
lowcost[G, p-〉adjvex] = p—〉weight;
p = p—>nextarc；
}
lowcost［v0］ = 0;
for ( i = 0; i 〈 G。vexnum； i++）
｛
k = MinEdge(lowcost， G。vexnum)；
if （k >= G.vexnum）
return；
std：：cout 〈< ”(" <〈 k <〈 ”，” 〈< adjvex［k] << "),” <〈 lowcost［k］<〈’\n’；
lowcost［k］ = 0；
p = G。vertices［k］.firstarc；
while （p)
｛
if （p->weightadjvex] = k；
lowcost[p—>adjvex］ = p-〉weight;
｝
p = p->nextarc；
｝
｝
｝
int main（）
｛
int adjvex[MAX_VERTEX_NUM]；
ALGraph G;
G。kind = 2;
CreateGraph（G)；
Prim(G, 0， adjvex）;
return 0；
｝
/*测试数据
9 15 2
A
B
C
D
E
F
G
H
I
A B 32。8
A I 18。2
A H 12。1
A C 44。6
B C 5。9
C D 21.3
C E 41。1
C G 56.4
D E 67。3
D F 98.7
E F 85.6
E G 10.5
H G 52.5
I H 8。7
I F 79.2
*/