《最小生成树问题》由会员分享，可在线阅读，更多相关《最小生成树问题（13页珍藏版）》请在金锄头文库上搜索。
1、 榆林学院12届课程设计 最小生成树问题课程设计说明书 学生姓名： 赵佳 学 号： 1412210112 院 系： 信息工程学院 专 业： 计算机科学与技术 班 级： 计14本1 指导教师： 答辩时间： 年 月 日 最小生成树问题一、 问题陈述最小生成树问题设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。二、 需求分析1. 在n个城市之间建设网络，只需保证连通即可。2. 求城市之间最经济的架设方法。3.采用多种存储结构，求解算法也采用多种。三、 概要设计1、 功能模块图开始创建一个图功能选择1.建立邻接矩阵2.建立邻接表3.kruskal
2、算法4. PRIM算法结束2、功能描述（1) CreateUDG()创建一个图：通过给用户信息提示，让用户将城市信息及城市之间的联系关系和连接权值写入程序，并根据写入的数据创建成一个图。（2) Switch()功能选择：给用户提示信息，让用户选择相应功能。（3) Adjacency_Matrix()建立邻接矩阵：将用户输入的数据整理成邻接矩阵并显现在屏幕上。（4) Adjacency_List()建立邻接表：将用户输入的数据整理成临接表并显现在屏幕上。（5) MiniSpanTree_KRSL()kruskal算法：利用kruskal算法求出图的最小生成树，即：城市之间最经济的连接方案。（6)
3、 MiniSpanTree_PRIM()PRIM算法：利用PRIM算法求出图的最小生成树，即：城市之间最经济的连接方案。四、 详细设计本次课程设计采用两种存储结构以及两种求解算法。1、两种存储结构的存储定义如下：typedef struct Arcell double adj; Arcell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct char vexsMAX_VERTEX_NUM; /节点数组 AdjMatrix arcs; /邻接矩阵 int vexnum,arcnum; /图的当前节点数和弧数 MGraph; typedef
4、 struct Pnode /用于普利姆算法 char adjvex; /节点 double lowcost; /权值 Pnode,ClosedgeMAX_VERTEX_NUM;/记录顶点集U到V-U的代价最小的边的辅助数组定义 typedef struct Knode/用于克鲁斯卡尔算法中存储一条边及其对应的2个节点 char ch1; /节点1 char ch2; /节点2 double value;/权值 Knode,DgevalueMAX_VERTEX_NUM; 2、求解算法采用Prim算法和Kruskal算法。（1）普里姆算法(Prim)算法普里姆算法(Prim)算法是一种构造性算法
5、，生成最小生成树的步骤如下：初始化U=v。以v到其他顶点的所有边为候选边。重复一下步骤(n-1)次，使得其他(n-1)个顶点被加入到U中。从候选边中挑选权值最小的边加入TE，设该边在VU中的顶点是vk，将顶点vk加入到U中;考察当前VU中的所有顶点vj ，修改候选边：若(vk,vj)的权值小于原来和vj关联的候选边，则用(vk,vj)取代后者作为候选边。 开始标志顶点1加入U集合寻找满足边的一个顶点在U,另一个顶点在V的最小边形成n-1条边的生成树顶点k加入U修改由顶点k到其他顶点边的权值结束得到最小生成树（2）克鲁斯卡尔(Kruskal)算法克鲁斯卡尔(Kruskal)算法是一种按权值的递增
6、次序选择合适的边来构造最小生成树的方法。假设G=(V,E)是一个具有n个顶点的带权连通无向图，T=(U,TE)是G的最小生成树，则构造最小生成树的步骤如下：置U的初值等于V（即包含有G中的全部顶点），TE的初值为空集（即图T中每一个顶点都构成一个分量）。将图G中的边按权值从小到大的顺序依次选取：若选取的边未使生成树T形成回路，则加入TE，否则舍弃，直到TE中包含(n-1)条边为止。3、使用的函数int CreateUDG(MGraph & G,Dgevalue & dgevalue); int LocateVex(MGraph G,char ch); int Minimum(MGraph G,
7、Closedge closedge); void MiniSpanTree_PRIM(MGraph G,char u); void Sortdge(Dgevalue & dgevalue,MGraph G); void Adjacency_Matrix(MGraph G);void Adjacency_List(MGraph G,Dgevalue dgevalue);函数之间的调用关系图：CreateUDG()main()Adjacency_Matrix()Adjacency_List()MiniSpanTree_KRSL()MiniSpanTree_PRIM()locateVex()loca
8、teVex()Minimum()locateVex()Sortdge()五、 程序代码#include #include #include #define MAX_VERTEX_NUM 20 #define OK 1 #define ERROR 0 #define MAX 1000 typedef struct Arcell double adj; Arcell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct char vexsMAX_VERTEX_NUM; /节点数组 AdjMatrix arcs; /邻接矩阵 int vexnum
9、,arcnum; /图的当前节点数和弧数 MGraph; typedef struct Pnode /用于普利姆算法 char adjvex; /节点 double lowcost; /权值 Pnode,ClosedgeMAX_VERTEX_NUM;/记录顶点集U到V-U的代价最小的边的辅助数组定义 typedef struct Knode/用于克鲁斯卡尔算法中存储一条边及其对应的2个节点 char ch1; /节点1 char ch2; /节点2 double value;/权值 Knode,DgevalueMAX_VERTEX_NUM; int CreateUDG(MGraph & G,D
10、gevalue & dgevalue); int LocateVex(MGraph G,char ch); int Minimum(MGraph G,Closedge closedge); void MiniSpanTree_PRIM(MGraph G,char u); void Sortdge(Dgevalue & dgevalue,MGraph G); void Adjacency_Matrix(MGraph G);void Adjacency_List(MGraph G,Dgevalue dgevalue);int CreateUDG(MGraph & G,Dgevalue & dgev
11、alue)/构造无向加权图的邻接矩阵 int i,j,k; coutG.vexnumG.arcnum; cout请输入各个城市名称(分别用一个字符代替)：; for(i=0;iG.vexsi; for(i=0;iG.vexnum;+i)/初始化数组 for(j=0;jG.vexnum;+j) G.arcsij.adj=MAX; cout请输入两个城市名称及其连接费用(严禁连接重复输入!)：endl; for(k=0;k dgevaluek.ch1 dgevaluek.ch2 dgevaluek.value; i = LocateVex(G,dgevaluek.ch1); j = LocateV
12、ex(G,dgevaluek.ch2); G.arcsij.adj = dgevaluek.value; G.arcsji.adj = G.arcsij.adj; return OK; int LocateVex(MGraph G,char ch) /确定节点ch在图G.vexs中的位置 int a ; for(int i=0; iG.vexnum; i+) if(G.vexsi = ch) a=i; return a; void Adjacency_Matrix(MGraph G) /用邻接矩阵存储数据int i,j;for(i=0; iG.vexnum; i+) for(j=0; jG.vexnum; j+) if(G.arcsij.adj=MAX)cout0 ; elsecoutG.arcsij.adj ; coutendl; void Adjacency_List(MGraph G,Dgeva
