实验三：管道铺设施工的最佳方案

实验三：管道铺设施工的最佳方案

一.问题描述

1.实验题目：

需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1

条管道铺设n-1条管道即可。假设任意两个小区之间则可以铺设管道，但由于地理环境不同，

所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的

最小生成树。

2.基本要求：

在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。

每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。

3.测试数据：

使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。

98.7

参考解:

二.需求分析

1.程序所能达到的基本可能：

在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管

道铺设n-1条管道即可。假设任意两个小区之间则可以铺设管道，但由于地理环境不同，所

需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，在可能假设的m条管道中，

选取n-1条管道，使得既能连通n个小区，又能使总投资最小。

2.输入输出形式及输入值范围：程序运行后，显示提示信息：请输入顶点数和边数（输入格

式为：顶点数，边数）之后程序从文件名为“C:\Vlata.txt读入顶点信息和边的信息，之后

显示提示信息输入开始节点，执行生成最小树程序，输出生成的最小树信息。

3.测试数据要求：顶点数边数为整数，顶点信息为大写字母，边的权值为浮点型，

C:\\data.txt文件内容为:ABCDEFGHI

1232.8235.91344.63421.34567.34698.75685.65710.53756.46

979.27852.51812.1898.71918.23541.1

三.概要设计

1.所用到得数据结构及其ADT

typedefstructnode〃边表结点

intNO;〃邻接点域;

vertexTypeadjvex;

EdgeTypeinfo;〃权值

structnode*next;〃指向下一个邻接点的指针域

}EdgeNode;

typedefstructvnode〃顶点表节点

(

vertexTypevertex;〃顶点域

EdgeNode*firstedge;〃编表头指针

}VertexNode;

typedefstruct〃邻接表

VertexNodeadjlist[MaxVertexNum];

intn,e;〃顶点数和边数

}ALGraph;//ALGraph是以邻接表方式存储的图类型

基本操作：ALGraph*CreateALGraphO〃建表

2.主程序流程及其模块调用关系

建表模块ALGraph*CreateALGraph()

最小生成树模块voidtree(ALGraph*G,intm)

函数调用关系图

四、详细设计

1.实现每个操作的伪码，重点语句加注释

1)建表模块

ALGraph*CreateALGraph()〃建表

!

inti,j,k;

floatm;

FILE*fp;

EdgeNode*s,*t;

ALGraph*G;

fp=fopenCC:\\data.txt",〃r");〃打开文件

if(fp=NULL)〃未找到文件

(

printf(，，Cann，topenthefile!\n");

exit(1);

)

G=(ALGraph*)malloc(sizeof(ALGraph));

printf(〃请输入顶点数和边数(输入格式为：顶点数，边数)\n〃)；

scanf(〃%d,%d〃,&G->n,&G->e);

for(i=l;i<=G->n;i++)〃建立顶点信息

(

G->adjlist[i].vertex=fgetc(fp);

G->adjlist[i].firstedge=NULL;

visited[i]=i;

}

for(k=l;k<=G->e;k++)

(

//printf(〃请输入第%d条边的两个端点序号，输入格式为：i,八n〃,k);

//scanf(〃％d,%d〃,&i,&j);

fscanf(fp,〃％d〃，&i);

fscanf(fp,"%d",&j);

s=(EdgeNode*)malloc(sizeof(EdgeNode));

t=(EdgeNode*)malloc(sizeof(EdgeNode));

//printf(〃请输入第加条边的对应权值\n〃,k);

fscanf;〃保存边信息，以无向网方式

s->NO=j;

s->adjvex=G->adj1ist[j].vertex;

s->info=m;

s->next=G->adjlist[i].firstedge;

G->adjlist[i].firstedge=s;

t->N0=i;

t->adjvex=G->adjlist[i].vertex;

t->info=m;

t->next=G->adjlist[j].firstedge;

G->adjlist[j].firstedge=t;

)

fclose(fp);〃关闭文件

returnG;

)

2)生成最小生成树模块

voidtree(ALGraph*G,intm)

I

floatlow[100];intteed[100];

intk,i,j;

floatmin,sum=0;

EdgeNode*s;

low[m]=0;

visited[m]=0;

for(i=l;i<=G->n;i++)

(

low[i]=1000;

teed[i]=m;

}

