管道铺设施工的最佳方案问题.docx
《管道铺设施工的最佳方案问题.docx》由会员分享，可在线阅读，更多相关《管道铺设施工的最佳方案问题.docx（29页珍藏版）》请在冰点文库上搜索。
管道铺设施工的最佳方案问题
一．问题描述：
1.实验题目：
需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道即可。
假设任意两个小区之间都可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。
选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。
2.基本要求：
在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。
每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。
3.测试数据：
使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。
右侧是给出的参考解。
4.简述每一部分的对象、目的和要求：
.主函数部分：
对象：
图G；
目的：
为图G分配空间，以作为后续调用函数的参数；
要求：
无。
.Create_ALGraph（）函数部分：
对象：
顶点，边及其权值；
目的：
将顶点，边存放在一起，构成图；
要求：
构造顶点表，各顶点的邻接表以构造图。
.Create_WLGraph（）函数部分：
对象：
图G；
目的：
将图中的权值只存放一次，存放到w指向的结构体中；
要求：
权值只存放一次，再分别存放该边的左右顶点。
.select_info（）函数部分：
对象：
w指向的结构体；
目的：
将该结构体中的各权值以升序排列；
要求：
采用简单选择法进行排序。
.Create_TLGraph（）函数部分：
对象：
排序后的w指向的结构体；
目的：
找到构成最小生成树的边；
要求：
依权值升序排列，判断各边是否构成回路来取舍各边。
二．需求分析
1.程序所能达到的基本可能：
在n个小区m条管道中，选取n-1条管道，实现连通这n个小区，同时权值之和为最小。
2.输入输出形式及输入值范围：
程序运行后，用户可根据提示信息：
"Pleaseinputtheverticesandtheedges:
"输入顶点数和边数，再根据提示信息：
"Pleaseinputtheinformationofthevertices:
"输入顶点信息，然后进入循环，创建各个顶点的邻接表，即根据提示信息"Pleaseinputtheinformationofedges:
"和"Pleaseinputtheinformationofweight:
"依次输入各顶点与其他顶点本身以及两者之间的权值，创建图完毕。
用户输入完毕后，程序自动输出运行结果。
输入值必须为字母和浮点数，可以不必区分大小写。
3.测试数据要求：
用户输入字母时，输入大写或小写，都可以被该程序识别，正常运行。
但必须根据提示信息后面给出的参考形式，有针对性地输入逗号。
三．概要设计
为了实现上述功能，该程序以邻接表来存储图，因此需要图这个抽象数据类型。
1.图抽象数据类型定义：
ADTALGraph{
数据对象：
D={
，i=1,2,3....,n,n
}
数据关系：
R=
;
基本操作：
Create_ALGraph（G）；//创建图
Create_WLGraph（G）；//将图G中各顶点以及权值存放到新图中，权值只存放一次
select_info（W,G）；//将新图W中的权值按升序排列
Create_TLGraph（w,G）；//将最小生成树以顶点对（i,j）的形式输出
}ADTALGraph
2.本程序保护模块：
主函数模块
图模块
调用关系：
3.主要算法流程图：
Create_ALGraph（）算法流程图：
Create_WLGraph（）算法流程图：
Create_TLGraph（）算法流程图：
四．详细设计
1.相关头文件的调用说明：
#include
#include
#defineMaxVerNum100
2.元素类型、结点类型和结点指针类型：
staticvoidforcefloat（float*p）
{
floatf=*p;
forcefloat（&f）;
}
typedefstructnode
{intadjvex;
floatinfo;
structnode*next;
}EdgeNode;
typedefstructvnode
{charvertex;
EdgeNode*firstedge;
}VertexNode;
typedefVertexNodeAdjList[MaxVerNum];
structbian
{intz,y;
floatinfo;
};
typedefstruct
{charv[MaxVerNum];
structbiane[MaxVerNum];
}WGraph;
structvisit
{visited[MaxVerNum];
position[MaxVerNum];
vvpp[MaxVerNum][MaxVerNum];
}
3.邻接表类型：
typedefstruct
{AdjListadjlist;
intn,e;
}ALGraph;
//部分基本操作的伪码实现
Create_ALGraph（ALGraph*G）
{inti,j;charp,q;
intk;/*intx=0;*/
EdgeNode*s;
chara,b;
printf（"Pleaseinputtheverticesandtheedges:
\n"）;
scanf（"%d,%d",&（G->n）,&（G->e））;
printf（"Pleaseinputtheinformationofthevertices:
\n"）;
getchar（）;
for（i=0;i<（G->n）;i++）
{scanf（"%c",&（G->adjlist[i].vertex））;
G->adjlist[i].firstedge=NULL;
/*if（G->adjlist[i].vertex!
=''&&G->adjlist[i].vertex!
='\n'&&G->adjlist[i].vertex!
=''）
x++;*/
}
for（k=0;k<2*（G->e）;k++）
{printf（"Pleaseinputtheinformationofedges:
\n"）;
getchar（）;
scanf（"%c,%c",&p,&q）;
s=（EdgeNode*）malloc（sizeof（EdgeNode））;
s->adjvex=q-64;
i=p-64;
getchar（）;
printf（"Pleaseinputtheinformationofweight:
\n"）;
scanf（"%f",&（s->info））;
s->next=G->adjlist[i-1].firstedge;
G->adjlist[i-1].firstedge=s;
}/*
printf（"Pleaseoutputtheinformation:
\n"）;
printf（"%d,%d\n",G->n,G->e）;
printf（"x=%d\n",x）;
for（i=0;in;i++）
{printf（"%c\n",G->adjlist[i].vertex）;
s=G->adjlist[i].firstedge;
while（s!
=NULL）
{printf（"thelinbianis%d,theinfois%.1f\n",s->adjvex,s->info）;
s=s->next;
}
}*/
}
intPanduan_Vertex（intk,inti,WGraph*w,EdgeNode*s）
{intt;
for（t=0;tif（（w->e[t]）.y==i+1&&（w->e[t]）.z==s->adjvex）
return1;
return0;
}
voidselect_info（WGraph*W,ALGraph*G）
{inti,j,p,k;
floatt;
for（i=0;i<（G->e）;i++）
{p=i;
for（j=i+1;j<（G->e）;j++）
if（W->e[j].infoe[p].info）p=j;
if（p!
=i）
{t=W->e[p].info;
W->e[p].info=W->e[i].info;
W->e[i].info=t;
k=W->e[p].z;
W->e[p].z=W->e[i].z;
W->e[i].z=k;
k=W->e[p].y;
W->e[p].y=W->e[i].y;
W->e[i].y=k;
}
}/*
for（i=0;i<（G->e）;i++）
printf（"%.1f",W->e[i].info）;
printf（"\n"）;*/
}
intjudge_vertex（WGraph*w,inti,structvisit*vp）
{
if（vp->visited[w->e[i].z-1]==-1&&vp->visited[w->e[i].y-1]==-1）
return1;
elseif（vp->visited[w->e[i].z-1]==-1&&vp->visited[w->e[i].y-1]==1）
return2;
elseif（vp->visited[w->e[i].y-1]==-1&&vp->visited[w->e[i].z-1]==1）
return3;
elseif（vp->visited[w->e[i].z-1]==1&&vp->visited[w->e[i].y-1]==1）
return4;
}
voidCreate_TLGraph（WGraph*w,ALGraph*G）
{WGraphT;
inti,j,t,h,k=2;
intm=1;intabc,bcd;
structvisit*vp;
vp=（structvisit*）malloc（sizeof（structvisit））;
for（i=0;i<（G->n）;i++）
{vp->visited[i]=-1;
vp->position[i]=-1;
vp->vvpp[i][0]=i+1;
for（j=1;jn;j++）
vp->vvpp[i][j]=0;
}
T.v[0]=w->v[w->e[0].z-1];
T.v[1]=w->v[w->e[0].y-1];
vp->visited[w->e[0].z-1]=1;
vp->position[w->e[0].z-1]=w->e[0].z;
for（j=0;j<（G->n）;j++）
if（vp->vvpp[w->e[0].z-1][j]==0）
{vp->vvpp[w->e[0].z-1][j]=w->e[0].y;
break;}
vp->visited[w->e[0].y-1]=1;
vp->position[w->e[0].y-1]=w->e[0].z;
T.e[0].info=w->e[0].info;
T.e[0].z=w->e[0].z;
T.e[0].y=w->e[0].y;
for（i=1;i<（G->e）;i++）
{t=judge_vertex（w,i,vp）;
if（t==4）
{if（vp->position[w->e[i].z-1]==vp->position[w->e[i].y-1]）
continue;
else{abc=0;bcd=0;
for（j=0;jn;j++）
if（vp->vvpp[vp->position[w->e[i].y-1]-1][j]!
=0）
abc++;
for（j=0;jn;j++）
if（vp->vvpp[vp->position[w->e[i].z-1]-1][j]!
=0）
bcd++;
for（j=bcd,h=0;jn&&h{vp->vvpp[（vp->position[w->e[i].z-1]）-1][j]=vp->vvpp[（vp->position[w->e[i].y-1]）-1][h];
vp->vvpp[vp->position[w->e[i].y-1]-1][h]=0;
}
for（h=bcd;hvp->position[（vp->vvpp[vp->position[w->e[i].z-1]-1][h]）-1]=vp->position[w->e[i].z-1];
T.e[m].info=w->e[i].info;
T.e[m].z=w->e[i].z;
T.e[m].y=w->e[i].y;
m++;
}
}
elseif（t==1）
{vp->visited[w->e[i].z-1]=1;
vp->visited[w->e[i].y-1]=1;
T.v[k++]=w->v[w->e[i].z-1];
T.v[k++]=w->v[w->e[i].y-1];
T.e[m].info=w->e[i].info;
T.e[m].z=w->e[i].z;
T.e[m].y=w->e[i].y;
m++;
vp->position[w->e[i].z-1]=w->e[i].z;
vp->position[w->e[i].y-1]=w->e[i].z;
vp->vvpp[w->e[i].z-1][1]=w->e[i].y;
vp->vvpp[w->e[i].y-1][0]=0;
}
elseif（t==2）
{vp->visited[w->e[i].z-1]=1;
vp->position[w->e[i].z-1]=vp->position[w->e[i].y-1];
for（j=0;j<（G->n）;j++）
if（vp->vvpp[vp->position[w->e[i].y-1]-1][j]==0）
{vp->vvpp[vp->position[w->e[i].y-1]-1][j]=w->e[i].z;
break;
}
vp->vvpp[w->e[i].z-1][0]=0;
T.v[k++]=w->v[w->e[i].z-1];
T.e[m].info=w->e[i].info;
T.e[m].z=w->e[i].z;
T.e[m].y=w->e[i].y;
m++;
}
elseif（t==3）
{vp->visited[w->e[i].y-1]=1;
vp->position[w->e[i].y-1]=vp->position[w->e[i].z-1];
for（j=0;j<（G->n）;j++）
if（vp->vvpp[vp->position[w->e[i].z-1]-1][j]==0）
{vp->vvpp[vp->position[w->e[i].z-1]-1][j]=w->e[i].y;
break;
}
vp->vvpp[w->e[i].y-1][0]=0;
T.v[k++]=w->v[w->e[i].y-1];
T.e[m].info=w->e[i].info;
T.e[m].z=w->e[i].z;
T.e[m].y=w->e[i].y;
m++;
}
}
printf（"Pleaseoutputtheinformation:
\n"）;
for（i=0;i<（G->n）-1;i++）
printf（"（%c,%c）\n",T.e[i].z+64,T.e[i].y+64）;
}
voidCreate_WLGraph（ALGraph*G）
{inti,j,t,m,k=0;
EdgeNode*s,*p;
WGraph*W;
W=（WGraph*）malloc（sizeof（WGraph））;
W->v[0]=G->adjlist[0].vertex;
s=G->adjlist[0].firstedge;
while（s!
=NULL）
{W->e[k].z=1;
W->e[k].y=s->adjvex;
W->e[k].info=s->info;
k++;
s=s->next;
}
for（i=1;i<（G->n）;i++）
{W->v[i]=G->adjlist[i].vertex;
s=G->adjlist[i].firstedge;
while（s!
=NULL）
{m=Panduan_Vertex（k,i,W,s）;
if（m==1）
{s=s->next;
continue;}
else
{W->e[k].z=i+1;
W->e[k].y=s->adjvex;
W->e[k].info=s->info;
k++;
s=s->next;
}
}
}/*
printf（"Pleaseoutputtheinformation:
\n"）;
for（i=0;in;i++）
printf（"%c\n",W->v[i]）;
for（i=0;ie;i++）
printf（"%d,%d,%.1f\n",W->e[i].z,W->e[i].y,W->e[i].info）;*/
select_info（W,G）;
Create_TLGraph（W,G）;
}
4.主函数的伪码：
main（）
{ALGraph*G;
G=（ALGraph*）malloc（sizeof（ALGraph））;
Create_ALGraph（G）;
Create_WLGraph（G）;
}
5.函数调用关系：
五．调试分析
1.出现问题及解决方法：
在刚开始写程序时，由于考虑不全面，在去除连通图闭合回路的算法中遇到很大困难，后来采用以下方法解决了这个问题：
将每个顶点分别放在一个结构体中，结构体中的数组visited[i]记录顶点Vi是否被访问过的情况，position[i]记录顶点Vi的具体位置，二维数组vvpp[i][j]记录已经将以该顶点为左顶点或右顶点的权值存入T中后，该权值的右顶点或左顶点的编号。
其具体思想是：
只要将一个权值存入T中，就将相应的左右顶点放到同一个二维数组中，之后每欲将一个权值加入T中，先检验该权值的两顶点是否在同一个二维数组中。
若不在，则将该权值存入T中；若在，将该权值舍去（因为再将该权值加入T中，就会出现回路）。
2.方法优缺点分析：
优点：
思想比较简单，容易令人理解；
在写核心算法时，先将字母顶点用相应的数字代替，所以在将数字转化成字母回去时，利用数字与ASCII码值的固定差值，可以保证用户在输入时的大小写字母都可以被该程序识别。
缺点：
由于采用数字来代替字母，中间的转换关系比较复杂，尤其是将对应关系理清需要足够的耐心和细心。
3．主要算法的时间和空间复杂度分析：
（1）由于Create_ALGraph（）算法中将读入顶点的操作执行了n次，读入边的操作执行了2m次，故其时间复杂度为O（n+2m）；
（2）由于Create_WLGraph（）算法将读入权值及其左右顶点的操作执行了n次，故其时间复杂度为O（n）；
（3）由于Create_TLGraph（）算法中根据判断是否构成回路来取舍边，因为有n条边，故要执行n次，所以时间复杂度是O（n）；
（4）由于select_info（）函数采用简单选择法排序，时间复杂度是O（
）；
（5）所有算法的空间复杂度都是O
（1）。
六．使用说明
程序运行后，用户根据提示输入顶点数，边数，顶点信息，边的信息，权值，输入完毕后程序会自动以顶点对（i,j）的形式输出最小生成树的边。
七．调试结果
输入数据：
“9”，“15”，“ABCDEFGHI”，“A,B”，“32.8”，“A,C”，“44.6”，“A,H”，“12.1”，“A,I”，“18.2”，“B,A”，“32.8”，“B,C”，“5.9”，“C,A”，“44.6”，“C,B”，“5.9”，“C,D”，“21.3”，“C,E”，“41.1”，“C,G”，“56.4”，“D,C”，“21.3”，“D,E”，“67.3”，“D,F”，“98.7”，“E,C”，“41.1”，“E,D”，“67.3”，“E,F”，“85.6”，“E,G”，“10.5”，“F,D”，“98.7”，“F,E”，“85.6”，“F,I”，“79.2”，“G,C”，“56.4”，“G,E”，“10.5”，“G,H”，“52.5”，“H,A”，“12.1”，“H,G”，“52.5”，“H,I”，“8.7”，“I,A”，“18.2”，“I,F”，“79.2”，“I,H”，“8.7”。
（双引号不需输入）
输出数据：
（B,C）,（H,I）,（E,G）,（A,H）,（C,D）,（A,B）,（C,E）,（F,I）
运行结果截屏：
八．附录
源程序清单：
#include/*调用的头文件库说明*/
#include
#defineMaxVerNum100
staticvoidforcefloat（float*p）
{
floatf=*p;/*由于我的TC中不支持浮点数，故添加了这个程序段*/
forcefloat（&f）;
}
typedefstructnode/*构造邻接表的结构体*/
{intadjvex;
floatinfo;/*存放权值*/
structnode*next;/*指向下一个邻接点的指针域*/
}EdgeNode;
typedefstructvnode/*构造顶点表的结构体*/
{charvertex;/*顶点域*/
EdgeNode*firstedge;/*边表头指针*/
}VertexNode;
typedefVertexNodeAdjList[MaxVerNum];
typedefstruct/*构造图的结构体*/
{AdjListadjlist;/*邻接表*/
intn,e;/*顶点数和边数*/
}ALGraph;
structbian/*存放权值及其左右顶点的结构体*/
{intz,y;
floatinfo;
};
typedefstruct/*用该结构体来只存放一次权值及其相应的顶点*/
{charv[MaxVerNum
升级会员 