最小生成树问题

1、榆林学院12届课程设计 最小生成树问题 课程设计说明书 学生姓名：赵佳 学号：12 院系：信息工程学院 专业：计算机科学与技术 班级：计14本1 指导教师： 答辩时间：年 月 日 最小生成树问题 一、问题陈述 最小生成树问题 设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架 设方法。存储结构采用多种。求解算法多种。 二、需求分析 1. 在n个城市之间建设网络，只需保证连通即可。 2. 求城市之间最经济的架设方法。 3. 采用多种存储结构，求解算法也采用多种。 三、概要设计 1、功能模块图 2、功能描述 (1) CreateUDG() 创建一个图：通过给用户信息提示，让用户将城市

2、信息及城市之间的联系关 系和连接权值写入程序，并根据写入的数据创建成一个图。 (2) Switch() 功能选择：给用户提示信息，让用户选择相应功能。 (3) Adjace ncy_Matrix() 建立邻接矩阵：将用户输入的数据整理成邻接矩阵并显现在屏幕上。 ( 4) Adjacency_List() 建立邻接表：将用户输入的数据整理成临接表并显现在屏幕上。 ( 5) MiniSpanTree_KRSL() kruskal 算法：利用 kruskal 算法求出图的最小生成树，即：城市之间最经 济的连接方案。 ( 6) MiniSpanTree_PRIM() PRIM算法：利用PRIM算法求出

3、图的最小生成树，即：城市之间最经济的连 接方案。 四、详细设计 本次课程设计采用两种存储结构以及两种求解算法。 1、两种存储结构的存储定义如下： typedef struct Arcell double adj; Arcell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct charvexsMAX_VERTEX_NUM; dj=MAX; cout 请输入两个城市名称及其连接费用 ( 严禁连接重复输入 !) ： endl; for(k=0;k dgevaluek.ch1 dgevaluek.ch2 dgevaluek.value; i

4、= LocateVex(G,dgevaluek.ch1); j = LocateVex(G,dgevaluek.ch2); ij.adj = dgevaluek.value; ji.adj = ij.adj; return OK; int LocateVex(MGraph G,char ch) dj=MAX) cout0 ; else coutij.adj ; coutendl; void Adjacency_List(MGraph G,Dgevalue dgevalue) h1=i else if(dgevaluej.ch1!=i coutbb endl; void MiniSpanTree

5、_KRSL(MGraph G,Dgevalue p2 = bjLocateVex(G,dgevaluei.ch2); if(p1 != p2) cout 城 市 dgevaluei.ch1 与 城 市 dgevaluei.ch2 连接。 endl; for(j=0; j dgevaluej.value) temp = dgevaluei.value; dgevaluei.value = dgevaluej.value; dgevaluej.value = temp; ch1 = dgevaluei.ch1; dgevaluei.ch1 = dgevaluej.ch1; dgevaluej.ch

6、1 = ch1; ch2 = dgevaluei.ch2; dgevaluei.ch2 = dgevaluej.ch2; dgevaluej.ch2 = ch2; void MiniSpanTree_PRIM(MGraph G,char u)djvex = u; closedgej.lowcost = kj.adj; closedgek.lowcost = 0; for(i=1; i; i+) k = Minimum(G,closedge); cout 城市 closedgek.adjvex 与城市 k 连接。 endl; closedgek.lowcost = 0; for(j=0; j;

7、+j) ifkj.adj closedgej.lowcost) closedgej.adjvex = k; closedgej.lowcost= kj.adj; int Minimum(MGraph G,Closedge closedge) owcost != 0 j = i; return j; void main() MGraph G; Dgevalue dgevalue; CreateUDG(G,dgevalue); char u; cout 图创建成功。 ; cout 请根据如下菜单选择操作。 n; cout1 、用邻接矩阵存储： endl; cout2 、用邻接表存储： endl;

8、cout3 、克鲁斯卡尔算法求最经济的连接方案 endl; cout4 、普里姆算法求最经济的连接方案 endl; int s; char y=y; while(y=y) cout 请选择菜单： s; switch(s) case 1: cout 用邻接矩阵存储为： endl; Adjacency_Matrix(G); break; case 2: cout 用邻接表存储为： endl; Adjacency_List(G,dgevalue); break; case 3: cout 克鲁斯卡尔算法最经济的连接方案为 :endl; MiniSpanTree_KRSL(G,dgevalue); b

9、reak; case 4: cout 普里姆算法最经济的连接方案为 :endl; coutu; MiniSpanTree_PRIM(G,u); break; default: cout 输入有误 !; break; coutendly; if(y=n) break; 五、运行结果与测试 六、设计体会与总结 通过本次课程设计， 我在程序设计中， 用邻接矩阵和邻接表这两种存储结构 进行编程，且对 Prim 算法和 Kruskal 算法生成最小生成树有了一个初步的了解， 同时也为日后的毕业设计打下了良好的基础。 而且通过课程设计在下述各方面得 到了锻炼： 1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算 法，正确分析出数据的逻辑结构， 合理地选择相应的存储结构， 并能设计出解决 问题的有效算法。 2、提高程序设计和调试能力。通过上机实习，验证自己设计的算法的正确 性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3、培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一 步提高程序设计水平。 在本次课