s=G->adjlist[m].firstedge;

while(s!=NULL)〃数组初始化

(

low[s->N0]=s->info;

s=s->next;

)

for(i=l;i<G->n;i++)

min=1000;

for(j=l;j<=G->n;j++)

if(visited[j]>0&&low[jkmin)〃找到最小权值

min=low[j];

k=j;〃标记节点

)

}

sum+=min;

visited[k]=O;

s=G->adjlist[k].firstedge;

while(s!=NULL)

(

if(visited[s->N0]>0&&s->info〈low[s->N0])〃找到最小权值

(

low[s->NO]=s->info;

teed[s->N0]=k;

)

s=s->next;

)

}

printf(〃最佳铺设方案\n〃)；

for(i=l;i<=G->n;i++)〃输出最小生成树信息

if(i!=m)

printfC，(%d,%d)%.2f\t，z,i,teed[i],low[i]);

printf(〃最小权值为:％.2f\n〃，sum);

)

3)主函数模块

voidmain()

!

ALGraph*G;

inti;

timetrawtime;

structtm*timeinfo;

time(&rawtime);

timeinfo=localtime(ftrawtime);

printfC实验名称：实验三：管道铺设施工的最佳方案\n");

printf(，z学号：031350102\nz，);

printfC姓名：王亚文\n〃)；

printf；

printf(〃程序运行开始，〃)；

printf(，zCurrentlocaltimeanddate:%sz\asctime(timeinfo));

G=CreateALGraph();〃建表

printf(〃输入开始节点\n〃);

scanf("%d",&i);

tree(G,i);〃生成最小树

//printfALGraph(G);

printf(〃\n〃)；

printf("'Currentlocaltimeanddate^s^,asctime(timeinfo));

)

五、调试分析

1.设计与调试过程中遇到的问题分析、体会

1)一开始对文件读写操作不熟，采用从键盘输出的方式验证正确与否，对应程序如下:

inti,j,k;

floatm;

EdgeNode*s,*t;

ALGraph*G;

G=(ALGraph*)malloc(sizeof(ALGraph));

printf(〃请输入顶点数和边数(输入格式为：顶点数，边数)\n〃)；

scanf("%d,%d〃，&G->n,&G->e);

for(i=l;i<=G->n;i++)〃建立顶点信息

G->adjlist[i].vertex=fgetc(fp);

G->adjlist[i].firstedge=NULL;

visited[i]=i;

i

for(k=l;k<=G->e;k++)

(

printf(〃请输入第%d条边的两个端点序号，输入格式为：i,j\n〃,k);

scanf(〃％d,%d〃,&i,&j);

s=(EdgeNode*)malloc(sizeof(EdgeNode));

t=(EdgeNode*)malloc(sizeof(EdgeNode));

printf(〃请输入第%d条边的对应权值\n〃,k);

scanfr%fzz,&m);〃保存边信息，以无向网方式

s->N0=j;

s->adjvex=G->adjlist[j].vertex;

s->inform;

s->next=G->adjlist[i].firstedge;

G->adjlist[i].firstedge=s;

t->N0=i;

t->adjvex=G->adjlist[i].vertex;

t->info=m;

t->next=G->adjlist[j].firstedge;

G->adjlist[j].firstedge=t;

}

returnG;

对应截屏如下：发现这种方式输入耗时长，而且在生成树程序不正确时修改程序需要重复输

入，较为麻烦

-

睛输入第7条边的对应权值

85.6

请输入第8条边的两个端点序号，输入格式为：

5,7

请输入第8条边的对应权值

10.5

请输入第9条边的两个端点序号，输入格式为：

37

宿输入第9条边的对应权值

56.4

请输入第［。条边的两个端点序号，输入格式为：

德输入第条边的对应权值

79.2

请输入第11条边的两个端点序号,输入格式为：

78

港输入第11条边的对应权值

52.5

请输入第12条边的两个端点序号,输入格式为：

1,8

请输入第12条边的对应权值

12.1

请输入第13条边的两个端点序号,输入格式为：i，j

褊｝入第13条边的对应权值

8.?

请输入第14条边的两个端点序号,输入格式为：i，J

善徐入第14条边的时应权值

182

请输入第15条边的两个端点序号,输入格式为：i，j

3,5

