数据结构课程设计java最小生成树

1、3上海电力学院数据结构（JAVA）课程设计 题 目:_最小生成树_ 学生姓名：_*_ 学 号：_*_ 院 系： 计算机科学与技术学院 专业年级： _*_级20*年 *月*日 14 目录1.设计题目.12.需求分析.11）运行环境.12）输入的形式和输入值的范围.13）输出的形式描述.14）功能描述.15）测试数据.13.概要设计.11）抽象数据类型定义描述.1.2）功能模块设计.13）模块层次调用关系图.24.详细设计。实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。.25.调试分析。包括调试过程中遇到的问题及解决的方法、算法的时间空间复杂性分析、经验体会。.66

2、.用户使用说明。详细列出每一步的操作说明。.77. 测试结果.78.附录：程序设计源代码.9一、设计题目1).问题描述 若要在 n 个城市之间建设通信网络，只需要架设n-1 条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。2). 基本要求 以邻接多重表存储无向带权图，利用克鲁斯卡尔算法或普瑞姆算法求网的最小生成树。二、需求分析1）运行环境 软件在JDK运行，硬件支持windows系统2） 输入的形式和输入值的范围自动生成顶点数据在1020之间；各个顶点之间权值在2550之间；通过程序改动亦可生成已知顶点权值之间的最小生成树，需将随机生成代码改为edge edge=ne

3、w edge(0,1,16),new（0,2,18）.；将已知顶点、权值通过其函数输入再生成其所对应最小生成树。3） 输出的形式描述 输出随机生成顶点个数以及各个顶点之间权值；然后输出本次生成顶点之间构成的最小生成树。4） 功能描述该程序会自动生成介于1020个数顶点模拟各城市，再随机生成介于2550之间数值作为权值模拟各个城市间的距离，并同时生成此次顶点、权值相对应的最小生成树，模拟各城市间的最小距离，最小生成树。如有确定城市顶点及其权值，则可改动程序令其不再随机生成顶点权值，在程序中输入如下代码:edge edge=new edge(0,1,16),new（0,2,18）.输入数组为edg

4、e数组，edge（起点，终点，权值）。通过将随机生成代码改动就可以生成该城市对应权值的最小生成树。5）测试数据 生成数据之后检验生成顶点数值是否介于1020之间；检验各顶点间权值大小是否介于2550间；同时检验其自动生成最小生成树是否正确。三、概要设计1）抽象数据类型定义描述定义排序类sort，将各个顶点按照其两顶点之间权值大小排序，从大到小排序，用到堆排序算法；定义带权值的边edge，分别存在start（起点）、end（终点）、value(权值)三个变量；定义main类，调用sort、edge类与自身函数通过Kruskal函数实现最小生成树。2）功能模块设计 主函数随机生成1020个顶点作为

5、城市并同时生成任意两顶点间2550的权值作为两城市距离；在界面输出随机生成顶点个数及任意两顶点间权值；再调用sort函数对权进行排序，按照权值的大小有小到大排序；排序之后实现Kruskal函数，通过kruskal函数生成最小生成树；最后输出所生成的最小生成树。3）模块层次调用关系图四、详细设计 实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。1. 定义带权值的边及其三个变量start（起点）、end（终点）、value（权值）；定义该属性为下边的根据权值排序、Kruskal实现最小生成树做下铺垫；函数实现如下：package tree;public class s

6、ort 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;/孩子节点中较小值上移ai = aj;aj = e;i = j

7、;j = i * 2 + 1;/i、j向下一层elsebreak; /跳出循环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-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("随机生成"+vertexNumber+"个顶点");edge edges=new edgevertexNumber*(vertexNumber-1)/2;for(int row=0, index=0; row<

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

10、页）；package 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向下一层elsebreak; /跳出循环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,

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

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

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

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

16、0之间权值正确运行，使得任意两顶点之间权值于2550之间；经验证该生成树为最小生成树，程序运行正确。 最小生成树定义：设G是一个带权连通无向图，w（e）是边e上的权，T是G的生成树，T中各边的权值之和称为生成树T的权值或者代价（cost）。权值最小的生成树称之为最小生成树（minimum cost spanning tree），简称最小生成树。八、附录：程序设计源代码package tree;public class sort public static void sift(edge a, int root, int limit)int i = root;int j = i*2+1;/j为i的

17、左孩子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;/i、j向下一层elsebreak; /跳出循环public static void sort(edge data)int length = da

18、ta.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-1);package tree;public class edge private int start, end, value;/定义开始、结束、权值public edge(int start,int end,int valu

19、e)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 setEnd(int end) this.end = end;public int getValue() return value;public void setValue(int value) this.value = value;packa

20、ge tree;public class main public static void main(String args) int vertexNumber=(int)(Math.random()+1)*10);System.out.println("随机生成"+vertexNumber+"个顶点");edge edges=new edgevertexNumber*(vertexNumber-1)/2;for(int row=0, index=0; row<vertexNumber; row+)/row行、column列、index数组for(i

21、nt column=0; column<row; column+)int x=(int)(Math.random()+1)*25);/random随机的edgesindex = new edge(row, column, x);System.out.println("顶点"+row+"和"+column+"之间的距离为"+x);index+;sort.sort(edges);/对数组 edges中的值进行堆排序int a = new intvertexNumber;for(int i = 0; i<a.length; i+)/初始时刻，所有顶点的连通分量编号为-1，表示所有顶点都属于一个独立的连通分量ai = -1;/ai的值表示第i个顶点所属的连通分量编号/该数组用于记录最小生成树edge result = new edgevertexNumber-1;int temp = 0;for(edge e : edges)int start = e.getStart();int end = e.getEnd();if(astart=aend && aend=-1)/只要将要加入result的edges的两个顶点相等都为-1，/说明不和result中的已经加入的联通分量有关系，则