《冬课程设计 破圈法java实现》由会员分享，可在线阅读，更多相关《冬课程设计 破圈法java实现（12页珍藏版）》请在金锄头文库上搜索。
1、 1. NANCHANG UNIVERSITY课 程 设 计 报 告课程名称： 程序设计课程设计实验 题 目： 破圈法求生成树 学 院： 信息工程 系： 电子商务 专 业： 计算机科学与技术 班 级： 学 号： 学生姓名： 时 间： 2013-12-30 至 2014-1-5 指导教师： 目 录1课程设计目的 12课程设计问题描述与要求 23课程设计报告内容 24结论 105参考书籍 10- 0 -摘 要最小生成树是数据结构中图的一种重要应用，在图中对于 n 个顶点的连通网可以建立许多不同的生成树，最小生成树就是在所有生成树中总的代价最小的生成树。本课程设计是以 java 语言来编写，主要运用
2、了邻接矩阵的存储形式，和实现 Collection 接口的类来简化程序，实现生成最小生成树。最小生成树的应用非常的广，如矿井通风设计和改造最优化方面以及如何搭建最短的网络线缆, 构建造价最低的通讯网络 。关键词：java，最小生成树；破圈法1. 课程设计目的求解最小生成树是数据结构课程教学中的一个重点学习的图论问题。但是目前教材中普遍讲解的是 Prim 和 Kruskal 算法，这两个算法的基本思想是基于避圈论法，破圈法而从相反的角度求解最小生成树。通过本次课程设计可以使学生了解破圈法求解最小生成树的基本理论，深化对破圈法算法方法的理解;训练综合运用所学知识处理实际问题的能力,强化面向对象的程
3、序设计理念。2. 课程设计题目描述和要求2.1 题目描述利用破圈法求最小生成树，并且运用面向对象的程序设计语言实现该算法。2.1.1 最小生成树在一给定的无向图 G = (V, E)中，(u, v) 代表连接顶点 u 与顶点 v 的边（即） ，而 w(u, v)代表此边的权重，若存在 T 为 E 的子集 （即）且为无循环图，使得的 w(T)最小，则此 T 为 G 的最小生成树。2.1.2 破圈法实现的理论依据该算法的理论依据是存在性定理：连通图至少有一棵生成树。如果我们给的连通图 G 中没有回路，那么 G 本身就是一棵生成树，若 G 中只有一个回路，- 1 -则删去 G 的回路上的一条边（不删
4、除结点） ，则产生的图仍是连通的，且没有回路，则得到的子图就是图 G 的一棵生成树，若 G 的回路不止一个，只要删去每一个回路上的一条边，直到 G 的子图是连通没有回路且与图 G 有一样的结点集，那么这个子图就是一棵生成树。由于我们破坏回路的方法可以不一样（即删去的边不一样）所以可得到不同的生成树，但是在求最小生成树的时候，为了保证求得的生成树的树权 W（T）最小，那么在删去回路上的边的时候，总是在保证图仍连通的前提下删去权值较大的边，尽量保留权值较小的边。这就是所谓的破圈法。2.1.3 破圈法算法步骤1. 在给定的赋权的连通图上任意找一个圈。2. 在所找的圈中去掉一条权数最大的边（若有两条或
5、者两条以上权数相等的 边，则任意去掉其中一条） 。3. 重复 1、2 操作，直至余下的图为最小生成树。如图：3. 课程设计报告内容3.1 概要设计程序的 UML 图：- 2 -3.2 算法的基本过程3.2.1 算法中的主要的主程序：（1）createEdgeList()用于通过邻近矩阵创建边集数组，为了方便排序，所以返回一个为 ArrayList 类型的引用。（2）removeEdge()用于删除某一条边。（3（IsConnectedGraph()检查图是否为连通图，可用于输入检查，和破圈法中检验在删除某条边后，所剩下图是否为连通图。（4（breakLoopBST()破圈法算法：首先用 cre
6、ateEdgeList()方法由邻近矩阵产生图的边集列表，利用 Collections 的 sort()和 reverse()方法使边列表以降序排列，依次删除列表中的最大边，并且同时检验删除后所剩下的图是否为连通图，如果是则可以删除，若不是重新把删除的边恢复，直到只剩下 V-1 条边（V 为顶点数） 。- 3 -3.2.2 主程序 main()的基本流程（1）创建图对象，自动调用构造方法初始化，输入邻接矩阵（2）调用破圈法方法 breakLoopBST()，生成最小生成树（3） 调用 output()输出最小生成树的邻接矩阵（4）程序结束3.3 算法实现的源程序（java）EdgeElemen
7、t.java:public class EdgeElement implements Comparable/边元素int fromvex;int endvex;int weight; /边的两个点与权重public EdgeElement(int v1, int v2,int wgt) /边集元素的构造方法fromvex = v1;endvex = v2;weight = wgt;public int getFromvex() /获取边元素的点和权重数据return fromvex;public int getEndvex()return endvex;public int getWeight
8、()return weight;Overridepublic int compareTo(EdgeElement e) /覆盖comparaTo方法return weight e.weight?1:(weight createEdgeList();/由邻接矩阵生成边集列表int vertices(); /返回图的定点数int edges();/返回图 的边数void putEdge(EdgeElement e);/填点边void removeEdge(int i,int j);/删除边boolean findEdge(int i ,int j);/查找边void output();/输出图pu
9、blic List depthFirstSearch(int v);/深度优先遍历void breakLoopBST();/破圈法求最小生成树AdjacencyGraphy.java:import java.util.*;public class AdjacencyGraphy implements Graph final int MaxValue = 1000; /一个不存在的 边的权值int n; /顶点数int e; /边数int a; /邻接矩阵public AdjacencyGraphy(int n)/初始化this.n = n;e = 0;a = new intnn;for(int
10、 i = 0 ;i set1 = new HashSet();for(int i = 0; i set2 = new HashSet(depthFirstSearch(m);if(!set1.equals(set2)return false;else return true;public void createGraph(EdgeElement d) /根据边集组创建一个图for(int t = 0;t createEdgeList()/由邻接矩阵生成边集列表ArrayList l = new ArrayList();- 6 -for(int i = 0 ;i 0 & aij depthFir
11、stSearch(int v) /深度优先遍历boolean visited = new booleann ;/存放节点是否访问过ArrayList dsplist = new ArrayList();/存放遍历序列for(int i = 0; i l)l.add(i);visitedi = true;for(int j = 0; j l =new ArrayList(createEdgeList();Collections.sort(l);Collections.reverse(l);for(int i = 0; i l.size(); i+)removeEdge(l.get(i).getF
12、romvex(),l.get(i).getEndvex();if(!IsConnectedGraph()- 8 -putEdge(l.get(i);elsecnt+;if(cnt = l.size()-n-1)break;TestBST.java:public class TestBST public static void main(String args) AdjacencyGraphy g = new AdjacencyGraphy();System.out.println(图的邻接矩阵: );g.output();g.breakLoopBST();System.out.println(
13、破圈法求出的最小生成树为 ：);g.output();3.4 运行结果- 9 -4. 结论经过我们不懈的努力我们终于完成了本次课程设计，通过这次课程设计，我感觉到要真正做出一个程序并不很容易，但只要用心去做，总会有收获，特别是当我遇到 一个问题，想办法去解决，最后终于找到方法时，心里的那份喜悦之情真是难以形容。编写程序中遇到问题再所难免，应耐心探究其中的原因，从出现问题的地方起，并联系前后程序，仔细推敲，逐个排查。直到最终搞清为止。我们本次做的是图的最小生成树问题，该算法主要侧重于找边、删边的过程，通过这个方法求到的最小生成树和别的算法相比，主要是算法简单，结构清晰，在程序实现中只是用到了数组和循环语句的知识，程序简单明了。因为破圈法与避圈法是两种不同的解题思维，通过本次课程设计让我更加知道“条条大路通罗马” ，平时应该变换角度得来思考问题。参考书目：1 Java 编程思想第四版，Bruce Eckel 著 陈昊鹏译，机械工业出版社，2012.112 龙亚.图的连通性算法探讨J.毕节师范高等专科学校学报，20023 数据结构教程java 语言描述，徐孝凯 编，清华大学出版社，2010.84 数据结构与算法java 语言描述，Mark Allen Weiss 著 冯舜玺译，机械工业出版社，2004.8