请输入第15条边的对应权值

41.1

输入开始节点

1

<2,1>32.80<3,2>5.90<4,3>21.30<5,3>41.10<6,9>79.20

<7,5>10.50<8,1>12.10<9,8>8.70输出信息

A的邻接点及权值;

h18.20H12.10C44.60B32.80

B的邻接点及权值:

5.90A32.80

的邻接点及权值B!:

C的邻接点及权值：

E41.10G56.40D21.30A44.60B5.90

D的邻接点及权值：

F98.70E67.30C21.30

E的邻接点及权值：

C41.10G10.50F85.60D67.30

F的邻接点及权值：

I79.20E85.60D98.70

G的邻接点及权值：

H52.50C56.4010.50

H的邻接点及权值：

I8.70A12.10G52.50

I的邻接点及权值：

h18.20H8.7079.20

pressanykeytocontinue

2)为检验所建立的无向网，编写了一个输出函数，输出各个顶点以及与该顶点相邻的其他

顶点以及对应权值，输出函数为voidprintfALGraph(ALGraph*G)〃输出表

inti;

EdgeNode*s;

printf("输出信息\n");

for(i=l;i<=G->n;i++)

(

printf(z，%c的邻接点及权值:\n〃,G->adjlist[i].vertex);

s=G->adjlist[i].firstedge;

while(s!=NULL)

(

printf(，z%c%.2f”,s->adjvex,s->info);

s=s->next;

)

printf(〃\n〃)；

}

输出测试截屏如下证明从文件读写的与所需要建立的无向网相符

|l•C:\USERS\ADMINISTRATOR\DESKTOP\VC\Debug\sa.exe,--X

窈验名称：实验三：管道铺设施工的最佳方案

学号：031350102

姓名：王亚文

行呈序运彳丁开始，Currentlocaltimeanddate：ThuNou1215:29:122015

情输入顶点数和边数（输入格式为:顶点数，边数）

9,15

输入开始节点

1

<9,8>8.70<2,1>32.80<3,2>5.90<4,3>21.30<5,3>41.10

<6,9）79.20<7,5>10.50<8,1>12.10<9,8>8.70输出信息

A的邻接点及权值:

I18.20H12.1044.60B32.80

B的邻接点及权值：

C5.90A32.80

C的邻接点及权值：

E41.10G56.4021.30A44.60B5.90

D的邻接点及权值：

F98.70E67.3021.30

E的邻接点及权值：

C41.10G10.50F85.6067.30

F的邻接点及权值：

I79.20E85.60D98.70

G的邻接点及权值：

H52.5056.4010.50

H的邻接点及权值：

I8.?0A12.10

I的邻接点及权值：

A18.20H8.70F79.20

(Currentlocaltineanddate：ThuNou1215:29:122015

Pressanykeytocontinue

2.主要算法的时间复杂度分析

六、使用说明

程序运行后，显示提示信息：请输入顶点数和边数（输入格式为：顶点数，边数）之后程序

从文件名为"C:\\data.txt读入顶点信息和边的信息，之后显示提示信息输入开始节点，

执行生成最小树程序，输出生成的最小树信息。

七、测试结果

|D：回汉

■'C:\USERS\ADMINISTRATOR\DESKTOP\VC\Debug\sa.exe'

需验名称：实验三：管道铺设施工的最佳方案

学号：031350102

姓名：王亚文

程序达彳丁开始，Currentlocaltimeanddate：ThuNou1215：33：442015

请输入顶点数和边数（输入格式为：顶点数，边数）

输入开始节点

£佳铺设方案

<2,1>32.80<3,2>5.90<4,3>21.30<5,3>41.10<6,9>79.20

<7,5>10.50<8,1>12.10<9,8>8.?0最小权值为：211.60

Currentlocaltineanddate：ThuNou1215：33：442015

Pressanykeytocontinue

3）这个程序遇到的第一个主要问题是在建表过程，因为边的顶点信息是大写英文字母，一

开始我是用的ASCLL码值，使用不方便，后来采用在定义时考虑多定义一个量，原程序：

typedefstructnode〃边表结点

j

vertexTypeadjvex;〃邻接点域；

EdgeTypeinfo;〃权值

structnode*next;〃指向下一个邻接点的指针域

}EdgeNode;

修正后的程序为:

