最小生成树问题.doc

《最小生成树问题.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

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

3、连接方案。（4)MiniSpanTree_PRIM()PRIM算法：利用PRIM算法求出图的最小生成树，即：城市之间最经济的连接方案。二、详细设计本次课程设计采用两种存储结构以及两种求解算法。1、两种存储结构的存储定义如下：typedefstructArcell{doubleadj;}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{charvexs[MAX_VERTEX_NUM];//节点数组AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//图的当前

4、节点数和弧数}MGraph;typedefstructPnode//用于普利姆算法{charadjvex;//节点doublelowcost;//权值}Pnode,Closedge[MAX_VERTEX_NUM];//记录顶点集U到V-U的代价最小的边的辅助数组定义typedefstructKnode//用于克鲁斯卡尔算法中存储一条边及其对应的2个节点{charch1;//节点1charch2;//节点2doublevalue;//权值}Knode,Dgevalue[MAX_VERTEX_NUM];2、求解算法采用Prim算法和Kruskal算法。（1）

5、普里姆算法(Prim)算法普里姆算法(Prim)算法是一种构造性算法，生成最小生成树的步骤如下：初始化U={v}。以v到其他顶点的所有边为候选边。重复一下步骤(n-1)次，使得其他(n-1)个顶点被加入到U中。从候选边中挑选权值最小的边加入TE，设该边在V—U中的顶点是vk，将顶点vk加入到U中;考察当前V—U中的所有顶点vj，修改候选边：若(vk,vj)的权值小于原来和vj关联的候选边，则用(vk,vj)取代后者作为候选边。开始标志顶点1加入U集合寻找满足边的一个顶点在U,另一个顶点在V的最小边形成n-1条边的生成树顶点k加入U修改由顶点k到其他顶点边

6、的权值结束得到最小生成树（2）克鲁斯卡尔(Kruskal)算法克鲁斯卡尔(Kruskal)算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。假设G=(V,E)是一个具有n个顶点的带权连通无向图，T=(U,TE)是G的最小生成树，则构造最小生成树的步骤如下：置U的初值等于V（即包含有G中的全部顶点），TE的初值为空集（即图T中每一个顶点都构成一个分量）。将图G中的边按权值从小到大的顺序依次选取：若选取的边未使生成树T形成回路，则加入TE，否则舍弃，直到TE中包含(n-1)条边为止。3、使用的函数intCreateUDG(MGraph&G,Dge

7、value&dgevalue);intLocateVex(MGraphG,charch);intMinimum(MGraphG,Closedgeclosedge);voidMiniSpanTree_PRIM(MGraphG,charu);voidSortdge(Dgevalue&dgevalue,MGraphG);voidAdjacency_Matrix(MGraphG);voidAdjacency_List(MGraphG,Dgevaluedgevalue);函数之间的调用关系图：CreateUDG()main()Adjacency_Matrix()A

8、djacency_List()MiniSpanTree_KRSL()MiniSp