《离散数学课外实验--最小生成树问题(2)》

《《离散数学课外实验--最小生成树问题(2)》》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《离散数学课外实验》学班级姓名华杜电力大嗲叙理嗲呢2013年6用目录1.32.分析及设计思路43.结构类型定义44.、源65.运行结果及调试分析81.问题描述我们设想要建筑一个连接若干城市的铁路网，己知建造直接连接城市V,.与~的干线费用为试设计一个铁路网，以使建筑总费用达到最小。将每个城市看成权图中一点，令~为权图中任意两点vy,v/构成的边（v,.，vJ所带的权。显然，这个问题是在权图中求一个带权总和最小的连通支撑图。又因为权代表费用，为非负。因此，这一带有最小权的支撑子图中没有回路，即这个子阁必

2、是阁G的支撑树。定义：生成树（支撑树）：设G为连通网（带权连通图），具有G的所有顶点个）II只有n-1条边的连通子网。树的权：生成树r的各边的权值总和。最小生成树（最小支撑树、最优树）：权值最小的生成树。上述建筑铁路网的问题就是求一个权图中的最优树问题。O.SanRapheal1.Cross2.DalyCit6.CrossB11.CrossC9,l)ublin15.Cupcrtin16.SanJose2.分析及设计思路算法一：Prim算法(贪心算法)设g=(v，£)为连通网，r=((/，r£)为其对应

3、的最小生成树，从v()开始构造。(1)开始时，U={u()=v()},=夕。(2)找到满足vveZg/"(w，v)=rninlvveZg/WwpwJe(/,gV-l/J的边，把它并入re屮，v同时并入t/。(3)反复执行(2)，直到=/时，终止算法。算法二：Kruskar算法设G=(V，£)为连通网，r为其对疲的最小生成树。(1)初始时t=即r中没有边，只有n个顶点，就是z?个连通分量。(2)在£中选择权值最小的边并将此边从£中删除。(3)如果V在r的不同的连通分量中，则将h，v；)加入到r中，从而

4、导致r中减少一个连通分量。(4)反复执行(2)(3)直到r中仅剩一个连通分量时，终止操作。3.结构类型定义对生成树结点的封装：namespaceNonUnearStruct{III〈summary>///虫成树结点的抽象数据类型III〈/summary〉publicclassSpanTreeNode{privatestringselfNcime;privatestringparentName;privatedoubleweight:III〈summary〉///获取或设置结点本身的名称III〈/sum

5、mary〉publicstringSelfNamegetreturnselfName;set{selfName=value;}}///〈summary〉///获取或设罝结点双亲的名称///〈/summary〉publicstringParentName{get{returnparentName;}set{parentNcime=value;}}///〈summary〉///获取或设置边的权值IIIpublicdoubleWeight{get{returnweight;}set{we

6、ight=value;}}///〈summary〉III构造SpanTreeNode实例III〈/summary〉publicSpanTreeNode0{selfName=string.Empty;parentName=string.Empty;weight=0.0;}III〈summary〉///构造SpanTreeNode劣例III〈/summary〉III〈paramname二〃selI‘Name〃>结点本身的名称///结点双系的名

7、称〈/param>///边的权值〈/param〉publicSpanTreeNode(stringselfName,stringparentName,doubleweight){this.selfNcime=selfNcime;this.parentName=parentName;this,weight=weight;辅助结构的构造:namespaceNonLinearStruct{III〈summary〉///鉍小生成树辅助结构IIIint

8、ernalstructAidpublicdoubleLowCost;publicintVcrtcxlndcx;最小生成树Prim算法封装:III///得到连通网的最小z:l:成树III〈/summary〉III〈returns〉连通M的/ti小生成树〈/returns〉publicSpcinTreeNode[IMiniSpcinTree(stringvNcime){Span