最小生成树实验报告.docx
《最小生成树实验报告.docx》由会员分享,可在线阅读,更多相关《最小生成树实验报告.docx(6页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上一、实验目的1. 通过上机程序,进一步加深对最小生成树的理解。2. 掌握Kruskal算法。3. 学会用程序解决离散数学中的问题。4. 增强我们编写程序的能力。二、实验内容求带权无向联通平面图的最小生成树三、实验环境我的实验依旧是在VC6.0实验环境下完成的,而所设计的程序也在这个环境下通过了编译,运行和测试。四、实验原理和实现过程利用Kruskal算法求最小生成树,原理如下:1. 选取最小权边e1,置边数j1.2. i=n-1结束,否则转c。3. 设已经选择的边为e1,e2,,ei,在G中选取不同于e1,e2,ei的边,使e1,e2,,ei,ei+1中无回路且ei+
2、1是满足此条件的最小边。4. ii+1,转b。根据这个,还有以下思路:由G生成的最小生成树T所包含的边的集合1按非降序权重将E中的边排序2建立n个单元素集(每个顶点一个)3最小生成树的边集合T初始为空4 .while |T|n-15. 令e(x,y)为E中的下一条边6. if包含x的集合不是与包含y的集合不是同一个集合 then7. 将e(x,y)加入到T8. 将包含x的集合和包含y的集合合并9. end if10.end while五、实验源代码及分析#includestruct Edgeint from, to, weight; /定义一个数据结构,存放点和边的关系以及边的权值 ;Edge
3、 edge100, temp; /用定义的数据结构来定义一个数组和一个变量 int i, j, n, m;int p100; int seek(int x) /用来找出当前端点所在集合编号 if(px=x) return x; else return px=seek(px);int Kruskal() int x, y,k=0; for(i=0;i100;i+) pi=i; for(i=0;im;i+) x=seek(edgek.from); /找出当前边两个端点所在集合编号 y=seek(edgek.to); if(x!=y) /如果在不同集合,合并 printf(%d, %d): %dn,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最小 生成 实验 报告
限制150内