管道铺设问题.docx

管道铺设问题.docx

《管道铺设问题.docx》由会员分享，可在线阅读，更多相关《管道铺设问题.docx（26页珍藏版）》请在冰点文库上搜索。

管道铺设问题

实验三：

管道铺设施工的最佳方案

一．问题描述

1.实验题目：

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

假设任意两个小区之间则可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。

选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。

2.基本要求：

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

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

3.测试数据：

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

参考解：

二．需求分析

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

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

假设任意两个小区之间则可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。

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

2.输入输出形式及输入值范围：

程序运行后，显示提示信息：

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

顶点数,边数）之后程序从文件名为”C:

\\data.txt读入顶点信息和边的信息，之后显示提示信息输入开始节点，执行生成最小树程序，输出生成的最小树信息。

3.测试数据要求：

顶点数边数为整数，顶点信息为大写字母，边的权值为浮点型，C:

\\data.txt文件内容为：

ABCDEFGHI

1232.8235.91344.63421.34567.34698.75685.65710.53756.46979.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*CreateALGraph（）//建表

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

1）主程序模块

建表模块ALGraph*CreateALGraph（）

最小生成树模块voidtree（ALGraph*G,intm）

函数调用关系图

四、详细设计

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

1）建表模块

ALGraph*CreateALGraph（）//建表

{

inti,j,k;

floatm;

FILE*fp;

EdgeNode*s,*t;

ALGraph*G;

fp=fopen（"C:

\\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=1;i<=G->n;i++）//建立顶点信息

{

G->adjlist[i].vertex=fgetc（fp）;

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

visited[i]=i;

}

for（k=1;k<=G->e;k++）

{

//printf（"请输入第%d条边的两个端点序号，输入格式为：

i,j\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（"请输入第%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;

}

2）生成最小生成树模块

voidtree（ALGraph*G,intm）

{

floatlow[100];intteed[100];

intk,i,j;

floatmin,sum=0;

EdgeNode*s;

low[m]=0;

visited[m]=0;

for（i=1;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=1;in;i++）

{

min=1000;

for（j=1;j<=G->n;j++）

{

if（visited[j]>0&&low[j]

{

min=low[j];

k=j;//标记节点

}

}

sum+=min;

visited[k]=0;

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

while（s!

=NULL）

{

if（visited[s->NO]>0&&s->infoNO]）//找到最小权值

{

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

teed[s->NO]=k;

}

s=s->next;

}

}

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

for（i=1;i<=G->n;i++）//输出最小生成树信息

if（i!

=m）

printf（"（%d,%d）%.2f\t",i,teed[i],low[i]）;

printf（"最小权值为:

%.2f\n",sum）;

}

3）主函数模块

voidmain（）

{

ALGraph*G;

inti;

time_trawtime;

structtm*timeinfo;

time（&rawtime）;

timeinfo=localtime（&rawtime）;

printf（"实验名称：

实验三：

管道铺设施工的最佳方案\n"）;

printf（"学号：

031350102\n"）;

printf（"姓名：

王亚文\n"）;

printf（"=============================================\n"）;

printf（"程序运行开始，"）;

printf（"Currentlocaltimeanddate:

%s",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=1;i<=G->n;i++）//建立顶点信息

{

G->adjlist[i].vertex=fgetc（fp）;

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

visited[i]=i;

}

for（k=1;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）;

scanf（"%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;

}

returnG;

}

对应截屏如下：

发现这种方式输入耗时长，而且在生成树程序不正确时修改程序需要重复输入，较为麻烦

2）为检验所建立的无向网，编写了一个输出函数，输出各个顶点以及与该顶点相邻的其他顶点以及对应权值，输出函数为voidprintfALGraph（ALGraph*G）//输出表

{

inti;

EdgeNode*s;

printf（"输出信息\n"）;

for（i=1;i<=G->n;i++）

{

printf（"%c的邻接点及权值:

\n",G->adjlist[i].vertex）;

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

while（s!

=NULL）

{

printf（"%c%.2f",s->adjvex,s->info）;

s=s->next;

}

printf（"\n"）;

}

}

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

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

六、使用说明

程序运行后，显示提示信息：

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

顶点数,边数）之后程序从文件名为”C:

