最小生成树问题

《最小生成树问题》

课程设计说明书

学生姓名： 赵佳

学 号： 12

院 系： 信息工程学院 专 业： 计算机科学与技术 班 级： 计14本1 指导教师： 答辩时间： 年 月 日

最小生成树问题

一、 问题陈述

最小生成树问题

设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。

二、 需求分析

1.在n个城市之间建设网络，只需保证连通即可。 2.求城市之间最经济的架设方法。

3.采用多种存储结构，求解算法也采用多种。

三、 概要设计

1、功能模块图

开始 创建一个图 功能选择 1.建立邻接矩阵 2.建立邻接表 算法 4. PRIM算法 结束

2、功能描述

（1) CreateUDG() 创建一个图：通过给用户信息提示，让用户将城市信息及城市之间的联系关系和连接权值写入程序，并根据写入的数据创建成一个图。

（2) Switch()

功能选择：给用户提示信息，让用户选择相应功能。 （3) Adjacency_Matrix()

建立邻接矩阵：将用户输入的数据整理成邻接矩阵并显现在屏幕上。 （4) Adjacency_List()

建立邻接表：将用户输入的数据整理成临接表并显现在屏幕上。 （5) MiniSpanTree_KRSL()

kruskal算法：利用kruskal算法求出图的最小生成树，即：城市之间最经济的连接方案。

（6) MiniSpanTree_PRIM()

PRIM算法：利用PRIM算法求出图的最小生成树，即：城市之间最经济的连接方案。

四、 详细设计

本次课程设计采用两种存储结构以及两种求解算法。 1、两种存储结构的存储定义如下： typedef struct Arcell {

double adj;

}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char vexs[MAX_VERTEX_NUM];

开始 标志顶点1加入U集合 形成n-1条边的生成树 寻找满足边的一个顶点在U,另一个顶点在V的最小边 顶点k加入U 修改由顶点k到其他顶点边的权值 得到最小生成树 结束 main() CreateUDG() Adjacency_Matrix() Adjacency_List() MiniSpanTree_KRSL() MiniSpanTree_PRIM() locateVex() Sortdge() locateVex() locateVex() Minimum() dj=MAX; }

cout<<\"请输入两个城市名称及其连接费用(严禁连接重复输入!)：\"<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; }

return OK; }

int LocateVex(MGraph G,char ch) dj==MAX) cout<<0<<\" \"; else

cout<<[i][j].adj<<\" \"; cout<cout<\";

else if(dgevalue[j].ch1!=[i]&&dgevalue[j].ch2==[i]) cout<\"; cout<<\"\\b\\b \"<void MiniSpanTree_KRSL(MGraph G,Dgevalue & dgevalue)h1)]; p2 = bj[LocateVex(G,dgevalue[i].ch2)]; if(p1 != p2) {

cout<<\" 城市\"<if(bj[j] == p2) bj[j] = p1; } } } }

void Sortdge(Dgevalue & dgevalue,MGraph G)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; } } } }

void MiniSpanTree_PRIM(MGraph G,char u)djvex = u; closedge[j].lowcost = [k][j].adj; } }

closedge[k].lowcost = 0; for(i=1; i<; i++) {

k = Minimum(G,closedge);

cout<<\" 城市\"<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; } } } }

int Minimum(MGraph G,Closedge closedge) owcost != 0 && closedge[i].lowcost < k) {

k = closedge[i].lowcost; j = i; } }

return j; }

void main() {

MGraph G;

Dgevalue dgevalue;

CreateUDG(G,dgevalue); char u;

cout<<\"图创建成功。\";

cout<<\"请根据如下菜单选择操作。\\n\"; cout<<\"1、用邻接矩阵存储：\"<cout<<\"3、克鲁斯卡尔算法求最经济的连接方案\"<char y='y'; while(y='y') {

cout<<\"请选择菜单：\"<>s; switch(s) {

case 1:

cout<<\"用邻接矩阵存储为：\"<cout<<\"用邻接表存储为：\"<cout<<\"克鲁斯卡尔算法最经济的连接方案为:\"<cout<<\"普里姆算法最经济的连接方案为:\"<>u;

MiniSpanTree_PRIM(G,u); break; default:

cout<<\"输入有误!\"; break; }

cout<>y;

if(y=='n') break; } }

五、 运行结果与测试

六、 设计体会与总结

通过本次课程设计，我在程序设计中，用邻接矩阵和邻接表这两种存储结构进行编程，且对Prim算法和Kruskal算法生成最小生成树有了一个初步的了解，同时也为日后的毕业设计打下了良好的基础。而且通过课程设计在下述各方面得到了锻炼：

1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。

2、提高程序设计和调试能力。通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。

3、培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。

在本次课程设计中，知道如何在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。并且用了多种求解方式。

这几天的课程设计让我充分地体会到了上机实践对于计算机编程的重要性。 只顾学习理论是远远不够的。实践中可以发现许许多多的问题，然后通过同学老师的帮助，得以解决，让自己的编程能力得到极大的提升。