克鲁斯卡尔算法求最小生成树.docx

目录 …………………………………………………………………………… 2 设计题目…………………………………………………………………… 2 设计任务及要求…………………………………………………………… 2 课程设计思想……………………………………………………………… 2 程序运行流程……………………………………………………………… 2 软硬件运行环境及开发工具……………………………………………… 2 …………………………………………………………………………… 2 流程图……………………………………………………………………… 2 抽象数据类型 MFSet 的定义…………………………………………… 3 主程序……………………………………………………………………… 4 抽象数据类型图的定义………………………………………………… 4 抽象数据类型树的定义………………………………………………… 5 …………………………………………………………………………… 7 程序………………………………………………………………………… 7 …………………………………………………………………… 10 测试结果…………………………………………………………………… 10 调试分析………………………………………………………………… 11 …………………………………………………………… 11 5 .1总结………………………………………………………………………… 11 体会………………………………………………………………………… 11 ……………………………………………………………………………… 12 ………………………………………………………………………… 12 1 设计题目: 最小生成树 设计任务及要求:任意创建一个图, 利用克鲁斯卡尔算法,求出该图的最小生成树。 课程设计思想: Kruskal 算法采用了最短边策略(设 G=(V,E) 是一个无向连通网,令 T=(U , TE) 是G 的最小生成树。最短边策略从 TE={} 开始,每一次贪心选择都是在边集 E 中选择最短边(u,v) ,如果边(u,v) 加入集合 TE 中不产生回路,则将边(u,v) 加入边集 TE 中,并将它在集合 E 中删去。) ,它使生成树以一种任意的方式生长,先让森林中的树木随意生长,每生长一次就将两棵树合并,最后合并成一棵树。 程序运行流程: 1)提示输入顶点数目; 2)接受输入,按照项目要求产生边权值的随机矩阵;然后求解最小生成树; 3)输出最小生成树并且退出; 软硬件运行环境及开发工具: VC 流程图 2 开始定义数据类型定义图定义树定义图的顶点数和边数 Kruskal 算法主程序图1 流程图 抽象数据类型 MFSet 的定义: ADT MFSet { 数据对象:若设 S是 MFSet 型的集合,则它由 n(n>0) 个子集 Si(i= 1,2...,n ) 构成,每个子集的成员代表在这个子集中的城市。数据关系: S1 U S2 U S3 U... U Sn = S, Si包含于 S(i= 1,2,...n ) Init (n): 初始化集合,构造 n个集合, 每个集合都是单成员,根是其本身。 ran k 数组初始化 0 Find(x): 查找 x所在集合的代表元素。即查找根,确定 x所在的集合,并路径压缩。 Merge(x, y): 检查 x与y 是否在同一个集合, 如果在同一个集合则返回假,否则按秩合并这两个集合并返回真。 3 } 主程序: int main() {初始化; while (条件){接受命令;处理命令;} return 0; } 抽象数据类型图的定义如下: ADT Graph{ 数据对象 V:V是具有相同特性的数据元素的集合,成为顶点集。数据关系 R: R={VR} VR={<v,w>|v ,w∈V且P(v,w),<v , w> 表示从 v 到w的弧,谓词 P(v,w)定义了弧<v , w> 的意义或信息} 基本操作 P: CreateGraph (&G ,V,VR ); 初始条件: V是图的顶点集, VR 是图中弧的集合。操作结果:按 V和的 VR 定义构造图 G。 DestoryGraph (&G ); 初始条件:图 G存在。操作结果:销毁图 G。 LocateVex (G,u); 初始条件:图 G存在, u和G中是顶点有相同特征。操作结果:若G中存在顶点