课程设计---克鲁斯卡尔算法求最小生成树

《课程设计---克鲁斯卡尔算法求最小生成树》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、课程设计报告课程名称：数据结构课程设计设计题目：克鲁斯卡尔算法求最小生成树系别：计算机系专业：组别：学生姓名：学号:起止日期:2011年6月29日~2011年7月6日指导教师:马强14目录1.需求分析……………………………………………………………………………21.1设计题目……………………………………………………………………21.2设计任务及要求……………………………………………………………21.3课程设计思想………………………………………………………………21.4程序运行流程:……………………………………………………

2、………21.5软硬件运行环境及开发工具………………………………………………22.概要设计……………………………………………………………………………22.1流程图………………………………………………………………………22.2抽象数据类型MFSet的定义………………………………………………32.3主程序………………………………………………………………………32.4抽象数据类型图的定义…………………………………………………42.5抽象数据类型树的定义…………………………………………………63.详细设计………………………………

3、……………………………………………83.1程序…………………………………………………………………………84.调试与操作说明……………………………………………………………………114.1测试结果……………………………………………………………………114.2调试分析……………………………………………………………………125.课程设计总结与体会………………………………………………………………125.1总结…………………………………………………………………………125.2体会……………………………………………………………………

4、……126.致谢…………………………………………………………………………………137.参考文献……………………………………………………………………………138.附录…………………………………………………………………………………14141.需求分析1.1设计题目：最小生成树1.2设计任务及要求：任意创建一个图，利用克鲁斯卡尔算法，求出该图的最小生成树。1.3课程设计思想：Kruskal算法采用了最短边策略(设G=(V,E)是一个无向连通网，令T=(U，TE)是G的最小生成树。最短边策略从TE={}开始，每一次贪心选择都是

5、在边集E中选择最短边(u,v)，如果边(u,v)加入集合TE中不产生回路，则将边(u,v)加入边集TE中，并将它在集合E中删去。)，它使生成树以一种任意的方式生长，先让森林中的树木随意生长，每生长一次就将两棵树合并，最后合并成一棵树。1.4程序运行流程:1)提示输入顶点数目；2)接受输入，按照项目要求产生边权值的随机矩阵；然后求解最小生成树；3)输出最小生成树并且退出；1.5软硬件运行环境及开发工具：VC2.概要设计2.1流程图14开始定义数据类型定义图Mgraphi==0定位定义图中的顶点数和边数Kruskal算法主

6、程序图1流程图2.2抽象数据类型MFSet的定义：ADTMFSet{数据对象：若设S是MFSet型的集合，则它由n(n>0)个子集Si（i=1,2...,n）构成，每个子集的成员代表在这个子集中的城市。数据关系：S1US2US3U...USn=S,Si包含于S（i=1,2,...n）Init(n):初始化集合，构造n个集合，每个集合都是单成员，根是其本身。rank数组初始化0Find(x):查找x所在集合的代表元素。即查找根，确定x所在的集合，并路径压缩。Merge(x,y):检查x与y是否在同一个集合，如果在同一个集

7、合则返回假，否则按秩合并这两个集合并返回真。}142.3主程序：intmain(){初始化；while(条件){接受命令;处理命令;}return0;}2.4抽象数据类型图的定义如下：ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，成为顶点集。数据关系R：R={VR}VR={v，w∈V且P（v，w），表示从v到w的弧，谓词P（v，w）定义了弧的意义或信息}基本操作P：CreateGraph（&G，V，VR）；初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和的V

8、R定义构造图G。DestoryGraph（&G）；初始条件：图G存在。操作结果：销毁图G。LocateVex（G，u）；初始条件：图G存在，u和G中是顶点有相同特征。操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。GetVex（G，v）；14初始条件：图G存在，v是G中某个顶点。操作结果：返回v的值。PutV