最小生成树问题课件

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

2、写入的数据创建成一个图。(2)Switch()功能选择：给用户提示信息，让用户选择相应功能。问题陈述最小生成树问题需求分析( 3) Adjacency_Matrix() 建立邻接矩阵：将用户输入的数据整理成邻接矩阵并显现在屏幕上。( 4) Adjacency_List() 建立邻接表：将用户输入的数据整理成临接表并显现在屏幕上。( 5) MiniSpanTree_KRSL()kruskal 算法：利用 kruskal 算法求出图的最小生成树，即：城市之间最经 济的连接方案。( 6) MiniSpanTree_PRIM()PRIM 算法：利用 PRIM 算法求出图的最小生成树，即：城市之间最经济

3、的连 接方案。四、 详细设计本次课程设计采用两种存储结构以及两种求解算法。 1、两种存储结构的存储定义如下： typedef struct Arcelldoubleadj; Arcell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef structchar vexsMAX_VERTEX_NUM; / 节点数组 AdjMatrix arcs; / 邻接矩阵 intvexnum,arcnum; / 图的当前节点数和弧数 MGraph; typedef struct Pnode / 用于普利姆算法 char adjvex; / 节点 double low

4、cost; / 权值Pnode,ClosedgeMAX_VERTEX_NUM;记录顶点集 U到 V-U的代价最小的 边的辅助数组定义typedef struct Knode/ 用于克鲁斯卡尔算法中存储一条边及其对应的 2 个节点char ch1; /节点 1char ch2; /节点 2double value;/ 权值 Knode,DgevalueMAX_VERTEX_NUM;2、求解算法采用 Prim 算法和 Kruskal 算法(1)普里姆算法(Prim)算法普里姆算法(Prim)算法是一种构造性算法，生成最小生成树的步骤如下： 初始化U=v。以 v 到其他顶点的所有边为候选边。重复一下

5、步骤(n-1)次，使得其他(n-1)个顶点被加入到 U 中。1从候选边中挑选权值最小的边加入 TE,设该边在 V U 中的顶点是 vk, 将顶点 vk 加入到 U 中；2考察当前 V U 中的所有顶点 vj ，修改候选边：若(vk,vj)的权值小于 原来和vj 关联的候选边，则用(vk,vj)取代后者作为候选边。(2)克鲁斯卡尔(Kruskal)算法克鲁斯卡尔(Kruskal)算法是一种按权值的递增次序选择合适的边来构造 最小生成树的方法。假设 G=(V,E)是一个具有 n 个顶点的带权连通无向图， T=(U,TE)是 G的最小生成树，则构造最小生成树的步骤如下：置 U 的初值等于 V (即包

6、含有 G 中的全部顶点)，TE 的初值为空集(即图 T 中每一个顶点都构成一个分量)。将图 G 中的边按权值从小到大的顺序依次选取：若选取的边未使生成树T形成回路，则加入 TE,否则舍弃，直到 TE 中包含(n-1)条边为止。3、使用的函数int CreateUDG(MGraph & GQgevalue & dgevalue);int LocateVex(MGraph G,char ch);int Mi nimu m(MGraph G,Closedge closedge);void Min iSpa nTree_PRIM(MGraph G,char u);void Sortdge(Dgeval

7、ue & dgevalue,MGraph G);void Adjace ncy_Matrix(MGraph G);void Adjace ncy_List(MGraph GQgevalue dgevalue);函数之间的调用关系图:五、程序代码#i nclude#i nclude#i nclude#defi ne MAX_VERTEX_NUM 20#defi ne OK 1#defi ne ERROR 0#defi ne MAX 1000typedef struct Arcelldouble adj;Arcell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;ty

8、pedef structchar vexsMAX_VERTEX_NUM; / 节点数组 AdjMatrix arcs; / 邻接矩阵in t vex nu m,arcnum; /图的当前节点数和弧数MGraph;typedef struct Pnode / 用于普利姆算法char adjvex; / 节点double lowcost; / 权值Pnode,ClosedgeMAX_VERTEX_NUM;记录顶点集 U 到 V-U 的代价最小的边的 辅助数组定义typedef struct Knode/ 用于克鲁斯卡尔算法中存储一条边及其对应的 2 个节点char ch1; /节点 1char c

9、h2; /节点 2double value;/ 权值 Knode,DgevalueMAX_VERTEX_NUM;int CreateUDG(MGraph & G,Dgevalue & dgevalue); int LocateVex(MGraph G,charch);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 Adjace

10、ncy_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 dgeva

11、luek.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 Adja

12、cency_Matrix(MGraph G) / 用邻接矩阵存储数据int i,j;for(i=0; iG.vexnum; i+)for(j=0; jG.vexnum; j+) if(G.arcsij.adj=MAX) cout0 ;else coutG.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&dgev

13、aluej.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);/ 将所有权值按从小到

14、大排序 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;

15、 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,

16、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.lo

17、wcost = 0;for(j=0; jG.vexnum; +j)if(G.arcskj.adj closedgej.lowcost) closedgej.adjvex = G.vexsk; closedgej.lowcost= G.arcskj.adj;int Minimum(MGraphG,Closedge closedge) / 求 closedge 中权值最小的边， 并返回其顶点在 vexs 中的位置int i,j;double k = 1000;for(i=0; iG.vexnum; i+)if(closedgei.lowcost != 0 & closedgei.lowcost k

18、)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; case 4: cout 普里姆算法最经济的连接方案为 :endl; coutu;MiniSpanTree_PRI