寻找最小生成树kruskal算法的java实现
最近几周忙着考试，这几天放假，于是，继上次关于最小生成树的实现拖到了今天。最小生成树的实现关于环的检测可以看这里；
最小生成树kruskal的思想如下：
思想还是比较简单，比较好懂，废话不多说，直接上代码
边的类如下package org.wrh.algorithmdemo;Edge implements Comparable<Edge> {/** 边的始点* */private int src;/** 边的终点* */private int dest;/** 边的权重* */private int weight;public Edge(int src, int dest,int weight) {super();this.src = src;this.dest = dest;this.weight=weight;}() {return src;}(int src) {this.src = src;}() {return dest;}(int dest) {this.dest = dest;}() {return weight;}(int weight) {this.weight = weight;}@Override(Edge o) {// TODO Auto-generated method stubif(this.weight<o.weight)return -1;else if(this.weight>o.weight)return 1;;}public String toString(){return “(“+src+”,”+dest+”,”+weight+”)”+”\n”;}}顶点类如下package org.wrh.algorithmdemo;import java.util.Arrays;import java.util.List;{/** 图中的顶点的个数* */private int vertices_number;/** 图中的边的个数* */private int edges_number;/** 图中边对象的引用* */private List<Edge> edges;public Graph(){}public Graph(int vertices_number, int edges_number) {super();this.vertices_number = vertices_number;this.edges_number = edges_number;}() {return vertices_number;}(int vertices_number) {this.vertices_number = vertices_number;}() {return edges_number;}(int edges_number) {this.edges_number = edges_number;}public List<Edge> getEdge() {return edges;}(List<Edge> edge) {this.edges = edge;}/** 功能：对图中的所有边按照边的权重按照从小到大的排序,** */public Edge[] sort(){Edge [] arrayEdge=new Edge[edges.size()];for(int i=0;i<edges.size();i++){arrayEdge[i]=edges.get(i);}Arrays.sort(arrayEdge);return arrayEdge ;}@Overridepublic String toString() {StringBuffer sb=new StringBuffer();for(Edge edge:edges){sb.append(“(“).append(edge.getSrc()).append(“,”).append(edge.getDest()).append(“,”).append(edge.getWeight()).append(“)”).append(“\n”);}return new String(sb);}}判断环的类如下package org.wrh.algorithmdemo;public class DisjuntSetCircle {/** 返回true是有环的，返回false是没有环的* */public static boolean isCycle(Graph graph,int[] parent) {int num=graph.getEdge().size();int src_represent;int dest_represent;for(int i=0;i<num;i++){int src=graph.getEdge().get(i).getSrc();//得到边的起始点int dest=graph.getEdge().get(i).getDest();//得到边的终点src_represent=find(parent,src);//System.out.println(“src=”+src);dest_represent=find(parent,dest);;}else{//否则，合并union(parent,src_represent,dest_represent);}}return false;}/** 合并两个不相交的集合* */(int[] parent, int src, int dest) {/** 由于两者是两个集合的不同的”代表元素”，因此将其中的的“代表元素”改为另外一个即可完成合并* */parent[src]=dest;}/** 用来寻找顶点X所在集合的”代表元素”* */(int[] parent, int x) {/** 首先判断顶点x的”代表元素是不是等于-1″，若等于-1，则说明，其实一个顶点的集合，返回自身顶点的标号即可；* 若不等于-1，，则说明此点在某个集合中，我们需找到他的代表元素的标号，即我们需要向上查找* */if(parent[x]==-1){return x;}return find(parent,parent[x]);}}主函数类如下package org.wrh.kruskalalg;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import org.wrh.algorithmdemo.DisjuntSetCircle;import org.wrh.algorithmdemo.Edge;import org.wrh.algorithmdemo.Graph;//kurskal算法的java实现/* * 思路如下： * 1)将图中所有边按权重从小到大排序，假设放在集合G当中，结合S放即将构成最小生成树所选的边，刚开始时，结合S为空集 * 2)逐渐选取权重最小的边，若此边与已经已经选中的边没有构成环，则放进S集合中 * 3)重复第三步，直至S集合中的边的数量为G中(顶点数-1) * */{(String[] args) {/** 给定边的数量和顶点的数量* */int vertices_num=9;int edges_num=13;/** new一个Graph对象* */Graph graph=new Graph(vertices_num,edges_num);/** 新建edges_num个Edge对象* */List<Edge> edge=new ArrayList<Edge>();edge.add(new Edge(0,1,4));edge.add(new Edge(0,7,8));edge.add(new Edge(1,7,11));edge.add(new Edge(1,2,8));edge.add(new Edge(2,3,7));edge.add(new Edge(2,8,2));edge.add(new Edge(2,5,4));edge.add(new Edge(3,4,9));edge.add(new Edge(3,5,14));edge.add(new Edge(4,5,10));edge.add(new Edge(5,6,2));edge.add(new Edge(6,7,1));edge.add(new Edge(6,8,6));/** 将边加载到图中* */graph.setEdge(edge);//这样就构成了一个4个顶点4条边的图/**定义parent数组来记录每个顶点属于那个集合的”代表元素”;* 例如：我们的学生管理系统一般会记录我们的”班长”是谁一样** *//** 对图中的边按照权重进行排序，返回该图边的数组* */Edge[] arrEdges=graph.sort();System.out.println(Arrays.toString(arrEdges));int parent []=new int[vertices_num];/** 首先我们将这些集合的代表元素初始化为 -1，表示他们都是单个元素的集合* */for(int i=0;i<parent.length;i++){parent[i]=-1;}graph=findMST(graph,arrEdges,parent);System.out.println(“最小生成树为：”+graph);}/** graph:原图* arrEdges:图中所有排序后的边按升序构成的数组* parent:图中个顶点的“代表元素”* */private static Graph findMST(Graph graph, Edge[] arrEdges,int parent []) {/** edgesMST用来保存图中最小生成树的所包含的边* */List<Edge> edgeList=new ArrayList<Edge>();/** 将权重最小的边加入到最小生成树中* */edgeList.add(arrEdges[0]);/** new一个Graph实例来保存最小生成树* */Graph graphMST=new Graph();/** for循环限制天条件中的edgeList.size()<graph.getVertices_number()是因为MST中的边的条数等于顶点的个数减一* */for(int i=1;i<graph.getEdges_number()&&edgeList.size()<graph.getVertices_number();i++){/** 将这条边加入到最小生成树中进行判断* */edgeList.add(arrEdges[i]);System.out.println(“打印edgeList：”+edgeList);/** 值得注意的是：且每次循环都要将parent清零,若不清零，将导致第二次以以后的循环的时候* isCircle函数中的find函数进行第一条边的源节点和目的节点的“代表元素”相等，即因有记忆错判为有环** 也可以选择对parent不清零，而解决方法就是，我们每次只传入新的边，然后陪和原来的parent来判断是否构成环，这种方法要更好一点* 具体步骤如下：* 我们借用一个中间图Graph graphTemp=new Graph();graphTemp.setEdge(new ArrayList(arrEdges[i]))；* 然后将下面for循环中的graphMST换成graphTemp即可，如下* if(DisjuntSetCircle.isCycle(graphTemp,parent)){//如果构成环，则去掉刚刚加进来的这条边System.out.println(“第”+i+”次有环”);edgeList.remove(arrEdges[i]);//graphMST.setEdge(edgeList);//不断更新MST中的边的内容}* */for(int j=0;j<parent.length;j++){parent[j]=-1;}graphMST.setEdge(edgeList);if(DisjuntSetCircle.isCycle(graphMST,parent)){//如果构成环，则去掉刚刚加进来的这条边System.out.println(“第”+i+”次有环”);edgeList.remove(arrEdges[i]);//graphMST.setEdge(edgeList);//不断更新MST中的边的内容}}return graphMST;}}
上面代码中的注释写的比较详细，这里就不详细的解释了，以后我还是会坚持实现我们常见的一些算法。
没有什么可留恋，只有抑制不住的梦想，
