文档介绍：该【最小生成树问题】是由【Duan700507】上传分享，文档一共【16】页，该文档可以免费在线阅读，需要了解更多关于【最小生成树问题】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。CKBOODwasrevisedintheearlymorningofDecember17,2020.
最小生成树问题
榆林学院12届课程设计
《最小生成树问题》
课程设计说明书
学生姓名:赵佳
学号: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++)
{