2013冬课程设计_破圈法java实现

《2013冬课程设计_破圈法java实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.NANCHANGUNIVERSITY课程设计报告课程名称：程序设计课程设计实验题目：破圈法求生成树学院：信息工程系：电子商务专业：计算机科学与技术班级：学号：学生姓名：时间：2013-12-30至2014-1-5指导教师：目录1．课程设计目的…………………………………………………12．课程设计问题描述与要求……………………………………^23．课程设计报告内容……………………………………………24．结论…………………………………………………………105．参考书籍……………………………………………………10摘要最小生成树是数据结构中图的一种重要应用，在图中对于n个顶点的连通网可以建立许多

2、不同的生成树，最小生成树就是在所有生成树中总的代价最小的生成树。本课程设计是以java语言来编写，主要运用了邻接矩阵的存储形式，和实现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本身就是一棵生成树，若G105中只有一个回路，

4、则删去G的回路上的一条边（不删除结点），则产生的图仍是连通的，且没有回路，则得到的子图就是图G的一棵生成树，若G的回路不止一个，只要删去每一个回路上的一条边，直到G的子图是连通没有回路且与图G有一样的结点集，那么这个子图就是一棵生成树。由于我们破坏回路的方法可以不一样（即删去的边不一样）所以可得到不同的生成树，但是在求最小生成树的时候，为了保证求得的生成树的树权W（T）最小，那么在删去回路上的边的时候，总是在保证图仍连通的前提下删去权值较大的边，尽量保留权值较小的边。这就是所谓的破圈法。2.1.3破圈法算法步骤1.在给定的赋权的连通图上任意找一个圈。2.在所找的圈中去掉一条权数最大的边（

5、若有两条或者两条以上权数相等的边，则任意去掉其中一条）。3.重复1、2操作，直至余下的图为最小生成树。如图：1.课程设计报告内容3.1概要设计程序的UML图：1053.2算法的基本过程3.2.1算法中的主要的主程序：（一）createEdgeList()用于通过邻近矩阵创建边集数组，为了方便排序，所以返回一个为ArrayList类型的引用。（二）removeEdge()用于删除某一条边。（三）IsConnectedGraph()检查图是否为连通图，可用于输入检查，和破圈法中检验在删除某条边后，所剩下图是否为连通图。（四）breakLoopBST()破圈法算法：首先用createEdgeL

6、ist()方法由邻近矩阵产生图的边集列表，利用Collections的sort()和reverse()方法使边列表以降序排列，依次删除列表中的最大边，并且同时检验删除后所剩下的图是否为连通图，如果是则可以删除，若不是重新把删除的边恢复，直到只剩下V-1条边（V为顶点数）。1053.2.2主程序main()的基本流程（一）创建图对象，自动调用构造方法初始化，输入邻接矩阵（二）调用破圈法方法breakLoopBST()，生成最小生成树（三）调用output()输出最小生成树的邻接矩阵（四）程序结束3.3算法实现的源程序（java）EdgeElement.java:publicclassEdg

7、eElementimplementsComparable{//边元素intfromvex;intendvex;intweight;//边的两个点与权重publicEdgeElement(intv1,intv2,intwgt){//边集元素的构造方法fromvex=v1;endvex=v2;weight=wgt;}publicintgetFromvex(){//获取边元素的点和权重数据returnfromve