\\data.txt读入顶点信息和边的信息，之后显示提示信息输入开始节点，执行生成最小树程序，输出生成的最小树信息。

七、测试结果

3）这个程序遇到的第一个主要问题是在建表过程，因为边的顶点信息是大写英文字母，一开始我是用的ASCLL码值，使用不方便，后来采用在定义时考虑多定义一个量，原程序：

typedefstructnode//边表结点

{

vertexTypeadjvex;//邻接点域;

EdgeTypeinfo;//权值

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

}EdgeNode;

修正后的程序为：

typedefstructnode//边表结点

{

intNO;//邻接点域;

vertexTypeadjvex;

EdgeTypeinfo;//权值

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

}EdgeNode;

这样多定义了一个量在后面的过程中会简单许多，其次书上给的程序是生成有向网的，一开始我是考虑的将边输入两边，就是在循环时的终止条件设为k<=2*G->e；这样虽然能解决无向网问题，但是一条边重复输入两边，较为麻烦，后期修正为：

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是以邻接表方式存储的图类型

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

3）在生成最小树这个程序的编写中，开始因为编程序是在老师讲解生成树之前，所以一开始是完全没有地方下手，网上XX了一下如何生成最小树，发现有两种方法，Kruskal和prim算法，但研究生学长这个适合用prim算法，Kruskal算法适合与边稀疏的连通图求解最小生成树，所以在编写时主要研究的是用prim算法，在编写prim算法时除了很多问题，例如一开始我并没有在循环中写teed[i]=m;这句话，导致在最后输出边的信息时会有随机数产生，截图如下：

想到随机数产生可能是因为没有赋值，所以加上teed[i]=m;这句话果然最后就输出正确了，再次在输出时，产生的结果中有重复的一个节点，<1,1>1000.00这个不应该被输出，所以考虑在输出时加一个限制条件if（i!

=m）再次输出就没有了，

中间编写时问题不大，之前有看过prim算法的详细介绍，所以在主思路上没有太大的错误，相对写起来也比较顺利。

2）建立邻接表的复杂度为O（n+e）;

Prim算法的时间复杂度为O（elogn）;

八、附录

#include

#include

#include

#include

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

#defineMaxVertexNum100

typedefcharvertexType;

typedeffloatEdgeType;

intvisited[100];//访问变量，为一时表示未访问

typedefstructnode//边表结点

{

intNO;//邻接点域;

vertexTypeadjvex;

EdgeTypeinfo;//权值

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

}EdgeNode;

typedefstructvnode//顶点表节点

{

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=fopen（"C:

\\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=1;i<=G->n;i++）//建立顶点信息

{

G->adjlist[i].vertex=fgetc（fp）;

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

visited[i]=i;

}

for（k=1;k<=G->e;k++）

{

//printf（"请输入第%d条边的两个端点序号，输入格式为：

i,j\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（"请输入第%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=1;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=1;in;i++）

{

min=1000;

for（j=1;j<=G->n;j++）

{

if（visited[j]>0&&low[j]

{

min=low[j];

k=j;//标记节点

}

}

sum+=min;

visited[k]=0;

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

while（s!

=NULL）

{

if（visited[s->NO]>0&&s->infoNO]）//找到最小权值

{

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

teed[s->NO]=k;

}

s=s->next;

}

}

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

for（i=1;i<=G->n;i++）//输出最小生成树信息

if（i!

=m）

printf（"（%d,%d）%.2f\t",i,teed[i],low[i]）;

printf（"最小权值为:

%.2f\n",sum）;

}

/*voidprintfALGraph（ALGraph*G）//输出表

{

inti;

EdgeNode*s;

printf（"输出信息\n"）;

for（i=1;i<=G->n;i++）

{

printf（"%c的邻接点及权值:

\n",G->adjlist[i].vertex）;

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

while（s!

=NULL）

{

printf（"%c%.2f",s->adjvex,s->info）;

s=s->next;

}

printf（"\n"）;

}

}

*/

voidmain（）

{

ALGraph*G;

inti;

time_trawtime;

structtm*timeinfo;

time（&rawtime）;

timeinfo=localtime（&rawtime）;

printf（"实验名称：

实验三：

管道铺设施工的最佳方案\n"）;

prin