算法设计与分析-贪心法求最小生成树

《算法设计与分析-贪心法求最小生成树》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、算法设计与分析——贪心法求最小生成树一.问题描述1・可以用连通网来表示n个城市间可能设置的通信网络，其中网的顶点表示城市，边表示两城市之间的路线，边的权值表示相应的费用。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，我们要选择这样一棵生成树，它使总的费用最少，这棵树就是最小生成树。一棵生成树的费用就是树上各边的费用之和。2.本程序的目的是要建设一个最经济的通信网，根据用户输入的网，输出相应的最小生成树。在这里城市以及两城市之间的费用都用整型数来代替。3.程序执行的命令包括：(1)利用克鲁斯卡尔算法求最小生成树

2、。(2)构造最小生成树中的连通分量。(3)权值应存放在定义的数组中。(4)输入城市个数。(5)输出费用最少的生成树。(6)结束。4•测试数据用户自定义输入城市个数，输入结束后回车即显示生成的最小生成树及最小开销。二.概要设计1：抽象数据类型MFSet的定义：ADTMFSet{数据对象:若设S是MFSet型的集合，则它由n(n>0)个子集Si(i=l,2...,n)构成，每个子集的成员代表在这个子集中的城市。数据关系:SIUS2US3U..・USn二S,Si包含于S(i=l,2,・・.n)Init(n):初始化集合，构造n个集合，每个集合都是单成员

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

4、v,wWV且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧3

5、,w>的意义或信息}4：抽象数据类型树的定义如下：ADTTree{数据对象D:D是具有相同特性数据元素的集合。数据关系R：若D为空集，则称为空树；若D仅含一个元素数据，则R为空集，否则R={H},H是如下二元关系：(1)在D中存在唯一的称为根的数据元素root,它在关系H下无前驱；(2)若D-{root}7^0),则存在D-{root}的一个划分Di,禺，・・・，几(m>0),对任意jHk(lWj,kWin)有DjflDk二①，且对任意的I(lWiWm),惟一存在数据元素x^Di有〈root,Xi〉WH；(3)对应于D-{root}的划分，H-{

6、〈root,xi>,…，0),对任意jHk(lWj,kWm)有比nHk=0,且对任意I(lWiWm),Hi是Di上的二元关系，(Di,{HJ)是一棵符合本定义的树，称为跟root的子树。5:本程序包括两个模块，调用关系比较简单：(1)主程序模块(2)带权无向图模块。程序各模块之间的调用关系如下：主程序模块V带权无向图模块一.详细设计#include#include#includeusingnamespacestd;#defineMOD10

7、1#delineMAXN30intset[MAXN];intrank[MAXN];typedefstructMintree｛〃最小生成树结构体定义intx,y;intdis;JMintree;Mintreemap[MAXNJ,mst[MAXNJ;boolcmp(constMintreea^constMintreeb)｛returna.dis

8、r=x;while(set[r]!=r)r=set[rj;inti=x,j;while(i!=r)｛j=set[i];set[i]=r;i=j；｝〃路径压缩returnr;boolMerge(intx,inty){〃合并集合函数intfx=Find(x);intfy=Find(y);if(fx!=fy){〃两端点不在一个集合，合并并返回真if(rank[fx]>rank[fy]){set[fyj=fx;}elseif(rank[fx]

9、turntrue;}returnfalse;〃两端点原本在一个集合，返回假。}intmain(){intn,i,j,k,num;intf