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

算法设计与分析——贪心法求最小生成树 一．问题描述 1.可以用连通网来表示n个城市间可能设置的通信网络，其中网的顶点表示城市，边表示两城市之间的路线，边的权值表示相应的费用。 对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，我们要选择这样一棵生成树，它使总的费用最少，这棵树就是最小生成树。一棵生成树的费用就是树上各边的费用之和。 2.本程序的目的是要建设一个最经济的通信网，根据用户输入的网，输出相应的最小生成树。在这里城市以及两城市之间的费用都用整型数来代替。 3．程序执行的命令包括： （1）利用克鲁斯卡尔算法求最小生成树。 （2）构造最小生成树中的连通分量。 （3）权值应存放在定义的数组中。 （4）输入城市个数。 （5）输出费用最少的生成树。 （6）结束。 4．测试数据 用户自定义输入城市个数，输入结束后回车即显示生成的最小生成树及最小开销。 二．概要设计 1：抽象数据类型MFSet的定义： ADT MFSet { 数据对象 ：若设S是MFSet型的集合，则它由n(n0)个子集Si（i = 1,2...,n）构成，每个子集的成员代表在这个子集中的城市。 数据关系 ： S1 U S2 U S3 U... U Sn = S, Si包含于S（i = 1,2,...n） Init (n): 初始化集合，构造n个集合，每个集合都是单成员，根是其本身。rank数组初始化0 Find(x):查找x所在集合的代表元素。即查找根，确定x所在的集合，并路径压缩。 Merge(x, y):检查x与y是否在同一个集合，如果在同一个集合则返回假，否则按秩合并这两个集合并返回真。 2：主程序： int main() { 初始化； while (条件) { 接受命令; 处理命令; } return 0; } 3：抽象数据类型 图 的定义如下： 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的意义或信息 } 4：抽象数据类型 树 的定义如下： ADT Tree{ 数据对象D:D是具有相同特性数据元素的集合。 数据关系R：若D为空集，则称为空树； 若D仅含一个元素数 据， 则R为空集，否则R={H}，H是如下二元关系： （1）在D中存在唯一的称为根的数据元素root，它在关系H 下无前驱； （2）若D-{root}≠，则存在D-{root}的一个划分D1，D2，…，Dm（m0），对任意j≠k（1≤j,k≤m）有Dj∩Dk=，且对任意的I（1≤i≤m），惟一存在数据元素xi∈Di有root，xi∈H； （3）对应于D-{root}的划分，H-{root，x1，…，roor，xm}有惟一的一个划分H1，H2，…，Hm（m＞0），对任意j≠k(1≤j，k≤m)有Hj∩Hk=，且对任意I（1≤i≤m），Hi是Di上的二元关系，（Di，{Hi}）是一棵符合本定义的树，称为跟root的子树。 5:本程序包括两个模块，调用关系比较简单： （1）主程序模块 （2）带权无向图模块。 程序各模块之间的调用关系如下： 三．详细设计 #include cstdio #include ctime #include algorithm using namespace std; #define MOD 101 #define MAXN 30 int set[MAXN]; int rank[MAXN]; typedef struct Mintree {//最小生成树结构体定义 int x, y; int dis; }Mintree; Mintree map[MAXN], mst[MAXN]; bool cmp(const Mintree a,const Mintree b) { return a.dis b.dis; }//快排比较函数 void Init(int n) {//初始化为n个集合 int i; for (i = 0; i n; i++) { set[i] = i; rank[i] = 0; } } int Find(int x) {//查找该集合的根 int