欢迎来到天天文库
浏览记录
ID:29217029
大小:37.00 KB
页数:6页
时间:2018-12-17
《算法设计与分析报告-贪心法求最小生成树》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、实用标准文案算法设计与分析——贪心法求最小生成树一.问题描述1.可以用连通网来表示n个城市间可能设置的通信网络,其中网的顶点表示城市,边表示两城市之间的路线,边的权值表示相应的费用。对于n个顶点的连通网可以建立许多不同的生成树,每一棵生成树都可以是一个通信网。现在,我们要选择这样一棵生成树,它使总的费用最少,这棵树就是最小生成树。一棵生成树的费用就是树上各边的费用之和。2.本程序的目的是要建设一个最经济的通信网,根据用户输入的网,输出相应的最小生成树。在这里城市以及两城市之间的费用都用整型数来代替。3.程序执行的命令包括:(1)利用克鲁斯卡尔算法求最小生成树。(2)构造最小生成树中的连通
2、分量。(3)权值应存放在定义的数组中。(4)输入城市个数。(5)输出费用最少的生成树。(6)结束。4.测试数据用户自定义输入城市个数,输入结束后回车即显示生成的最小生成树及最小开销。二.概要设计1:抽象数据类型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所在集合的代表元
3、素。即查找根,确定x所在的集合,并路径压缩。Merge(x,y):检查x与y是否在同一个集合,如果在同一个集合则返回假,否则按秩合并这两个集合并返回真。2:主程序:intmain(){初始化;while(条件){接受命令;处理命令;精彩文档实用标准文案}return0;}3:抽象数据类型图的定义如下:ADTGraph{数据对象V:V是具有相同特性的数据元素的集合,成为顶点集。数据关系R:R={VR}VR={
4、v,w∈V且P(v,w),表示从v到w的弧,谓词P(v,w)定义了弧的意义或信息}4:抽象数据类型树的定义如下:ADTTree{数据对象D:D是具有相同
5、特性数据元素的集合。数据关系R:若D为空集,则称为空树;若D仅含一个元素数据,则R为空集,否则R={H},H是如下二元关系:(1)在D中存在唯一的称为根的数据元素root,它在关系H下无前驱;(2)若D-{root}≠,则存在D-{root}的一个划分D1,D2,…,Dm(m>0),对任意j≠k(1≤j,k≤m)有Dj∩Dk=,且对任意的I(1≤i≤m),惟一存在数据元素xi∈Di有∈H;(3)对应于D-{root}的划分,H-{,…,}有惟一的一个划分H1,H2,…,Hm(m>0),对任意j≠k(1≤j,k≤m)有Hj∩Hk=,且对
6、任意I(1≤i≤m),Hi是Di上的二元关系,(Di,{Hi})是一棵符合本定义的树,称为跟root的子树。5:本程序包括两个模块,调用关系比较简单:(1)主程序模块(2)带权无向图模块。程序各模块之间的调用关系如下:主程序模块带权无向图模块三.详细设计#include#include#include精彩文档实用标准文案usingnamespacestd;#defineMOD101#defineMAXN30intset[MAXN];intrank[MAXN];typedefstructMintree{//最小生成树结构体定义intx,y
7、;intdis;}Mintree;Mintreemap[MAXN],mst[MAXN];boolcmp(constMintreea,constMintreeb){returna.dis8、ge(intx,inty)精彩文档实用标准文案{//合并集合函数intfx=Find(x);intfy=Find(y);if(fx!=fy){//两端点不在一个集合,合并并返回真if(rank[fx]>rank[fy]){set[fy]=fx;}elseif(rank[fx]
8、ge(intx,inty)精彩文档实用标准文案{//合并集合函数intfx=Find(x);intfy=Find(y);if(fx!=fy){//两端点不在一个集合,合并并返回真if(rank[fx]>rank[fy]){set[fy]=fx;}elseif(rank[fx]
此文档下载收益归作者所有