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

1、 1. NANCHANG UNIVERSITY 课 程 设 计 报 告 课程名称： 程序设计课程设计实验 题 目： 破圈法求生成树 学 院： 信息工程 系： 电子商务 专 业： 计算机科学与技术 班 级： 学 号： 学生姓名： 时 间： 2013-12-30至2014-1-5 指导教师： 目 录1 课程设计目的 12 课程设计问题描述与要求 23 课程设计报告内容 24 结论 105 参考书籍 10摘 要最小生成树是数据结构中图的一种重要应用，在图中对于n个顶点的连通网可以建立许多不同的生成树，最小生成树就是在所有生成树中总的代价最小的生成树。本课程设计是以java语言来编写，主要运用了邻接矩

2、阵的存储形式，和实现Collection接口的类来简化程序，实现生成最小生成树。最小生成树的应用非常的广，如矿井通风设计和改造最优化方面以及如何搭建最短的网络线缆, 构建造价最低的通讯网络 。关键词：java，最小生成树；破圈法1. 课程设计目的求解最小生成树是数据结构课程教学中的一个重点学习的图论问题。但是目前教材中普遍讲解的是Prim和Kruskal算法，这两个算法的基本思想是基于避圈论法，破圈法而从相反的角度求解最小生成树。通过本次课程设计可以使学生了解破圈法求解最小生成树的基本理论，深化对破圈法算法方法的理解;训练综合运用所学知识处理实际问题的能力,强化面向对象的程序设计理念。2. 课

3、程设计题目描述和要求2.1题目描述 利用破圈法求最小生成树，并且运用面向对象的程序设计语言实现该算法。2.1.1最小生成树 在一给定的无向图G = (V, E)中，(u, v) 代表连接顶点u 与顶点v的边（即），而w(u, v)代表此边的权重，若存在T为E的子集（即）且为无循环图，使得的w(T)最小，则此T为G的最小生成树。破圈法实现的理论依据 该算法的理论依据是存在性定理：连通图至少有一棵生成树。如果我们给的连通图G 中没有回路，那么G 本身就是一棵生成树，若G 中只有一个回路，则删去G 的回路上的一条边（不删除结点），则产生的图仍是连通的，且没有回路，则得到的子图就是图G 的一棵生成树，

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

5、图：3. 课程设计报告内容3.1概要设计程序的UML图：3.2算法的基本过程3.2.1算法中的主要的主程序：（1） createEdgeList()用于通过邻近矩阵创建边集数组，为了方便排序，所以返回一个为ArrayList类型的引用。（2） removeEdge()用于删除某一条边。（3） IsConnectedGraph()检查图是否为连通图，可用于输入检查，和破圈法中检验在删除某条边后，所剩下图是否为连通图。（4） breakLoopBST()破圈法算法：首先用createEdgeList()方法由邻近矩阵产生图的边集列表，利用Collections的sort()和reverse()方法

6、使边列表以降序排列，依次删除列表中的最大边，并且同时检验删除后所剩下的图是否为连通图，如果是则可以删除，若不是重新把删除的边恢复，直到只剩下V-1条边（V为顶点数）。3.2.2主程序main()的基本流程（1） 创建图对象，自动调用构造方法初始化，输入邻接矩阵（2） 调用破圈法方法breakLoopBST()，生成最小生成树（3） 调用output()输出最小生成树的邻接矩阵（4） 程序结束3.3算法实现的源程序（java）EdgeElement.java:public class EdgeElement implements Comparable<EdgeElement>/边元素

7、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()return weight;Overridepublic int compareTo(EdgeElement e)/

8、覆盖comparaTo方法return weight > e.weight?1:(weight < e.weight?-1:0);Overridepublic String toString()/覆盖toString方法return "("+fromvex+","+endvex+")"+weight;Graph.java:import java.util.*;public interface Graph /图的接口，包含图的操作void intialGraph();public boolean IsConnectedGra

9、ph();/检查是否为连通图public void createGraph(EdgeElement d);/根据边集组创建一个图public List<EdgeElement>createEdgeList();/由邻接矩阵生成边集列表int vertices();/返回图的定点数int edges();/返回图的边数void putEdge(EdgeElement e);/填点边void removeEdge(int i,int j);/删除边boolean findEdge(int i ,int j);/查找边void output();/输出图public List<In

10、teger> 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 i =

11、0 ;i < n ; i +)for(int j = 0 ; j < n ; j +)if(i=j)aij=0;elseaij=MaxValue;public int getMaxValue()return MaxValue; public AdjacencyGraphy()intialGraph();/*实现接口中的方法*/public void intialGraph()System.out.print("请输入图的顶点数：");Scanner s = new Scanner(System.in);n=s.nextInt();a = new intnn;Sy

12、stem.out.println("请输入图邻接矩阵（无边的权值为1000）：");for(int i = 0 ;i < n ; i +)for(int j = 0 ; j < n ; j +)aij = s.nextInt();s.close();public boolean IsConnectedGraph()/检查是否为连通图HashSet<Integer> set1 = new HashSet<Integer>();for(int i = 0; i < n; i+)set1.add(i);int m = (int)Math.

13、random()*n;HashSet<Integer> set2 = new HashSet<Integer>(depthFirstSearch(m);if(!set1.equals(set2)return false;else return true;public void createGraph(EdgeElement d)/根据边集组创建一个图for(int t = 0;t < d.length; t+)putEdge(dt);public List<EdgeElement>createEdgeList()/由邻接矩阵生成边集列表ArrayLis

14、t<EdgeElement> l = new ArrayList<EdgeElement>();for(int i = 0 ;i < n ; i +)for(int j = i+1 ; j < n ; j +)if(aij<MaxValue)l.add(new EdgeElement(i,j,aij);return l;public int vertices()return n;/返回图的定点数public int edges()return e;/返回图的边数public void putEdge(EdgeElement e) /填点边int i =

15、 e.getFromvex();int j = e.getEndvex();int w = e.getWeight();if(aij != 0 && aij != MaxValue)System.out.println("已经存在该边，不能继续添加");elseaij = w;aji = w;public void removeEdge(int i,int j)/删除边aij = MaxValue;aji = MaxValue;public boolean findEdge(int i,int j)/查找边if(aij > 0 && a

16、ij < MaxValue)return true;else return false;public void output()/输出图for(int i = 0 ;i < n ; i +)for(int j = 0 ; j < n ; j +)System.out.print(aij+" ");System.out.println();/*图的深度遍历*/public ArrayList<Integer> depthFirstSearch(int v) /深度优先遍历boolean visited = new booleann ;/存放节点是

17、否访问过ArrayList<Integer> dsplist = new ArrayList<Integer>();/存放遍历序列for(int i = 0; i < n;i+)visitedi = false;dfs(v,visited,dsplist);return dsplist;private void dfs(int i,boolean visited,ArrayList<Integer> l)l.add(i);visitedi = true;for(int j = 0; j < n; j+)if(aij != 0 &&

18、 aij != MaxValue &&!visitedj)dfs(j,visited,l);/*破圈法求最小生成*/public void breakLoopBST()/破圈法int cnt = 0;ArrayList<EdgeElement> l =new ArrayList<EdgeElement>(createEdgeList();Collections.sort(l);Collections.reverse(l); for(int i = 0; i < l.size(); i+)removeEdge(l.get(i).getFromvex(),l.get(i).getEndvex();if(!IsConnectedGraph()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(&