数据结构论文最小生成树

1、课题：最小生成树问题 任课老师：朱节中 专业：软件工程年级：2012级班级：1班学号：20122344001姓名：董上琦目录1. 设计题目2. 需求分析1）运行环境2）输入的形式和输入值的范围3）输出的形式描述4）功能描述5）测试数据3. 概要设计1）抽象数据类型定义描述.2）功能模块设计3）模块层次调用关系图4. 详细设计。实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法5. 调试分析。包括调试过程中遇到的问题及解决的方法、算法的时间空间复杂性分析、经验体会6. 用户使用说明。详细列出每一步的操作说明7. 测试结果8. 附录：程序设计源代码、设计题目1）.问题描述

2、在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储 结构采用多种。求解算法多种。2）.基本要求以邻接多重表存储无向带权图，利用克鲁斯卡尔算法或普瑞姆算法求网的最 小生成树。、需求分析1）运行环境软件在JDK运行，硬件支持windows系统2）输入的形式和输入值的范围自动生成顶点数据在1020之间；各个顶点之间权值在2550之间；通过程序 改动亦可生成已知顶点权值之间的最小生成树，需将随机生成代码改为edge edge=new edge（0,1,16）,new（0,2,18） ；将已知顶点、权值通过其函数输入再生成其所对应最小生成树。3）输出的形式描述输出随机生成顶点个数以及各个

3、顶点之间权值；然后输出本次生成顶点之间构成的最小生成树。4）功能描述该程序会自动生成介于1020个数顶点模拟各城市，再随机生成介于2550之间数值作为权值模拟各个城市间的距离，并同时生成此次顶点、权值相对应的最小生成树，模拟各城市间的最小距离，最小生成树。如有确定城市顶点及其权 值，则可改动程序令其不再随机生成顶点权值，在程序中输入如下代码：edge edge=new edge（0,1,16）,new（0,2,18） 输入数组为edge数组，edge （起点，终点，权值）。通过将随机生成代码改 动就可以生成该城市对应权值的最小生成树。5）测试数据生成数据之后检验生成顶点数值是否介于 1020之

4、间；检验各顶点间权值大 小是否介于2550间；同时检验其自动生成最小生成树是否正确。三、概要设计1）抽象数据类型定义描述定义排序类sort ,将各个顶点按照其两顶点之间权值大小排序，从大到小排 序，用到堆排序算法；定义带权值的边edge，分别存在start （起点）、end （终点）、value（权值） 三个变量；定义main类，调用sort、edge类与自身函数通过Kruskal函数实现最小生成 树。2）功能模块设计主函数随机生成1020个顶点作为城市并同时生成任意两顶点间 2550的权 值作为两城市距离；在界面输出随机生成顶点个数及任意两顶点间权值； 再调用 sort函数对权进行排序，按照

5、权值的大小有小到大排序；排序之后实现 Kruskal 函数，通过kruskal函数生成最小生成树；最后输出所生成的最小生成树。3）模块层次调用关系图sortvoid siftvoid sortedgeint stallint eudintalueA四、详细设计实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块 写出伪码算法。1. 定义带权值的边及其三个变量start(起点)、end (终点)、value (权值)；定义该属性为下边的根据权值排序、Kruskal实现最小生成树做下铺垫；函数实 现如下：package tree;public class sort public sta

