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

《克鲁斯卡尔算法求最小生成树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实用标准目录1.需求分析……………………………………………………………………………21.1设计题目……………………………………………………………………21.2设计任务及要求……………………………………………………………21.3课程设计思想………………………………………………………………21.4程序运行流程………………………………………………………………21.5软硬件运行环境及开发工具………………………………………………22.概要设计……………………………………………………………………………22.1流程图……………………………………

2、…………………………………22.2抽象数据类型MFSet的定义……………………………………………32.3主程序………………………………………………………………………42.4抽象数据类型图的定义…………………………………………………42.5抽象数据类型树的定义…………………………………………………53.详细设计……………………………………………………………………………73.1程序…………………………………………………………………………74.调试与操作说明……………………………………………………………………104.1测试结果……………

3、………………………………………………………104.2调试分析…………………………………………………………………115.课程设计总结与体会……………………………………………………………115.1总结…………………………………………………………………………115.2体会…………………………………………………………………………116.致谢………………………………………………………………………………127.参考文献…………………………………………………………………………12文案大全实用标准1.需求分析1.1设计题目：最小生成树1.2设计任

4、务及要求：任意创建一个图，利用克鲁斯卡尔算法，求出该图的最小生成树。1.3课程设计思想：Kruskal算法采用了最短边策略(设G=(V,E)是一个无向连通网，令T=(U，TE)是G的最小生成树。最短边策略从TE={}开始，每一次贪心选择都是在边集E中选择最短边(u,v)，如果边(u,v)加入集合TE中不产生回路，则将边(u,v)加入边集TE中，并将它在集合E中删去。)，它使生成树以一种任意的方式生长，先让森林中的树木随意生长，每生长一次就将两棵树合并，最后合并成一棵树。1.4程序运行流程:1)提示输入顶点数目；2)接受输入，按照项

5、目要求产生边权值的随机矩阵；然后求解最小生成树；3)输出最小生成树并且退出；1.5软硬件运行环境及开发工具：VC2.概要设计2.1流程图文案大全实用标准文案大全实用标准开始定义数据类型定义图定义树定义图的顶点数和边数Kruskal算法主程序图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):

6、初始化集合，构造n个集合，每个集合都是单成员，根是其本身。rank数组初始化0文案大全实用标准Find(x):查找x所在集合的代表元素。即查找根，确定x所在的集合，并路径压缩。Merge(x,y):检查x与y是否在同一个集合，如果在同一个集合则返回假，否则按秩合并这两个集合并返回真。}2.3主程序：intmain(){初始化；while(条件){接受命令;处理命令;}return0;}2.4抽象数据类型图的定义如下：ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，成为顶点集。数据关系R：R={VR}VR={

7、>

8、v，w∈V且P（v，w），表示从v到w的弧，谓词P（v，w）定义了弧的意义或信息}基本操作P：CreateGraph（&G，V，VR）；初始条件：V是图的顶点集，VR是图中弧的集合。操作结果：按V和的VR定义构造图G。DestoryGraph（&G）；文案大全实用标准初始条件：图G存在。操作结果：销毁图G。LocateVex（G，u）；初始条件：图G存在，u和G中是顶点有相同特征。操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。GetVex（G，v）；初始条件：图G存在，v是G中某个顶

9、点。操作结果：返回v的值。PutVex（&G，v，value）；初始条件：图G存在，v是G中某个顶点。操作结果：对V赋值value，FirstAdjVex（G，v）；初始条件：图G存在，v是G中某个顶点。操作结果：返回v的第一个邻接顶点。若顶点在G