《数据结构(JAVA)课程设计》由会员分享，可在线阅读，更多相关《数据结构(JAVA)课程设计（23页珍藏版）》请在金锄头文库上搜索。
1、上海电力学院数据结构（JAVA）课程设计题 目：最小生成树问题学号：20083377名：院 系：计算机与信息工程学院专业年级：软件工程2008级2011年11 月23日目录一、设计目的：2二、设计内容：31、问题描述：32、基本要求：33、试验提示：34、选做内容：3三、概要设计：3四、详细设计：41、构建所有城市顶点全连接：42、对数组edges中的值进行堆排序： 5Sort.sort（edges）;53、用克鲁斯卡尔算法实现最小生成树：64、类的设计：9五、程序代码：141、class Edge： 142、class Sort： 153、class MainTest： 16六、程序测试：1
2、8七、课程设计心得：22八、参考资料：22、设计目的:（1） 熟练掌握图的创建及遍历基本操作算法。（2）熟练掌握图的最小生成树算法及应用。（3）利用以存储边（带权）的数组表示图，实现在n个城市之间建设最低的经济代价的通 信网络。二、设计内容:1、问题描述：若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代 价建设这个通信网，是一个网的最小生成树问题。2、基本要求：（1）利用克鲁斯卡尔算法求网的最小生成树。（2）实现教科书中定义的抽象数据类型MFSet。以此表示构造生成树过程中的连通分量。（3）以文本形式输出生成树中各条边以及他们的权值。3、试验提示：通信线路一旦建立
3、，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的 顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数，可利用C语言提 供的随机数函数产生。图的存储结构的选取应和所作操作相适应。为了便于选择权值最小的边，此题的存储结 构既不选用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边（带权）的数组表示图。4、选做内容：利用堆排序（参见教科书）实现选择权值最小的边。三、概要设计:此次我们设计的这个在n个城市之间建设的通信网络，用最小生成树的方法，算出经 济代价最小的网络。我们首先要把通信网络所有的带权值的边生成出来，即所有城市顶点间 的全连接。接着，利用堆排序算法把所有的带权
4、值的边，从小到大排列起来。然后，用克鲁 斯卡尔算法，求出最小生成树。类的设计：我们抽象出一个带权值边的类class Edge，它有三个属性（private int start, end, value;），即起点、终点和权值。在抽象出一个堆排序类class Sort。其余的都放到public class MainTest的main（）函数里了。其实只为了简单点，所以类少了点，其实这个程序本身就 很简单。+ sin(itr mt, Edgej: void+ soft(Ecige) void四、详细设计:1、构建所有城市顶点全连接：首先，我们随机生成 15 到 30vertexNumber个顶点，生
5、成vertexNumber*(vertexNumber-1)/2 个全连接需要边edges。然后，这个问题需要所要城市之间的全连接，但是是无向的并且 每个城市不可形成自环，所以要有vertexNumber-1个row和row-1个column。然后随机生 值为50到100的权值x。然后按顺序加入到Edge edges里。自此我们得到了所有顶点的全 连接，并且记录了所有带权值的边edges o代码：int vertexNumber=(int)(Math.random()+1)*15);System.out.println(随机生成+vertexNumber+个顶点);Edge edges=new
6、 EdgevertexNumber*(vertexNumber-1)/2;for(int row=0, index=0; rowvertexNumber; row+)(for(int column=0; column=0; i-)(sift(data, i, length-1);/排序for (int j = length - 1; j 0; j-) (/交换 data0和 datajEdge e = data0;data0 = dataj;dataj = e;sift(data, 0, j-1);public static void sift(Edge a, int root, int li
7、mit)(int i = root;int j = i*2+1;while (j = limit) (/取其子节点的较大者if (j limit & aj.getValue() ai.getVilue() (Edge e = ai;ai = aj;aj = e;i= j;j = i * 2 + 1;else(break;/跳出循环3、用克鲁斯卡尔算法实现最小生成树：此时，我们已经得到了所有带权值的边权值从小到大的数组，我们按照克鲁斯卡尔算法 就可以从数组中一条边一条边地添加到result数组中最重输出。一条一条边的添加，虽然 我们已经解决了权值从小到大的问题，但是我们怎么解决不形成环的问题呢？
8、也就是如何解 决同一连通分量的顶点间的连接问题。所以，我们要想办法标识加入最终结果集合result不同的联通分量，而且可以看到，没 有加入result中的edges的顶点是悬空的，所以也要标识这些悬空的顶点。我们先将所有没有加入result中的悬空顶点标识为-1int a = new intvertexNumber;/初始时刻，所有顶点的连通分量编号为-1，表示所有顶点都属于一个独立的连通20083377 郑京阳6分量for(int i = 0; ia.length; i+)(ai = -1；接着标识不同的加入result中的连通分量：astart = aend = temp;则：只要将要加入
9、result的edges的两个顶点相等都为-1，说明不和result中的已经加入的联 通分量有关系，则可以直接加入result。if(astart=aend & aend=-1)astart = aend = temp;resulttemp = e;temp+;如果将要加入的edges的两个顶点不相等有三种可能：一是start=-1为悬空顶点，那么就让start=end，使加入的连通分量和其连接的result中连通 分量的标识统一。else if (astart != aend) if (astart = -1) astart = aend;一是end=-1为悬空顶点，那么就让end=star
10、t，使加入的连通分量和其连接的result中连通 分量的标识统一。else if (aend = -1) aend = astart;三是要加入的edges使得result中的两个不同的连通分量连接起来，我们就需要将一个和另 外一个进行统一。就遍历所有的顶点如果值和start相等就都等于end，则两个连通分量进行 了统一。else int t = astart;for (int i = 0; i vertexNumber; i+) if (ai = t) ai = aend;然后，得到了 result,遍历，输出，得到结果。具体代码如下：/* kruskal方法得到最小生成树*a数组的元素数等
11、于顶点数* ai的值表示第i个顶点所属的连通分量编号* ai = aj表示第i和j个顶点属于同一连通分量*/int a = new intvertexNumber;/初始时刻，所有顶点的连通分量编号为-1，表示所有顶点都属于一个独立的连通 分量for(int i = 0; ia.length; i+)(ai = -1;该数组用于记录最小生成树Edge result = new EdgevertexNumber-1;int temp = 0;for(Edge e : edges)(int start = e.getStart();int end = e.getEnd();if(astart=ae
12、nd & 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 = astart;for (int i = 0; i vertexNumber; i+) (if (ai = t) (ai = aend;resulttemp = e;temp+;/System.out.println();/System.out.println(Arrays.toString(a);if(temp = vertexNumber-1)( break;System.out.println(最小生成树为：);for(Edge e : result)(Sy
