改进的最小生成树算法

数据结构与算法课程设计报告课程名称：数据结构与算法课程设计题目:改进的最小生成树算法专业：计算机科学与技术班级：（一）班学号：1362810118，1362810107，1362810108学生姓名：王洪，汪妍，罗林芳目录TOC\o"1-5"\h\z\o"CurrentDocument"一、问题描述1\o"CurrentDocument"二、需求分析1\o"CurrentDocument"性能需求1\o"CurrentDocument"功能需求2\o"CurrentDocument"问题假设2\o"CurrentDocument"三、准备知识2欧拉图定义：2欧拉图相关定理：错误！未定义书签。欧拉图应用：.错误！未定义书签。\o"CurrentDocument"四、算法和数据结构设计5\o"CurrentDocument"算法分析5建立模型51）前期准备.错误！未定义书签。2）确定模型.错误！未定义书签。具体算法实现.错误！未定义书签。时间复杂度分6题目拓展8五、程序测试错误！未定义书签。测试1（测试没有度数为奇数的顶点）9测试2（测试度数为奇数的定点有4个）9六、总结11已完成部分11\o"CurrentDocument"后期设想113.课程设计思考与体会错误！未定义书签。\o"CurrentDocument"七、参考文献11最小生成树是数据结构中图的一种重要应用，在图中对于n个顶点的连通网可以建立许多不同的生成树，最小生成树就是在所有生成树中总的代价最小的生成树。本课程设计是以java语言来编写，主要运用了邻接矩阵的存储形式，和实现Collection接口的类来简化程序，实现生成最小生成树。最小生成树的应用非常的广，如矿井通风设计和改造最优化方面以及如何搭建最短的网络线缆，构建造价最低的通讯网络。关键词：java，最小生成树；破圈法一、问题描述一般都采用prim算法或者kruskal算法，两个算法都很直接。prim算法其实就是disj算法的变形，只是更新策略和判断策略不同而已。kruskal采用了不相交集和堆，写出的算法也很简洁并且很好理解。而这两者都是通过添加边来构造树，最小生成树还有一种大类就是破圈法。本文我们探究的是用破圈法来构造树，即连续删除某些边，从而破坏图中的回路，直到图中不存在回路为止，此时的图就是生成树。二、需求分析根据提示使用删除边的方法，我们想到了破圈算法。破圈算法是1975年由我国数学家管梅谷教授提出来的。破圈法基本思想：在给定的图中任意找出一个回路，删去该回路中权最大的边。然后在余下的图中再任意找出一个回路，再删去这个新找出的回路中权最大的边，……一直重复上述过程，直到剩余的图中没有回路。这个没有回路的剩余图便是最小生成树。算法的基本思想：先将图G的边按权的递减顺序排列后，依次检验每条边，在保持连通的情况下，每次删除最大权边，直到余下n-1条边为止。性能需求1）构造数据的输入形式和范围输入顶点数为int类型，范围为0-100。数据结构采用邻接矩阵存储图。功能需求在给定的赋权的连通图上任意找一个圈。在所找的圈中去掉一条权数最大的边(若有两条或者两条以上权数相等的边，则任意去掉其中一条)。重复1、2操作，直至余下的图为最小生成树。问题假设假设本题涉及的无向图是一个连通图。三、准备知识算法的理论基础：定理1:任意图G有支撑树的充分必要条件是图G是连通的。定理2:图G=(V,E)是一个树的充分必要条件是G是连通图，且e=n-1。最小生成树最小生成树：一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图连通的最少的边，如图1所示。无向圈及其不同生成树生成树2图1最小生成树示意图设G=(V,E)是无向连通带权图，即一个网络。E中的每一条边(v,w)的权为W(v,w)。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权的总和称为生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。避圈法避圈法的主要思想就是：开始选一条最小权的边，以后每一步中，总从与已选边不构成圈的那些未选边中，选择一条权最小的(每一步中，如果有两条或两条以上的边都是权值最小的边，则从中任选一条)。避圈法主要分为两种：Prim算法和Kruskal算法，下面分别进行介绍。a.Prim算法设G=(V,E)是连通带权图，V={1,2,…,n}。构造G的最小生成树Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就进行如下的贪心选择：选取满足条件iES,j£V-S，且c[i][j]最小的边，将顶点j添加到S中。这个过程一直进行到=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。图2显示了某一带权图。最小生成树的生成过程如下：TOC\o"1-5"\h\z\o"CurrentDocument"3;c136;c44;c232;c55;c3最终得到的最小生成树如图3所示。图3带权图G的最小生成树示意图b.Kruskal算法给定无向连通带权图G=(V,E),V={1,2,...,n。Kruskal算法构造G的最小生成树的基本思想是：将G的n个顶点看成n个孤立的连通分支，并将所有的边按权从小到大排序；从第一条边开始，依据每条边的权值递增的顺序检查每一条边，并按照下述方法连接两个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前两个不同的连通分支T1和T2的端点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边;如果端点v和w在当前的同一个连通分支中，就直接查看第k+1条边，这个过程一个进行到只剩下一个连通分支时为止。此时，已构成G的一棵最小生成树。仍以图2所示的带权图G为例说明其最小生成树的生成过程，生成过程如下所示：13;c146;c2TOC\o"1-5"\h\z5;c36;c423;c5最终得到的最小生成树和图3所示是一样的。破圈法破圈法可以描述如下：如果我们给的连通图G中没有回路，那么G本身就是一棵生成树；若G中只有一个回路，则删去G的回路上的一条边(不删除结点)，则产生的图仍是连通的且没有回路，则得到的子图就是图G的一棵生成树；若G的回路不止一个，只要删去每一个回路上的一条边，直到G的子图是连通没有回路且与图G有一样的结点集，那么这个子图就是一棵生成树。由于我们破坏回路的方法可以不一样，所以可得到不同的生成树，但是在求最小生成树的时候，为了保证求得的生成树的树权最小，那么在删去回路上的边的时候，总是在保证带权图仍连通的前提下删掉权值较大的边，保留权值较小的边。破圈法就是在带权图的回路中找出权值最大的边，将该边去掉，重复这个过程，直到图连通且没有圈为止，保留下来的边所组成的图即为最小生成树。下面仍利用图1.1.2对破圈法进行说明。首先是去除权值大的边，并且检测去除该边后整个图是否连通，对于图2来说，即第一步去掉权值为6的边，如图4所示。图4去掉权值为6的G的示意图从图中可以看出，去掉权值为6的边后整个图仍是连通的。所以接下来去除权值为5的边，并且检测去除该边后图是否连通，结果如图5所示。由图可知，去掉所有权值为5的边会造成图G不连通，因此23;c5这条边是必须保留的。然后再去除权值为4的边。由于权值为1、2、3、4的边分别连接着独立的节点，故都必须保留，得到的最小生成图5去掉权值为5的G的示意图树结果与图3也是一样的。避圈法与破圈法比较Prim算法是从空图出发，将点进行二分化，从而逐步加边得到最小生成树。它是近似求解算法，虽然对于大多数最小生成树问题都能求得最优解，但相当一部分求得的是近似最优解，具体应用时不一定很方便。但是它可以看作是很多种最小树算法的概括，在理论上有一定的意义。Kruskal算法也是从空图出发。它是精确算法，即每次都能求得最优解，但对于规模较大的最小生成树问题，求解速度较慢。破圈法是从图G出发，逐步去边破圈得到最小生成树。它最适合在图上工作，当图较大时，可以几个人同时在各个子图上工作，因此破圈法在实用上是很方便的。四、算法和数据结构设计1.算法分析概要设计：当仔细研究了课题并且考虑过后，我们都想到了破圈法，通过删边来构造最小生成树用拓扑分类算法，找到图中的圈。具体就是依次找到图中度为1的顶点(可以保存在队列里)，删除之(这里的删除是暂时的，下次遍历还要还原这些点)，然后与其邻接的顶点的入度-1，这样往复操作，直到图中已不存在入度为1的顶点，即所有的顶点的度都>=2，那么剩下的边就都在环里了。当然，如果没剩下边，说明没有环，算法结束。剩下的边就都是环中的边了，找一个权最大的删去即可。再进行1操作，直到图中无圈，即所有的圈都已破掉，剩下的就是最小生成树了。详细设计：算法中的主要的主程序：voidintialGraph()：用于创建图publicbooleanIsConnect():并查集判断图连通性publicbooleanIsConnectedGraph():检查是否为连通图publicvoidcreateGraph(Edge[]d)：根据边集组创建一个图publicList<Edge>createEdgeList()：由邻接矩阵生成边集列表intvertices():返回图的定点数intedges():返回图的边数voidputEdge(Edgee):填点边voidremoveEdge(inti,intj)：删除边booleanfindEdge(inti,intj)：查找边voidoutput():输出图publicList<Integer>depthFirstSearch(intv)：深度优先遍历voidbreakLoopBST():删边获得最小生成树主程序main()的基本流程创建图对象，自动调用构造方法初始化，输入邻接矩阵调用破圈法方法breakLoopBST()，生成最小生成树调用output()输出最小生成树的邻接矩阵程序结束

建立模型先将图G的边按权的递减顺序排列，Ei为删除边集。具体步骤为第1步：令i=1,E0=O,G0=G;第2步：取边eiEE(Gi-1)即E\Ei-1,令Ei=Ei-1U{ei},使得Gi=G[E\Ei]连通,且W(ei)权尽可能大；第3步：若i<e-n+1,令i=i+1,返回第2步,否则，Gi=G[E\Ei]把Ei中的边全部删除，即是所求的最小支撑树数学模型如图：1.取圈{ADE},删除DE边2.取圈{ABD},删除AB边3.取圈(ABDC},删除CD边，得到最小生成树算法的伪代码实现算法：AdjacencyGraph(intn)输入：图的阶数n输出：任意的一个构造图>a=newint[n][n];>forinti=0;i<n;i++;>for(inti=0;i<n;i++){For(intj=0;j<i+1;j++)}判断图的连通性算法：booleanIsConnectedGraph()输入图输出：true或者false>for(inti=0;i<n;i++){set1.add(i);}，图顶点集合>if(!set1.equals(set2)),深搜得到便利点的集合，与图顶点集合比较Returnfalse;,返回比较结果为连通性判断。1.取圈{ADE},删除DE边2.取圈{ABD},删除AB边3.取圈(ABDC},删除CD边，得到最小生成树elsereturntrue;算法：深度优先遍历ArrayList<Integer>depthFirstSearch(intv)输入节点数n输出：是否访问过>boolean[]visited=newboolean[n]>for(i=0;i<n;i++)>returndsplist算法;输出图breakLoopBST()输入:排序后的列表输出:最小生成树>collection.sort(1)，边按升序排序>collection.reserve(1)，边排序反转成降序>for(i=0;i<n;i++)，遍历删除每条边，若保持连通性，删除之，否则保留。>break深度搜索尽管能得到结果，但效率却比prim算法差了更多，借鉴prim算法并查集判断图的连通性的思想，对算法进行优化，将连通性判断改为并查集，提高效率，给出算法伪代码如下：核心算法的优化采用并查集判断连通性算法booleanIsConnect()>for(inti=0;i<n;i++)，初始化父亲节点>ArrayList<Edge>l=newArrayList<Edge>(createEdgeList())，以边关系更新父亲节点>for(intj=0;j<l.size();j++)>for(intk=0;k<n;k++)，寻找父节点的父节点，直至更新至根节点>for(inti=0;i<n;i++)，判断图中节点的父亲节点是否统一>returntrueorfalse，输入图的连通性b.算法的具体实现：见附录1：算法复杂度分析经分析，影响算法主要决定因素是深度遍历和并查集的递归次数，分别对采用不同方法效率进行分析如下：该算法采用深度搜索判断图的连通性的时间复杂度为：O（n2）；算法采用并查集判断图的连通性的时间复杂度为：O（n（n+1）/2）；由此可知，并查集极大的改进了算法效率。以顶点为4的无向图为例（邻接矩阵）：0478276470416382410727663720最小生成树（邻接矩阵）：0478847041638410886380在生成最小生成树的过程中采用深度搜索判断图的连通性递归次数为：3+3+3=9次，而使用并查集的方法判断图的连通性递归次数为：1+2+3=6>9次。由此可以看出，使用并查集判断连通性的效率远高于深度搜索。题目拓展1）提出问题对于我们已经实现的算法的结果，执行的算法效率依然有待高，有没有更简单的优化算法来实现生成最小生成树。2）算法分析可以采用邻接多重表的方式来进行动态优化算法：首先初始化数组和顶点遍历数组，将满足条件的顶点加入集合循环判断在其他顶点中选择满足条件的权值最小的边

五程序测试测试1（测试不能构成图时能否得到最小生成树）顶点数必须大于大于等于2才会有边1）输入信息：创建图生成最小生成树2）预测结果至少可以得到一条边3）实际输出结果如图4.1所示如造圈邻接矩阵为：TOC\o"1-5"\h\z084840勾造图邻接拒阵为：084840图4.1测试1实际输出结果4）结果分析根据输出结果分析，当顶点数为2时只能有一条边，构不成图，由于我们是采用删除边的方法，当只有一条边的时候也不用删除，直接输出。测试2（测试顶点数是3最小并且为最小连通图时的情况）创建图生成最小生成树1）输入信息请入顶点数：32）预测结果创建图生成最小生成树至少需要机器狗的数目为2应该只剩下其中的两条边，并且满足是最小生成树3）实际输出如图4.2所示

向造图邻接拒阵为:076107603510350向造图邻接拒阵为:0810OCi03535图4.2测试2实际输出结果04）结果分析得到的结果确实为只有两条边构成的生成树，而且是最小生成树满足要求，符合题意。测试3（测试顶点数为其他数防止偶然的情况发生）5）输入信息麻入顶点数:创建图生成最小生成树6）预测结果麻入顶点数:创建图生成最小生成树至少输出的结果应该为只有5条边构成的最小生成树7）实际输出如图4.2所示询定倒邻球地件为:012668380871203286911866320593544838659050778091355003387184477330构造图邻接拒阵为：01212032oc>oo183200505003318330图4.2测试2实际输出结果8）结果分析得到的经过将矩阵转换为图形，满足我们所要求的是最小生成树，并且只有5条边符合题意。六总结1.后期设想已完成部分完成题目要求，采用删除某些边，破坏图中的回路，直到图中不存在回路为止，此时得到的生成树就是最小生成树。这种方法与老师上课讲的prime和kruskal算法在思想上有很大的不同，后两者采用的是加边的方法，将边一条一条加入生成一棵最小生成树，而我们采用的这种俗称叫做破圈法，既是将边一条一条删除最后得到一棵最小生成树。通过实验让我们更加懂得有时候解决问题可以从相反的方向去思考，不能墨守成规，一成不变，要有创新后期设想我们能不能再进一步改进算法，实现更加高效的程序，学习算法的目的也是在于优化程序，在采用删除边的方法的同时更主要实现效率的提高，这也促使我们对于这个问题要有更深的理解和认识，以及在解决问题的时候我们应该考虑的更加全面，更加具体和详细。程序设计思考与体会经过我们不懈的努力我们终于完成了本次课程设计，通过这次课程设计，我感觉到要真正做出一个程序并不很容易，但只要用心去做，总会有收获，特别是当我遇到一个问题，想办法去解决，最后终于找到方法时，心里的那份喜悦之情真是难以形容。编写程序中遇到问题再所难免，应耐心探究其中的原因，从出现问题的地方起，并联系前后程序，仔细推敲，逐个排查。直到最终搞清为止。我们本次做的是图的最小生成树问题，该算法主要侧重于找边、删边的过程，通过这个方法求到的最小生成树和别的算法相比，主要是算法简单，结构清晰，在程序实现中只是用到了数组和循环语句的知识，程序简单明了。因为破圈法与避圈法是两种不同的解题思维，通过本次课程设计让我更加知道“条条大路通罗马”，平时应该变换角度得来思考问题。七参考文献屈婉玲.离散数学[M].北京：高等教育出版社，2008.叶核亚.数据结构(Java版)[M].北京：电子工业出版社，2011.屈婉玲.算法设计与分析[M].北京：高等教育出版社，2008.Java编程思想第四版，BruceEckel著陈昊鹏译，机械工业出版社，2012.11龙亚.图的连通性算法探讨[J].毕节师范高等专科学校学报，2002附录1：a.Graph.java:importjava.util.*;publicinterfaceGraph{//图的接口，包含图的操作voidintialGraph();//创建图publicbooleanIsConnectedGraph();//检查是否为连通图publicvoidcreateGraph(Edge[]d);//根据边集组创建一个图publicList<Edge>createEdgeList();//由邻接矩阵生成边集列表intvertices();//返回图的定点数intedges();//返回图的边数voidputEdge(Edgee);//填点边voidremoveEdge(inti,intj);//删除边booleanfindEdge(inti,intj);//查找边voidoutput。；//输出图publicList<Integer>depthFirstSearch(intv);//深度优先遍历voidbreakLoopBST();//删边获得最小生成树}publicclassEdgeimplementsComparable<Edge>{//边元素intfromvex;intendvex;intweight;//边的两个点与权重publicEdge(intv1,intv2,intwgt){fromvex=v1;endvex=v2;weight=wgt;}publicintgetFromvex(){returnfromvex;}publicintgetEndvex(){returnendvex;}publicintgetWeight(){returnweight;}©Override//边集元素的构造方法//获取边元素的点和权重数据publicintcompareTo(Edgee){//覆盖comparaTo方法returnweight>e.weight?1:(weight<e.weight?-1:0);}©OverridepublicStringtoString(){return〃(〃+fromvex+〃，〃+endvex+〃)〃+weight;}//覆盖toString方法}a.AdjacencyGraphy.javaimportjava.util.ArrayList;importjava.util.Collections;importjava.util.HashSet;importjava.util.List;//importjava.util.Random;importjava.util.Scanner;publicclassAdjacencyGraphyimplementsGraph{finalintMaxValue=1000;//一个不存在的边的权值intn;//顶点数inte;//边数int[][]a;〃邻接矩阵publicAdjacencyGraphy(intn){//初始化this.n=n;e=0;a=newint[n][n];for(inti=0;i<n;i++)for(intj=0;j<n;j++){if(i==j)a[i][j]=0;elsea[i][j]=MaxValue;}}publicintgetMaxValue(){returnMaxValue;}publicAdjacencyGraphy(){intialGraph();}/**********************实现接口中的方法*********************************/publicvoidintialGraph(){System.out.print(〃请输入图的顶点数：");Scanners=newScanner(System.in);n=s.nextInt();a=newint[n][n];//Randomrandom1=newRandom(100);//System.out.println("请输入图邻接矩阵(无边的权值为1000)：");for(intk=0;k<n;k++)a[k][k]=0;for(inti=0;i<n;i++)for(intj=i+1;j<n;j++){a[i][j]=a[j][i]=(int)(Math.random()*100)+1;}s.close();}publicbooleanIsConnect(){//并查集判断连通性int[]father=newint[n];for(inti=0;i<n;i++)father[i]=i;ArrayList<Edge>l=newArrayList<Edge>(createEdgeList());for(intj=0;j<l.size();j++){intstart=l.get(j).getFromvex();intdest=l.get(j).getEndvex();father[dest]=start;}for(intk=0;k<n;k++)(father[k]=get_father(k,father);}for(inti=0;i<n;i++)if(father[i]!=0)returnfalse;returntrue;}privateintget_father(intk,int[]father)(if(k==father[k])returnk;elsereturnget_father(father[k],father);}publicbooleanIsConnectedGraph(){//检查是否为连通图HashSet<Integer>setl=newHashSet<Integer>();for(inti=0;i<n;i++){set1.add(i);}intm=(int)Math.random()*n;HashSet<Integer>set2=newHashSet<Integer>(depthFirstSearch(m));if(!set1.equals(set2))returnfalse;elsereturntrue;}publicvoidcreateGraph(Edge[]d){//根据边集组创建一个图for(intt=0;t<d.length;t++){putEdge(d[t]);}}publicList<Edge>createEdgeList(){//由邻接矩阵生成边集列表ArrayList<Edge>l=newArrayList<Edge>();for(inti=0;i<n;i++)for(intj=i+1;j<n;j++){if(a[i][j]<MaxValue){l.add(newEdge(i,j,a[i][j]));}}returnl;}publicintvertices(){returnn;}publicintedges(){returne;}//返回图的定点数//返回图的边数publicvoidputEdge(Edgee){//填点边inti=e.getFromvex();intj=e.getEndvex();intw=e.getWeight();if(a[i][j]!=0&&a[i][j]!=MaxValue)System.out.println(〃已经存在该边，不能继续添加〃)；else{a[i][j]=w;a[j][i]=w;}}publicvoidremoveEdge(inti,intj){//删除边a[i][j]=MaxValue;a[j][i]=MaxValue;}publicbooleanfindEdge(inti,intj){//查找边if(a[i][j]>0&&a[i][j]<MaxValue)returntrue;elsereturnfalse;}publicvoidoutput(){