typedefstructnode〃边表结点

t,1

intNO;〃邻接点域；

vertexTypeadjvex;

EdgeTypeinfo;〃权值

structnode*next;〃指向下一个邻接点的指针域

}EdgeNode;

这样多定义了一个量在后面的过程中会简单许多，其次书上给的程序是生成有向网的，

开始我是考虑的将边输入两边，就是在循环时的终止条件设为k«2*G-〉6；这样虽然能解决

无向网问题，但是一条边重复输入两边，较为麻烦，后期修正为：

s->NO=j;

s->adjvex=G->adjlist[j].vertex;

s->info=m;

s->next=G->adjlist[i].firstedge;

G->adjlist[i].firstedge=s;

t->NO=i;

t->adjvex=G->adjlist[i].vertex;

t->info=m;

t->next=G->adjlist[j].firstedge;

G->adjlist[j].firstedge=t;

修正后的函数虽然语句较之前的多了5句但在输入时少输了一半的边信息。其次解决耗时最

长的一个错误是在建表中，原程序：

typedefVertexNodeAdjlist[MaxVertexNum];

typedefstruct〃邻接表

{

Adjlistadjlist;

//intn,e;〃顶点数和边数

intn;

inte;

}ALGraph;//ALGraph是以邻接表方式存储的图类型

这个程序是抄的书上的，一开始不觉得书上的程序会是错的，结果一直没有看这个定义，在

输入边的信息时循环次数总是不对，一直尝试着改动写的输入信息，弄了一下午也没有搞定

这个问题，于是去求助研究生学长，下面是研究生学长发过来的邮件帮我指出错误所在，看

了学长的这封邮件后，重新改了一下自己的程序，修正后的程序为

typedefstruct〃邻接表

!

VertexNodeadjlist[MaxVertexNum];

intn,e;〃顶点数和边数

}ALGraph;//ALGraph是以邻接表方式存储的图类型

问题所在:结构体ALGraph(红色标记部分)中，"Adjlistadjlistf语句定义错误，上

面没有定义Adjlist这个类型；|

解决方案：考虑在主函数main()中将全局结构体数组typedefVertexNode

AdjlistfMaxVertexNum];中Adjlist数组名作为参数进入ALGraph*

CreateALGraph()

即ALGraph*CreateALGraph(VertexNode*adjlist);

将的访问方式更改为原因:该结构体数组定义为全局结构体

G->adjliSt[i].xadjlist[i].x,

数组无须通过ALGraph结构体指针G来访同使用数组指针VertexNode*adjlist方便

快捷

程序修正后输入正常了，就开始进入下一个阶段生成最小树的程序。

3)在生成最小树这个程序的编写中，开始因为编程序是在老师讲解生成树之前，所以一开

始是完全没有地方下手，网上百度了一下如何生成最小树，发现有两种方法,Kruskal和prim

算法，但研究生学长这个适合用prim算法，Kruskal算法适合与边稀疏的连通图求解最小

生成树，所以在编写时主要研究的是用prim算法，在编写prim算法时除了很多问题，例如

一开始我并没有在循环中写teed[i]=m;这句话，导致在最后输出边的信息时会有随机数产

生，截图如下：

最佳铺设方案

(2,-858993460>32.80<3,2>5.90<4,3>21.30<5,3>41.10<6,9>79.

20<8,-858993460>12.10<9,8>8,70最小权值为

想到随机数产生可能是因为没有赋值，所以加上teed[i]=m;这句话果然最后就输出正确了，

再次在输出时，产生的结果中有重复的一个节点，<1,D1000.00这个不应该被输出，所以

考虑在输出时加一个限制条件if(i!=m)再次输出就没有了，

最佳铺设方案

<1,1>1000.00<2,1>32.80<3,2>5.90<4,3>21.30<5,3>41.10

<6,9>79.20<7,5>10.50<8,1>12.10<9,8>8.70最小权值为

0

中间编写时问题不大，之前有看过prim算法的详细介绍，所以在主思路上没有太大的错误,

相对写起来也比较顺利。

2)建立邻接表的复杂度为0(n+e);

Prim算法的时间复杂度为O(elogn);

八、附录

#include<stdio.h>

#include<malloc.h>

#include<stdlib.h>

#include<time.h>

