1 / 25
文档名称:

数据结构,最小生成树克鲁斯卡尔算法的实现.docx

格式:docx   大小:275KB   页数:25页
下载后只包含 1 个 DOCX 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

数据结构,最小生成树克鲁斯卡尔算法的实现.docx

上传人:459972402 2019/6/20 文件大小:275 KB

下载得到文件列表

数据结构,最小生成树克鲁斯卡尔算法的实现.docx

文档介绍

文档介绍:摘 要设计了一个用 C/C++编写程序实现克鲁斯卡尔最小生成树算法,该程序操作简单,界面清晰,易于为用户所接受 。关键词:克鲁斯卡尔,邻接矩阵,最小生成树, vc++。目 录1课题描述 12问题分析和任务定义 23逻辑设计 34详细设计 45程序编码 116程序调试与测试 177结果分析 198总结 20参考文献 21课题描述用C/C++编写程序实现克鲁斯卡尔最小生成树算法。 假设要在n个城市之间建立通讯联络网,则连通 n个城市只需要 n-1条线路。这是我们设计一个最小生成树的程序用来算出最节省经费的前提下建立这个通信站。1问题分析和任务定义假设连通网 N=(V,{E}),则令最小生成树的初始状态为只有 n个顶点而无边的非连通图 T=(V,{}),图中每个顶点自成一个连通分量。在E中选择代价最小的边,若该边依附的顶点落在 T中不同的连通分量上,则将此边加入到 T中,否则舍去此边而选择下一条代价最小的边。依次类推,直到 T中所有顶点都在同一连通分量上为止。2逻辑设计设计思想:采用邻接矩阵来存储图,然后采用克鲁斯卡尔算法求出最小生成树。结构体定义函数模块一函数模块二(图的创建)(求最小生成树)采用邻接矩阵做存储结构克鲁斯卡尔算法主函数引用函数模块一、二,实现算法设计1).定义结构体。2).采用邻接矩阵做存储结构创建图(函数模块一) 。3).采用克鲁斯卡尔算法求出该图的最小生成树(函数模块二) 。4).在主函数里面分别调用以上各个函数,最终实现设计目的。·函数CreateMGraph用来实现图的创建,以及图的相关信息的存储。图的存储采用邻接矩阵存储结构。·函数minitree_KRUSKAL用来求图的最小生成树。图的最小生成树有普利姆算法和克鲁斯卡尔算法可以实现,本段代码使用的是克鲁斯卡尔算法,这也是本题所要求使用的。·各个函数间的联系先调用函数 CreateMGraph实现图的创建,·在开始的时候添加一些限制条件方便函数的功能实现例如:#defineMaxVertexNum100 // 最大顶点个数#defineQueueSize30#defineM30·模块一:图的创建·结构体定义为:typedefstruct{VertexTypevexs[MaxVertexNum]; //顶点表Linkedges[MaxVertexNum][MaxVertexNum];// 图中当前的相连接的两个顶点intn,e; //图中当前的顶点数和边数}MGraph;·函数定义为:MGraphCreateMGraph(){4MGraphG;inti,j,k,ch3;charch1,ch2;printf(" 请输入该图的顶点数和边数 :\n");scanf("%d,%d",&(),&());printf(" 请输入该图的顶点信息:\n");for(i=1;i<=;i++){getchar();scanf("%c",&([i]));}for(i=1;i<=;i++)for(j=1;j<=;j++)[i][j].w=0;printf(" 请输入该图每条边对应的两个顶点的名:\n");for(k=1;k<=;k++){scanf("%c",&ch1);printf("请输入第%d条边的顶点序号:",k);scanf("%c%c",&ch1,&ch2);printf(" 请输入第%d条边的权值大小:",k);scanf("%d",&ch3);for(i=1;ch1!=[i];i++);for(j=1;ch2!=[j];j++);e[p].vexh=i;e[p].vext=j;e[p].weight=[i][j].w=ch3;//权值e[p].flag=0;p++;}returnG;}(),该图的存储结构是邻接矩阵,先对图的结构体进行定义,再进行初始化。在函数中需要手动输入图的参数(如顶点数、边数、顶点信息、相连接的顶点、边的权值等)用来建立图并且确定图的邻接矩阵。最后在完成图的信息输入即建立图以后输出图的邻接矩阵表。·模块二:求图的最小生成树。voidminitree_KRUSKAL(MGraph*G){inti,min,j,k;VEXt[M];for(i=1;i<=G->n;i++){t[i].data=G->vexs[i];t[i].jihe=i;}i=1;while(i<G->n){min=MaxVertexNum;for(j=0;j<G->e;j++){if(e[j].weigh

最近更新

2025年娄底职业技术学院单招职业倾向性测试题.. 62页

2025年人教版语文四年级下册第三单元测试基础.. 8页

2025年娄底职业技术学院单招职业适应性测试题.. 60页

2025年宁夏中 卫 市单招职业倾向性测试题库附.. 61页

经济新常态背景下我国企业经济管理的创新路径.. 3页

高温环境下材料抗腐蚀性研究-全面剖析 30页

绿色制造与衡器行业的可持续发展-全面剖析 29页

第7节重要功能因子 17页

分子美食技术在烹饪中的应用-第10篇-全面剖析.. 23页

产品质量检测合同书 6页

2025年宁夏固原地区单招职业适应性测试题库带.. 62页

2025年一种动物作文700字 3页

2025年宁夏工业职业学院单招职业技能测试题库.. 60页

2025年宁夏工业职业学院单招职业适应性测试题.. 61页

2025年人教版小学三年级语文下册期中考试题及.. 8页

2025年宁夏工商职业技术学院单招职业技能测试.. 62页

2025年现代经典美文段落摘抄加赏析 4页

纳米纤维素替代部分造纸法烟草基片中木浆纤维.. 3页

2025年宁夏建设职业技术学院单招职业技能测试.. 63页

2025年宁夏建设职业技术学院单招职业技能测试.. 63页

2025年牡丹江大学单招职业技能测试题库有完整.. 61页

违纪违法典型案例对照剖析材料 5页

2024中国邮政集团限公司甘肃省分公司校园招聘.. 246页

2024年贷款产品心得体会(精选9篇) 14页

汉字与中国文化复习笔记 44页

中医内科常见病诊疗指南(中华中医药学会) 3页

水彩画技法与赏析演示文稿 219页

古瑞瓦特逆变器说明书 2页

婺源徽派建筑 4页

回族的相关介绍-课件(PPT精) 45页