6、tic void sift(edge a, int root, int limit)int i = root;int j = i*2+1;/j 为i的左孩子while (j <= limit) /沿较小值孩子节点向下筛选if (j < limit && aj.getValue() < aj + 1.getValue()数组元素比较j+;/j为左右孩子的较小者if (aj.getValue() > ai.getValue() /若父亲节点值较大edge e = ai;/孩子节点中较小值上移ai = aj;aj = e;i = j;j = i * 2 + 1

7、;/i、j 向下一层else break;/跳出循环public static void sort(edge data) int length = data.length;for (int i = length/2-1; i>=0; i-)创建最大堆sift(data, i, le ngth-1);for (int j = length - 1; j > 0; j-)每趟把最大值交换到后面字，再生成堆edge e = data0;data0 = dataj;dataj = e;sift(data, 0, j-1);2. 随机生成介于1020之间个顶点作为各个城市，并同时生成任意两顶

8、点间权 值，介于2550之间；每n个顶点之间最多生成n*(n-1)条边；生成vertexNumber-1 个row (行)和row-1个column (列)可以防止同一个顶点生成自环；函数实现如下：int vertexNumber=( int )(Math. random()+1)*10)；System. out .println(”随机生成"+vertexNumbe叶"个顶点");edge edges= n ewedgevertexNumber*(vertexNumber-1)/2;for (int row=0, index=0; row<vertexNu

9、mber; row+)/row 行、column列、index 数组for (int column=0; column<row; column+)int x=( int )(Math. random()+1)*25);/random随机的edgesi ndex =n ewedge(row, colu mn, x);System.out .println(”顶点"+row+"和"+column+"之间的距离为"+x);in dex+;3. 定义排序类sort，按照堆排序函数对数组edge按照权值大小从小到大进行排序（参照课本299页）;pa

10、ckage tree;public class sort public static void sift(edge a, int root, int limit)int i = root;int j = i*2+1;/j 为i的左孩子while (j <= limit) /沿较小值孩子节点向下筛选if (j < limit && aj.getValue() < aj + 1.getValue()数组元素比较j+;/j为左右孩子的较小者if (aj.getValue() > ai.getValue() /若父亲节点值较大edge e = ai;/孩子节点中

11、较小值上移ai = aj;aj = e;i = j;j = i * 2 + 1;/i、j 向下一层else break;/跳出循环public static void sort(edge data)int length = data.length;for (int i = length/2-1; i>=0; i-)/创建最大堆sift (data, i, length-1);for (int j = length - 1; j > 0; j-)/每趟把最大值交换到后面字,再生成堆edge e = dataO;dataO = dataj;dataj = e;sift (data, 0

12、, j-1);4.Kruskal方法实现最小生成树。Kruskal 方法与Prim方法都是基于最小生成树的 MS性质：设G(V,E)是一个 联通带权无向图，TV是顶点集合V的一个非空真子集。若(tv，v)包含于E是一 条权值最小的边，其中tv包含于TV, v包含于V-TV,则必定存在G的一棵最小生成 树T,T包含边(tv,v)。其Kruskal算法参照课本334页。其算法如下：int a = new int vertexNumber;/初始时刻，所有顶点的连通分量编号为-1，表示所有顶点都属于一个独立的连通分量for (int i = 0; i<a.length; i+) ai = -1

13、;edge result = n ewedgevertexNumber-1;/该数组用于记录最小生成树 int temp = 0;for (edge e : edges)int start = e.getStart(); int end = e.getEnd();if (astart=aend && aend=-1) astart = ae nd = temp; resulttemp = e; temp+; else if (astart != aend) if (astart = -1) astart = ae nd;else if (aend = -1) ae nd = a

14、start;else int t = astart;for (int i = 0; i < vertexNumber; i+) if (ai = t) ai = ae nd;resulttemp = e;temp+;五、调试分析包括调试过程中遇到的问题及解决的方法、算法的时间空间复杂性分析、 经验体会。Sort 排序类算法时间复杂度为O(log2n)，Kruskal算法时间复杂度为0(1); 调试过程中，Kruskal算法实现出现问题，刚开始无法实现该函数，无法生 成最小生成树；经请教同学、查看资料、查看课本解决问题。实现堆排序过程无 法实现，参考课本之后解得堆排序算法实现过程：调用si

15、ft ()方法n/2次，使得数据序列成为最大堆；对j=n-1，n-2.1 ，执行下列n-1次完成排序操作：交 换根end0和元素endj，调用sift ()方法将endj的前j个元素调整成最大 堆。在编程过程中如遇难题可对其题目进行认真分析，然后参考课本或者其他资料已现有代码亦或闻询他人帮助，在自己查询或者问询他人过程中也是自己学习 的过程，可以从中学习到很多知识。六、用户使用说明程序运行后会自动跳出1020个随机顶点作为各个城市，同时随机生成2550 的权值x，并生成此次所有顶点及其权值构成的最小生成树。七、测试结果1.生成0-12共13个顶点:随机生騎个顶点顶点二和0之间的距离笊K0 顶点

16、2和0之间的距离为2 § 顶点丄和二之间的距离芮丸, 顶点3和©之间的距离为北 顶点3和丄之闾的距离为30 顶点己和2之间的距离为处 顶点§和0之间的距离为24 顶点4和1之间的距禽为30 顶点弓和2之间的距离为2包 顶点4和勺之间的距离芮45 顶点5和0之间的距离为 顶点5和二之间的距离対20 顶点5和2之间的距离为£9 顶点5和3之闾的距离芮34 顶点5和4才间的距离为弓2 顶点宜和0之洵的距离为M5 顶虽和1之间的距离为3 5 顶点宕和2之间的距离为总总 顶点E和3之间的距离为弓4 顶点宜和4之间的距离为岂7 顶点E和5之间的距离为39 顶点：和。

17、之间的距离为3$ 顶点7和1之间的距离芮2丄 顶点：和2之间的距离为2 7 顶点丁和3之闾的距离対4巳 顶点7和弓之间的距离为弓专 顶点U和5之洵的距离対37顶点寸和£之间的延离黑H0 顶点£和0之间的距离为40 顶点总和丄之间的延离药2宜 顶点E和2之间的距离为30 顶点3和3之间的距离为3总 顶虽和理之间的距离为42 顶点2和5之间的距离为 顶点2和总之间的證离为堆7 顶点E和U之间的距陽为27 顶点9和0之间的涯离为30 顶点9和1之间的距离芮35 顶点9和丄之间的延离药叮 顶点9和3之间的距离为29 顶点勺和咗之间的延离药33 顶点9和5之冋的距离为25 顶点9和&

18、#163;之间的距离为23 顶点9*7 Z间的距离为29 顶点9和2之间的距离为处 顶点10和0之间的距离为32 顶点1G和1之闾的距离为弓总 顶点：0和2 Z间的距离为4 E 顶点工0和3之间的距离为35 顶点：0和4之闾的距廃対37 顶点10和5之间的距离为弓5 顶点：0和£之间的距离対27 顶点10和7之间的距离为日1 顶点丄0和3之闾的距盔为4二 顶点:和9之间的距离为432.生成最小生成树为：最小生咸树芮：连接顶点号和占该边的权值为25 连摟顶点2和0该边的权值为2方 连接顶点岂和丄该边的权值为2宜 连樓顶点7和2该边的权值为27 连接顶臣2和：该边的权值为丄丁 连接顶点丄

19、0和宜该边的权值为2 = 连摟顶点5和0该边的权值为27 连接顶点守和6该边的权值为2昌 连接顶点电和2该边的权值为 连接顶点今和3该边的权值芮2日程序随机自动生成介于1020之间个顶点正确运行，随机自动生成介于2550 之间权值正确运行，使得任意两顶点之间权值于 2550之间；经验证该生成树为 最小生成树，程序运行正确。最小生成树定义：设G是一个带权连通无向图，w（ e）是边e上的权，T是G 的生成树，T中各边的权值之和称为生成树T的权值或者代价（cost）。权值最小的生成树称之为最小生成树(minimumcost spanning tree ),简称最小生成树。八、程序设计源代码packa

20、ge tree;public class sort public static void sift(edge a, int root, int limit)int i = root;int j = i*2+1;/j 为i的左孩子while (j <= limit) /沿较小值孩子节点向下筛选if (j < limit && aj.getValue() < aj + 1.getValue()数组元素比较j+;/j为左右孩子的较小者if (aj.getValue() > ai.getValue() /若父亲节点值较大edge e = ai;/孩子节点中较小值

21、上移ai = aj;aj = e;i = j;j = i * 2 + 1;/i、j 向下一层else break;/跳出循环public static void sort(edge data)int length = data.length;for (int i = length/2-1; i>=0; i-)/创建最大堆sift (data, i, length-1);for ( int j = length - 1; j > 0; j-)每趟把最大值交换到后面字,再生成堆edge e = data0;data0 = dataj;dataj = e;sift (data, 0, j

22、-1);package tree;public class edge private int start, end, value;/定义开始、结束、权值public edge( int start, int end, int value)this .start=start;this .end=end;this .value=value;public int getStart() return start;public void setStart( int start) this .start = start;public int getEnd() return end;public void

23、setEnd( int end) this .end = end;public int getValue() return value;public void setValue( int value) this .value = value; package tree;public class mainpublic static void main(String args)int vertexNumber=( int )(Math. random()+1)*10); System. out .println(”随机生成"+vertexNumbe叶"个顶点");ed

24、ge edges= n ewedgevertexNumber*(vertexNumber-1)/2;for (int row=0, index=0; row<vertexNumber; row+) /row 行、column列、index 数组for (int column=0; column<row; column+)int x=( int )(Math. random()+1)*25);/random随机的edgesi ndex =n ewedge(row, colu mn, x);System.out .println(”顶点"+row+"和"+

25、column+"之间的距离为"+x);in dex+;sort. sort (edges);/ 对数组edges中的值进行堆排序 int a = new int vertexNumber;for (int i = 0; i<a.length; i+)/初始时刻，所有顶点的连通分量编号为 -1，表示所有顶点都属于 一个独立的连通分量ai = -1;ai的值表示第i个顶点所属的连通分量编号/该数组用于记录最小生成树edge result = n ewedgevertexNumber-1;int temp = 0;for (edge e : edges)int start

26、= e.getStart();int end = e.getEnd();if (astart=aend && aend=-1)只要将要加入 result 的edges的两个顶点相等都为-1，/说明不和result中的已经加入的联通分量有关系，则可以直 接加入result。astart = ae nd = temp;resulttemp = e;temp+;else if (astart != aend)if (astart = -1)/start=-1为悬空顶点，那么就让 start=end，使加入的连通分量和其连接的result中连通分量的标识统一。astart = ae n

27、d;else if (aend = -1)end=-1为悬空顶点，那么就让 end=start，使加入的连通 分量和其连接的result中连通分量的标识统一。ae nd = astart;else int t = astart;for (int i = 0; i < vertexNumber; i+)/要加入的edges使得result中的两个不同的连通分量连接起 来，需将一个和另外一个进行统一/遍历所有的顶点如果值和start相等就都等于end,则两个连通 分量进行了统一if (ai = t)ai = ae nd;resulttemp = e;得到了 resulttemp+;/Syst

28、em.out.println(”");/System.out.pri ntln( Arrays.toStri ng(a);if (temp = vertexNumber-1)break;System. out .pri ntl n(”最小生成树为：");for (edge e : result)System. out .pri ntl n(”连接顶点"+e.getStart()+" 和"+e.getEnd()+"该边的权值为"+e.getValue();Whe n you are old and grey and full of sleep,And no ddi ng by the fire, take dow n this book,And slowly read, and dream of the soft lookYour eyes had once, and of their shadows deep;How many loved your mome nt