




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、kruskal算法求最小生成树课题:用kruskal算法求最小生成树。编译工具:Visual Studio 2017kruskal算法基本思想:先构造一个只含 n个顶点、而边集为空的子图,把子图中各个顶点看成各棵树上的根结点,之后,从网的边集E中选取一条权值最小的边,若该条边的两个顶点分属不同的树,也即则将其加入子图,即把两棵树合成一棵树,反之,若该条边的两个顶点已落在同一棵树上, 则不可取,而应该取下一条权值最小的边再试之。依次类推,直到森林中只有一棵树,子图中含有n-1条边为止。问题:按如下连通图用kruskal算法求最小生成树。程序源码:#include #include using n
2、amespace std;const int N = 100;int nodesetN;int n, m;struct Edge /int u;int v;int w;eN*N;bool comp(Edge x, Edge y) /return x.w y.w;void Init(int n) /for (int i = 1; i = n; i+)nodeseti = i;int Merge(int a, int b)/int p = nodeseta;/p定义结构体配合 sort() 方法对权值进行升序对集合号 nodeset 数组进行初始化将 ei.u 结点传递给 a; ei.v 结点传递
3、给 b.为 a 结点的集结号,int q = nodesetb;/q为 b 结点的集结号if (p = q) return 0;/判断结点间是否回环。若两个结点的集结号相同,则不操作,直接返回。for (int i = 1; i = n; i+)/ 是 q 的改为 p.if (nodeseti = q)nodeseti = p;return 1;int Kruskal(int n)int ans = 0;若两个结点的集结号不相同,检查所有结点,把集合号for (int i = 1; i=m; i+)if (Merge(ei.u, ei.v)cout A 结点:vv ei.u B 结点: ei.
4、v endl; / 各结点ans += ei.w;n-;if (n = 1)return ans;return 0;输出满足条件的int main() cout 输入总结点数(n)和总边数(m) : n m;In it (n);cout 输入结点数(u),(v) 和权值(w) : endl;for (i nt i = 1; i ei.u ei.v ei.w;sort(e+1, e + m+1, comp);int ans = Kruskal( n);cout 最小的花费是: ans endl;return 0;源码流程解析:(1)在ma in ()中,输入结点数 n与边m n=7, m=12在
5、In it (n) 中,对nodeseti 进行初始化。下标i1234567集合号1234567(3)使用sort ()方法按权值进行升序排序。eiuvwe1372e2124e3354e4564e5576e6677e7168e8238e9349e104510e112611e122714调用 kruskal(n)方法,(n=7,m=12)。for (i nt i = 1; i=m; i+)if (Merge(ei.u, ei.v)/调用 int Merge(int a, int b)方法cout A 结点: ei.u B 结点: ei.v endl;ans += ei.w;n-;if (n =
6、1)retur n ans;return 0;int Merge(int a, int b)/int p = nodeseta;/pint q = nodesetb;/qif (p = q) return 0;/则不操作,直接返回。for (int i = 1; i = n; i+)/ 是 q 的改为 p.if (nodeseti = q)nodeseti = p;将 ei.u 结点传递给 a; ei.v 结点传递给 b.为 a 结点的集结号,为 b 结点的集结号 .判断结点间是否回环。若两个结点的集结号相同,若两个结点的集结号不相同,检查所有结点,把集合号return 1;(5)示意图分析abno desetano desetbPq373737121212353535563636573333673333161313231111341414no desetiansn12345632611345632+4511343632+4+4411343332+4+4+43回环,直接返回回环,直接返回11141 1 12+4+4+4+82回环,直接返回11111112+4+4+4+8+9=311e4/10(6)输出结果当n=1时,退出循环,程序结束8e3424e7
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 成都2025上半年四川成都市新都区所属事业单位招聘45人笔试历年参考题库附带答案详解-1
- 保定河北保定市中医院招聘工作人员30人笔试历年参考题库附带答案详解-1
- 口腔护士转正述职报告
- 酒吧助理工作总结
- 2021-2022学年云南省曲靖市罗平县二中高二下学期期中语文试题
- 猜一猜:面塑艺术
- 数学人教版 一年级上学期期中测试卷1(含答案)
- 赢销截拳道培训
- 恒力集团可降解塑料制品的市场推广障碍突破
- 2019年奥迪a3车辆使用说明书
- 品味美好情感教学课件-2024-2025学年统编版道德与法治七年级下册
- 第二单元 焕发青春活力 大单元教学设计-2024-2025学年统编版道德与法治七年级下册
- 共赢未来餐饮行业合作新篇
- 2025年江苏农林职业技术学院单招职业适应性考试题库及参考答案1套
- 2025年辽宁省交通高等专科学校单招职业倾向性测试题库汇编
- 2025年陕西延长石油集团有限责任公司招聘笔试参考题库含答案解析
- 三八妇女节模板
- 10kV配电站房工程施工方案与技术支持
- 2024上海市招聘社区工作者考试题及参考答案
- 《招标投标法》考试题库200题(含答案)
- 《求职与面试技巧》课件
评论
0/150
提交评论