1 / 9
文档名称:

最小生成树问题.docx

格式:docx   大小:61KB   页数:9页
下载后只包含 1 个 DOCX 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

最小生成树问题.docx

上传人:HEziyao 2023/2/7 文件大小:61 KB

下载得到文件列表

最小生成树问题.docx

文档介绍

文档介绍:该【最小生成树问题 】是由【HEziyao】上传分享,文档一共【9】页,该文档可以免费在线阅读,需要了解更多关于【最小生成树问题 】的内容,可以使用淘豆网的站内搜索功能,选择自己适合的文档,以下文字是截取该文章内的部分文字,如需要获得完整电子版,请下载此文档到您的设备,方便您编辑和打印。Revisedat2pmonDecember25,2020.
最小生成树问题
榆林学院12届课程设计
《最小生成树问题》
课程设计说明书
学生姓名:赵佳
学号:
院系:信息工程学院
专业:计算机科学与技术
班级:计14本1
指导教师:
答辩时间:年月日
最小生成树问题
问题陈述
最小生成树问题
设计要求:在n个城市之间建设网络,只需保证连通即可,求最经济的架设方法。存储结构采用多种。求解算法多种。
需求分析
在n个城市之间建设网络,只需保证连通即可。
求城市之间最经济的架设方法。
,求解算法也采用多种。
概要设计
功能模块图
开始
创建一个图
功能选择


算法