〃输入序号与字母对应关系AT,,B-2,C-3,D-4,E-5,F-6,G-7,H-8,1-9

#defineMaxVertexNum100

typedefcharvertexType;

typedeffloatEdgeType;

intvisited[100];〃访问变量,为一时表示未访问

typedefstructnode〃边表结点

f

intNO;〃邻接点域；

vertexTypeadjvex;

EdgeTypeinfo;〃权值

structnode*next;〃指向下一个邻接点的指针域

}EdgeNode;

typedefstructvnode〃顶点表节点

if

vertexTypevertex;〃顶点域

EdgeNode*firstedge;〃编表头指针

}VertexNode;

typedefstruct〃邻接表

VertexNodeadjlist[MaxVertexNum];

intn,e;〃顶点数和边数

}ALGraph;//ALGraph是以邻接表方式存储的图类型

ALGraph*CreateALGraph()〃建表

inti,j,k;

floatm;

FILE*fp;

EdgeNode*s,*t;

ALGraph*G;

fp=fopenCC:\\data.txt","r");〃打开文件

if(fp=NULL)〃未找到文件

(

printf("Carin'topenthefile!\n〃)；

exit(1);

}

G=(ALGraph*)malloc(sizeof(ALGraph));

printf(〃请输入顶点数和边数(输入格式为：顶点数，边数)\n〃)；

scanf(〃%d,%d”,&G->n,&G->e);

for(i=l;i<=G->n;i++)〃建立顶点信息

(

G->adjlist[i].vertex=fgetc(fp);

G->adjlist[i].firstedge=NULL;

visited[i]=i;

1

for(k=l;k<=G->e;k++)

(

//printf(〃请输入第%(1条边的两个端点序号，输入格式为：i,j\n〃,k);

//scanfC%d,%d",&i,&j);

fscanf(fp,〃%d〃，&i);

fscanf(fp,〃％d〃，&j);

s=(EdgeNode*)malloc(sizeof(EdgeNode));

t=(EdgeNode*)malloc(sizeof(EdgeNode));

//printf(〃请输入第%d条边的对应权值\n〃,k);

fscanf(fp,〃%f”,&m);〃保存边信息，以无向网方式

s->NO=j;

s->adjvex=G->adjlist[j].vertex;

s->info=m;

s->next=G->adjlist[i].firstedge;

G->adjlist[i].firstedge=s;

t->NO=i;

t->adjvex=G->adjlist[i].vertex;

t->info=m;

t->next=G->adjlist[j].firstedge;

G->adjlist[j].firstedge=t;

)

fclose(fp);〃关闭文件

returnG;

)

voidtree(ALGraph*G,intm)

!

floatlow[100];intteed[100];

intk,i,j；

floatmin,sum=0;

EdgeNode*s;

low[m]=0;

visited[m]=0;

for(i=l;i<=G->n;i++)

low[i]=1000;

teed[i]=m;

}

s=G->adjlist[m].firstedge;

while(s!=NULL)〃数组初始化

low[s->NO]=s->info;

s=s->next;

}

for(i=l;i<G->n;i++)

(

min=1000;

for(j=l;j<=G->n;j++)

(

if(visit6d[j]〉0&&low[j]〈min)〃找到最小权值

(

min=low[j];

k=j;〃标记节点

)

}

sum+二min;

visited[k]=O;

s=G->adjlist[kJ.firstedge;

while(s!=NULL)

(

if(visited[s->N0]>0&&s->info<low[s->N0])〃找到最小权值

(

low[s->NO]=s->info;

teed[s->N0]zzk;

}

s=s->next;

)

)

printf（〃最佳铺设方案\n〃）;

for(i=l;i〈=G->n;i++)〃输出最小生成树信息

if(i!=m)

printf(〃(%d,%d)%.2f\t，z,i,teed[i],low[i]);

printf(〃最小权值为:%.2f\n〃，sum);

)

AvoidprintfALGraph(ALGraph*G)〃输出表

{

inti;

EdgeNode*s;

printf(〃输出信息信");

for(i=l;i<=G->n;i++)

(

printfCz%c的邻接点及权值：\n”,G->adjlist[i].vertex);

s=G->adjlist[i].firstedge;

while(s!=NULL)

(

printf(z，%c%.2f:s->adjvex,s->in