最小生成树问题课件.doc

。 榆林学院12届课程设计 最小生成树问题课程设计说明书 学生姓名： 赵佳 学 号： 1412210112 院 系： 信息工程学院 专 业： 计算机科学与技术 班 级： 计14本1 指导教师： 答辩时间： 年 月 日 最小生成树问题一、 问题陈述最小生成树问题设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。二、 需求分析1. 在n个城市之间建设网络，只需保证连通即可。2. 求城市之间最经济的架设方法。3.采用多种存储结构，求解算法也采用多种。三、 概要设计1、 功能模块图开始创建一个图功能选择1.建立邻接矩阵2.建立邻接表3.kruskal算法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,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct char vexsMAX_VERTEX_NUM; /节点数组 AdjMatrix arcs; /邻接矩阵 int vexnum,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; 2、求解算法采用Prim算法和Kruskal算法。（1）普里姆算法(Prim)算法普里姆算法(Prim)算法是一种构造性算法，生成最小生成树的步骤如下：初始化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)算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。假设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,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()locateVex()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,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,Dgevalue & 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 & dgevalue)/构造无向加权图的邻接矩阵 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 = LocateVex(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,Dgevalue dgevalue) /用邻接表储存数据int i,j;for(i=0;iG.vexnum;i+)coutG.vexsi;for(j=0;jG.arcnum;j+)if(dgevaluej.ch1=G.vexsi&dgevaluej.ch2!=G.vexsi)coutdgevaluej.ch2;else if(dgevaluej.ch1!=G.vexsi&dgevaluej.ch2=G.vexsi)coutdgevaluej.ch1;coutbb endl;void MiniSpanTree_KRSL(MGraph G,Dgevalue & dgevalue)/克鲁斯卡尔算法求最小生成树 int p1,p2,i,j; int bjMAX_VERTEX_NUM; /标记数组 for(i=0; iG.vexnum; i+) /标记数组初始化 bji=i; Sortdge(dgevalue,G);/将所有权值按从小到大排序 for(i=0; iG.arcnum; i+) p1 = bjLocateVex(G,dgevaluei.ch1); p2 = bjLocateVex(G,dgevaluei.ch2); if(p1 != p2) cout 城市dgevaluei.ch1与城市dgevaluei.ch2连接。endl; for(j=0; jG.vexnum; j+) if(bjj = p2) bjj = p1; void Sortdge(Dgevalue & dgevalue,MGraph G)/对dgevalue中各元素按权值按从小到大排序 int i,j; double temp; char ch1,ch2; for(i=0; iG.arcnum; i+) for(j=i; j dgevaluej.value) temp = dgevaluei.value; dgevaluei.value = dgevaluej.value; dgevaluej.value = temp; ch1 = dgevaluei.ch1; dgevaluei.ch1 = dgevaluej.ch1; dgevaluej.ch1 = ch1; ch2 = dgevaluei.ch2; dgevaluei.ch2 = dgevaluej.ch2; dgevaluej.ch2 = ch2; void MiniSpanTree_PRIM(MGraph G,char u)/普里姆算法求最小生成树 int i,j,k; Closedge closedge; k = LocateVex(G,u); for(j=0; jG.vexnum; j+) /辅助数组初始化 if(j != k) closedgej.adjvex = u; closedgej.lowcost = G.arcskj.adj; closedgek.lowcost = 0; for(i=1; iG.vexnum; i+) k = Minimum(G,closedge); cout 城市closedgek.adjvex与城市G.vexsk连接。endl; closedgek.lowcost = 0; for(j=0; jG.vexnum; +j) if(G.arcskj.adj closedgej.lowcost) closedgej.adjvex = G.vexsk; closedgej.lowcost= G.arcskj.adj; int Minimum(MGraph G,Closedge closedge) /求closedge中权值最小的边，并返回其顶点在vexs中的位置 int i,j; double k = 1000; for(i=0; iG.vexnum; i+) if(closedgei.lowcost != 0 & closedgei.lowcost k) k = closedgei.lowcost; j = i; return j; void main() MGraph G; Dgevalue dgevalue; CreateUDG(G,dgevalue); char u; cout图创建成功。; cout请根据如下菜单选择操作。n; cout1、用邻接矩阵存储：endl; cout2、用邻接表存储：endl; 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); break; ca