结束
2、功能描述
CreateUDG()
创建一个图:通过给用户信息提示,让用户将城市信息及城市之间的联系关系和连接权值写入程序,并根据写入的数据创建成一个图。
Switch()
功能选择:给用户提示信息,让用户选择相应功能。
Adjacency_Matrix()
建立邻接矩阵:将用户输入的数据整理成邻接矩阵并显现在屏幕上。
Adjacency_List()
建立邻接表:将用户输入的数据整理成临接表并显现在屏幕上。
MiniSpanTree_KRSL()
kruskal算法:利用kruskal算法求出图的最小生成树,即:城市之间最经济的连接方案。
MiniSpanTree_PRIM()
PRIM算法:利用PRIM算法求出图的最小生成树,即:城市之间最经济的连接方案。
详细设计
本次课程设计采用两种存储结构以及两种求解算法。
1、两种存储结构的存储定义如下:
typedefstructArcell
{
doubleadj;
}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{
charvexs[MAX_VERTEX_NUM];开始
标志顶点1加入U集合
寻找满足边的一个顶点在U,另一个顶点在V的最小边
形成n-1条边的生成树
顶点k加入U
修改由顶点k到其他顶点边的权值
结束
得到最小生成树
CreateUDG()
main()
Adjacency_Matrix()
Adjacency_List()
MiniSpanTree_KRSL()
MiniSpanTree_PRIM()
locateVex()
locateVex()
Minimum()
locateVex()
Sortdge()
dj=MAX;
}
cout<<"请输入两个城市名称及其连接费用(严禁连接重复输入!):"<<endl;
for(k=0;k<;++k)
{
cin>>dgevalue[k].ch1>>dgevalue[k].ch2>>dgevalue[k].value;
i=LocateVex(G,dgevalue[k].ch1);
j=LocateVex(G,dgevalue[k].ch2);
[i][j].adj=dgevalue[k].value;
[j][i].adj=[i][j].adj;
}
returnOK;
}
intLocateVex(MGraphG,charch)dj==MAX)
cout<<0<<"";
else
cout<<[i][j].adj<<"";
cout<<endl;
}
}
voidAdjacency_List(MGraphG,Dgevaluedgevalue)h1==[i]&&dgevalue[j].ch2!=[i])
cout<<dgevalue[j].ch2<<"->";
elseif(dgevalue[j].ch1!=[i]&&dgevalue[j].ch2==[i])
cout<<dgevalue[j].ch1<<"->";
cout<<"\b\b"<<endl;
}
}
voidMiniSpanTree_KRSL(MGraphG,Dgevalue&dgevalue)h1)];
p2=bj[LocateVex(G,dgevalue[i].ch2)];
if(p1!=p2)
{
cout<<"城市"<<dgevalue[i].ch1<<"与城市"<<dgevalue[i].ch2<<"连接。"<<endl;
for(j=0;j<;j++)
{
if(bj[j]==p2)
bj[j]=p1;
}
}
}
}
voidSortdge(Dgevalue&dgevalue,MGraphG)alue>dgevalue[j].value)
{
temp=dgevalue[i].value;
dgevalue[i].value=dgevalue[j].value;
dgevalue[j].value=temp;
ch1=dgevalue[i].ch1;
dgevalue[i].ch1=dgevalue[j].ch1;
dgevalue[j].ch1=ch1;
ch2=dgevalue[i].ch2;
dgevalue[i].ch2=dgevalue[j].ch2;
dgevalue[j].ch2=ch2;
}
}
}
}
voidMiniSpanTree_PRIM(MGraphG,charu)djvex=u;
closedge[j].lowcost=[k][j].adj;
}
}
closedge[k].lowcost=0;
for(i=1;i<;i++)
{
k=Minimum(G,closedge);
cout<<"城市"<<closedge[k].adjvex<<"与城市"<<[k]<<"连接。"<<endl;
closedge[k].lowcost=0;
for(j=0;j<;++j)
{
if[k][j].adj<closedge[j].lowcost)
{
closedge[j].adjvex=[k];
closedge[j].lowcost=[k][j].adj;
}
}
}
}
intMinimum(MGraphG,Closedgeclosedge)owcost!=0&&closedge[i].lowcost<k)
{
k=closedge[i].lowcost;
j=i;
}
}
returnj;
}
voidmain()
{
MGraphG;
Dgevaluedgevalue;
CreateUDG(G,dgevalue);
charu;
cout<<"图创建成功。";
cout<<"请根据如下菜单选择操作。\n";
cout<<"1、用邻接矩阵存储:"<<endl;
cout<<"2、用邻接表存储:"<<endl;
cout<<"3、克鲁斯卡尔算法求最经济的连接方案"<<endl;
cout<<"4、普里姆算法求最经济的连接方案"<<endl;
ints;
chary='y';
while(y='y')
{
cout<<"请选择菜单:"<<endl;
cin>>s;
switch(s)
{
case1:
cout<<"用邻接矩阵存储为:"<<endl;
Adjacency_Matrix(G);
break;
case2:
cout<<"用邻接表存储为:"<<endl;
Adjacency_List(G,dgevalue);
break;
case3:
cout<<"克鲁斯卡尔算法最经济的连接方案为:"<<endl;
MiniSpanTree_KRSL(G,dgevalue);
break;
case4:
cout<<"普里姆算法最经济的连接方案为:"<<endl;
cout<<"请输入起始城市名称:";
cin>>u;
MiniSpanTree_PRIM(G,u);
break;
default:
cout<<"输入有误!";
break;
}
cout<<endl<<"是否继续?y/n:";
cin>>y;
if(y=='n')
break;
}
}
运行结果与测试
设计体会与总结
通过本次课程设计,我在程序设计中,用邻接矩阵和邻接表这两种存储结构进行编程,且对Prim算法和Kruskal算法生成最小生成树有了一个初步的了解,同时也为日后的毕业设计打下了良好的基础。而且通过课程设计在下述各方面得到了锻炼:
1、能根据实际问题的具体情况,结合数据结构课程中的基本理论和基本算法,正确分析出数据的逻辑结构,合理地选择相应的存储结构,并能设计出解决问题的有效算法。
2、提高程序设计和调试能力。通过上机实****验证自己设计的算法的正确性。学会有效利用基本调试方法,迅速找出程序代码中的错误并且修改。
3、培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度,进一步提高程序设计水平。
在本次课程设计中,知道如何在n个城市之间建设网络,只需保证连通即可,求最经济的架设方法。并且用了多种求解方式。
这几天的课程设计让我充分地体会到了上机实践对于计算机编程的重要性。
只顾学****理论是远远不够的。实践中可以发现许许多多的问题,然后通过同学老师的帮助,得以解决,让自己的编程能力得到极大的提升。