2022年最小生成树问题 .pdf

榆林学院 12 届课程设计最小生成树问题课程设计说明书学生姓名 ：赵佳学号：1412210112 院系：信息工程学院专业：计算机科学与技术班级：计 14本 1 指导教师 ：答辩时间 ：年月日名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 13 页 - - - - - - - - - 最小生成树问题一、 问题陈述最小生成树问题设计要求：在 n 个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。二、 需求分析1. 在 n 个城市之间建设网络，只需保证连通即可。2. 求城市之间最经济的架设方法。3. 采用多种存储结构，求解算法也采用多种。三、 概要设计1、功能模块图2、功能描述（1) CreateUDG() 创建一个图： 通过给用户信息提示， 让用户将城市信息及城市之间的联系关系和连接权值写入程序，并根据写入的数据创建成一个图。（2) Switch() 开始创建一个图功能选择1. 建 立邻接 矩阵2. 建 立邻接表3.kruskal算法4. PRIM算法结束名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 13 页 - - - - - - - - - 功能选择：给用户提示信息，让用户选择相应功能。（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 算法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 13 页 - - - - - - - - - （1）普里姆算法 (Prim) 算法普里姆算法 (Prim) 算法是一种构造性算法，生成最小生成树的步骤如下：初始化 U=v。以 v 到其他顶点的所有边为候选边。重复一下步骤 (n-1) 次，使得其他 (n-1) 个顶点被加入到 U中。 1 从候选边中挑选权值最小的边加入TE ，设该边在 VU中的顶点是 vk，将顶点 vk 加入到 U中; 2 考察当前 VU中的所有顶点 vj ，修改候选边：若 (vk,vj)的权值小于原来和 vj 关联的候选边，则用 (vk,vj)取代后者作为候选边。（2）克鲁斯卡尔 (Kruskal)算法克鲁斯卡尔 (Kruskal)算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。假设G=(V,E)是一个具有n 个顶点的带权连通无向图，T=(U,TE)是 G的最小生成树，则构造最小生成树的步骤如下：置 U的初值等于 V（即包含有 G中的全部顶点），TE的初值为空集（即图T中每一个顶点都构成一个分量） 。将图 G中的边按权值从小到大的顺序依次选取：若选取的边未使生成树T形成回路，则加入TE ，否则舍弃，直到TE中包含 (n-1) 条边为止。开始标志顶点 1 加入 U 集合寻找满足边的一个顶点在U,另一个顶点在V 的最小边形成 n-1 条边的生成树顶点 k 加入 U 修改由顶点k 到其他顶点边的权值结束得到最小生成树名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 13 页 - - - - - - - - - 开始创建标记数组并初始化将所有权值按从小到大排序利用标记数组判断是否形成环是否扫描完全部线路输出权值最小线路形成最小生成树结束否是否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); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 13 页 - - - - - - - - - 函数之间的调用关系图：五、 程序代码#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 /用于普利姆算法 CreateUDG() main() Adjacency_Matrix() Adjacency_List() MiniSpanTree_KRSL() MiniSpanTree_PRIM() locateVex() locateVex() Minimum() locateVex() Sortdge() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 13 页 - - - - - - - - - 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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 13 页 - - - - - - - - - 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 ; 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&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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 13 页 - - - - - - - - - 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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 13 页 - - - - - - - - - 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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 13 页 - - - - - - - - - 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_PRIM(G,u); break; default: cout输入有误 !; break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 13 页 - - - - - - - - - coutendly; if(y=n) break; 六、 运行结果与测试七、 设计体会与总结通过本次课程设计， 我在程序设计中， 用邻接矩阵和邻接表这两种存储结构进行编程，且对 Prim 算法和 Kruskal 算法生成最小生成树有了一个初步的了解，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 13 页 - - - - - - - - - 同时也为日后的毕业设计打下了良好的基础。而且通过课程设计在下述各方面得到了锻炼：1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。2、提高程序设计和调试能力。通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。3、培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。在本次课程设计中，知道如何在 n 个城市之间建设网络， 只需保证连通即可，求最经济的架设方法。并且用了多种求解方式。这几天的课程设计让我充分地体会到了上机实践对于计算机编程的重要性。只顾学习理论是远远不够的。 实践中可以发现许许多多的问题，然后通过同学老师的帮助，得以解决，让自己的编程能力得到极大的提升。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 13 页 - - - - - - - - -