Java实现图连通网的最小生成树算法之Kruskal算法

摘要：图，连通网，最小生成树，Kruskal算法，Java实现Kruskal

在上一篇文章中我们实现了Prim算法，虽然代码量有点大，还有有很多可优化的空间，有兴趣可以取看看：Java实现图连通网的最小生成树算法之Prim算法，这里我们来实现Kruskal算法,本质上的原理跟Prim是一样的，都是为了找一条安全边，具体可参考<<算法导论>>这里不多说。

一、Kruskal

Kruskal也可以称之为”加边法”，每次加到最小生成树A中的边都是安全部，并且该安全边永远是权重最小的连接两个不属于同一颗树的节点。很明显Kruskal算法也属于贪心算法，因为它每次都选择一条权重最小的边加入到集合A中。

算法伪代码如下：

MST-KRUSKAL(G,w)
    A=∅
    for each vertex v∈G.V
        MAKE-SET(v)
    sort the edges of G.E into nondecreasing order by weight w;
    for each edge(u,v)∈G.E,taken in nondecreasing order by weight
        if FIND-SET(u)≠FIND-SET(v)
            A=A∪{(u,v)}
            UNION(u,v)
    return A

上面的伪代码定义大概意思如下，我们先让每个节点都属于独立的一棵树，然后将边按从小到大排序，这里可以用最小堆，也可以用归并排序，还可以用快速排序，我先的实现是用归并噗【排序算法时间复杂度为O(ElgE),接下来我们从小到大取出边来，若边的两个节点不属于同一颗树，就表明这条边属于最小生成树集合A中，加入集合A，然后将这两个节点合并到同一颗树中。

原理还是很简单的，下面举一个例子：

例子是网上找的，跟伪代码的实现逻辑一样的，因为实在太简单就不一一解释了，相信大家都看得懂。

二、Kruskal算法时间复杂度分析

我们现在来重新看一下Kruskal算法，把上面的伪代码拷贝下来

MST-KRUSKAL(G,w)
    A=∅
    for each vertex v∈G.V
        MAKE-SET(v)
    sort the edges of G.E into nondecreasing order by weight w;
    for each edge(u,v)∈G.E,taken in nondecreasing order by weight
        if FIND-SET(u)≠FIND-SET(v)
            A=A∪{(u,v)}
            UNION(u,v)
    return A

算法第二行对集合进行初始化的时间复杂度为O(1)，第3~4行的时间复杂度为O(V)，然后第5行的排序，这里如果用归并排序或者堆排序的话都可以到达O(ElgE),算法第6行for循环是O(E),第7行我们用Java的引用来实现，每个节点持有所在树的引用，所以是O(1),跟for循环一起就是O(E)，算法第8行也是一样，主要是第9行，这里要合并两两颗树，这里其实看实现方法，一般都能到达O(lgV)，跟for循环一起就是O(ElgV)，所以时间复杂度为：O(V)+O(ElgE)+O(E)+O(E)+O(ElgV)=O(ElgE+ElgV)。

在上一篇文章中，我们知道Prim算法的时间复杂度为O(VlgV+ElgV)。

Prim算法时间复杂度和Kruskal时间复杂度对比

Prim:O(VlgV+ElgV)
Kruskal：O(ElgE+ElgV)

很明显通过O(VlgV)和O(ElgE)比较，Prim在稠密图中比Kruskal优，在稀疏图中比Kruskal劣。

三、Java实现

我这里完全根据伪代码的思路来实现一个Java版本的Kruskal算法，我们知道Kruskal是要对边排序的，所以这里需要有一个排序方法，我这里用归并排序。
因为要根据边的权重排序，所以这里要有一个边的类：

/**
 * 边，这里要有两个属性，两个节点以及边的权重
 */
class Edge{
    private Node vertex1;
    private Node vertex2;
    private int weight;
    public Edge(Node vertex1, Node vertex2, int weight) {
        this.vertex1 = vertex1;
        this.vertex2 = vertex2;
        this.weight = weight;
    }
    public Node getVertex1() {
        return vertex1;
    }
    public void setVertex1(Node vertex1) {
        this.vertex1 = vertex1;
    }
    public Node getVertex2() {
        return vertex2;
    }
    public void setVertex2(Node vertex2) {
        this.vertex2 = vertex2;
    }
    public int getWeight() {
        return weight;
    }
    public void setWeight(int weight) {
        this.weight = weight;
    }
    @Override
    public String toString() {
        return "Edge [vertex1=" + vertex1 + ", vertex2=" + vertex2 + ", weight=" + weight + "]";
    }
}

根据边进行归并排序:

/**
     * 归并排序
     * @param a
     * @param left
     * @param right
     */
    public static Edge[] mergeSort(Edge[] a) {
        return mergeSort(a, 0, a.length-1);
    }
    private static Edge[] mergeSort(Edge[] a, int left, int right) {
        if(left<right){
            int middle = (left+right)/2;
            //对左边进行递归
            mergeSort(a, left, middle);
            //对右边进行递归
            mergeSort(a, middle+1, right);
            //合并
            merge(a,left,middle,right);
        }
        return a;
    }
    private static void merge(Edge[] a, int left, int middle, int right) {
        Edge[] tmpArr = new Edge[a.length];
        int mid = middle+1; //右边的起始位置
        int tmp = left;
        int third = left;
        while(left<=middle && mid<=right){
            //从两个数组中选取较小的数放入中间数组
            if(a[left].getWeight()<=a[mid].getWeight()){
                tmpArr[third++] = a[left++];
            }else{
                tmpArr[third++] = a[mid++];
            }
        }
        //将剩余的部分放入中间数组
        while(left<=middle){
            tmpArr[third++] = a[left++];
        }
        while(mid<=right){
            tmpArr[third++] = a[mid++];
        }
        //将中间数组复制回原数组
        while(tmp<=right){
            a[tmp] = tmpArr[tmp++];
        }
    }

然后伪代码中的一个难点就是如何判断一条边的两个节点属于同一棵树，并且如何合并为一颗树。这里我想的思路是，每个节点都有一个引用只想自己属于哪一棵树，如果两个节点的引用相同，则属于同一颗树！然后合并的时候，需要找到另一个节点的所在树中的所有节点，更新它们的引用，并且加到第一个节点所在的树中。所以这里有树如下：

/**
 * 有一个树对象，开始每一个节点就是一棵树
 * @author pc
 *
 */
class Tree{
    private List<Node> nodes=new ArrayList<Node>();
    public void addNode(Node node) {
        nodes.add(node);
    }
    public List<Node>  getNodes() {
        return nodes;
    }
}

上面说的，每个节点要持有所在树的引用，所以节点如下：

/**
 * 图的节点，因为Kruskal要判断每个节点是否属于同一颗树，所以这里要有个标志标志该节点
 * 属于哪一颗树
 * @author pc
 *
 */
class Node{
    private Tree tree;//每个接点都有属于哪一颗树
    private String value;//节点名称
    public Node(String value) {
        super();
        this.value = value;
    }
    public Tree getTree() {
        return tree;
    }
    public void setTree(Tree tree) {
        this.tree = tree;
    }
    public String getValue() {
        return value;
    }
    public void setValue(String value) {
        this.value = value;
    }
}

图如下：

//定义图：无向图
class Graph{
    //顶点
    private List<Node> vertexs;
    //边
    private List<Edge> edges;
    //初始化
    public Graph() {
        this.vertexs=new ArrayList<Node>();
        this.edges=new ArrayList<Edge>();
    }
    //添加顶点
    public void addVertex(Node node) {
        vertexs.add(node);
    }
    //添加顶点
    public void addEdage(Edge edge) {
        edges.add(edge);
    }
    public List<Node> getVertexs() {
        return vertexs;
    }
    public void setVertexs(List<Node> vertexs) {
        this.vertexs = vertexs;
    }
    public List<Edge> getEdges() {
        return edges;
    }
    public void setEdges(List<Edge> edges) {
        this.edges = edges;
    }
    /**
     * 打印图
     * @param index
     */
    public void printGraph() {
        System.out.println("节点：");
        for (Node vertex: vertexs) {
            System.out.print(vertex.getValue()+"\t");
        }
        System.out.println();
        System.out.println("边：");
        for (Edge edge: edges) {
            System.out.println(edge.getVertex1().getValue()+"----"+edge.getWeight()+"----"+edge.getVertex2().getValue());
        }
    }
}

我这里图没有用邻接矩阵的方式实现，直接把边当做一个集合了。如果要用邻接矩阵，可能依然需要一个可以排序的边的对象。

到这里我们就准备好了该准备的内容，接下来是Kruskal算法的实现。

public static  List<Edge> kruskal(Graph graph){
        //1、初始化集合A
        List<Edge> A =new ArrayList<Edge>();
        //2、初始化深林，这里只需要用节点的一个标志即可
        List<Node> nodes = graph.getVertexs();
        //深林从1开始编号
        for (int i = 0; i <nodes.size(); i++) {
            Tree tree = new Tree();
            tree.addNode(nodes.get(i));
            nodes.get(i).setTree(tree);
        }
        //对边按权重进行从小到大排序，因为要保证时间复杂度为E(ElgE),这里进行归并排序
        List<Edge> edges =graph.getEdges();
        //转变成数组
        Edge[] arr = new Edge[edges.size()];
        for(int i=0;i<edges.size();i++){  
            arr[i]=edges.get(i);  
        }  
        //进行归并排序
        arr = mergeSort(arr);
        //遍历边
        for (int i = 0; i < arr.length; i++) {
            Edge edge = arr[i];
            //判断这两个节点是否属于同一颗树
            Node vertex1 = edge.getVertex1();
            Node vertex2 = edge.getVertex2();
            Tree tree1=vertex1.getTree();
            Tree tree2=vertex2.getTree();
            if(tree1!=tree2) {
                //把边加入集合A
                A.add(edge);
                //这里要合并这两个节点所在的树,这里往树tree1合并，就是把树tree2中的所有节点的树改为tree1
                List<Node> tree2Node = tree2.getNodes();
                for (Node node : tree2Node) {
                    tree1.addNode(node);
                    node.setTree(tree1);
                }
                tree2Node=null;
            }
        }
        return A;
    }

把上面的代码整合测试：

/**
 * 连通无向图最小生成树Kruskal算法Java实现
 * @author suibibk@qq.com
 */
public class Kruskal {
    public static  List<Edge> kruskal(Graph graph){
        //1、初始化集合A
        List<Edge> A =new ArrayList<Edge>();
        //2、初始化深林，这里只需要用节点的一个标志即可
        List<Node> nodes = graph.getVertexs();
        //深林从1开始编号
        for (int i = 0; i <nodes.size(); i++) {
            Tree tree = new Tree();
            tree.addNode(nodes.get(i));
            nodes.get(i).setTree(tree);
        }
        //对边按权重进行从小到大排序，因为要保证时间复杂度为E(ElgE),这里进行归并排序
        List<Edge> edges =graph.getEdges();
        //转变成数组
        Edge[] arr = new Edge[edges.size()];
        for(int i=0;i<edges.size();i++){  
            arr[i]=edges.get(i);  
        }  
        //进行归并排序
        arr = mergeSort(arr);
        //遍历边
        for (int i = 0; i < arr.length; i++) {
            Edge edge = arr[i];
            //判断这两个节点是否属于同一颗树
            Node vertex1 = edge.getVertex1();
            Node vertex2 = edge.getVertex2();
            Tree tree1=vertex1.getTree();
            Tree tree2=vertex2.getTree();
            if(tree1!=tree2) {
                //把边加入集合A
                A.add(edge);
                //这里要合并这两个节点所在的树,这里往树tree1合并，就是把树tree2中的所有节点的树改为tree1
                List<Node> tree2Node = tree2.getNodes();
                for (Node node : tree2Node) {
                    tree1.addNode(node);
                    node.setTree(tree1);
                }
                tree2Node=null;
            }
        }
        return A;
    }
    /**
     * 归并排序
     * @param a
     * @param left
     * @param right
     */
    public static Edge[] mergeSort(Edge[] a) {
        return mergeSort(a, 0, a.length-1);
    }
    private static Edge[] mergeSort(Edge[] a, int left, int right) {
        if(left<right){
            int middle = (left+right)/2;
            //对左边进行递归
            mergeSort(a, left, middle);
            //对右边进行递归
            mergeSort(a, middle+1, right);
            //合并
            merge(a,left,middle,right);
        }
        return a;
    }
    private static void merge(Edge[] a, int left, int middle, int right) {
        Edge[] tmpArr = new Edge[a.length];
        int mid = middle+1; //右边的起始位置
        int tmp = left;
        int third = left;
        while(left<=middle && mid<=right){
            //从两个数组中选取较小的数放入中间数组
            if(a[left].getWeight()<=a[mid].getWeight()){
                tmpArr[third++] = a[left++];
            }else{
                tmpArr[third++] = a[mid++];
            }
        }
        //将剩余的部分放入中间数组
        while(left<=middle){
            tmpArr[third++] = a[left++];
        }
        while(mid<=right){
            tmpArr[third++] = a[mid++];
        }
        //将中间数组复制回原数组
        while(tmp<=right){
            a[tmp] = tmpArr[tmp++];
        }
    }
    /**
     * 打印最小生成树的边
     * @param A
     */
    public static void printKruskal(List<Edge> A) {
        //这里就已经生成了最小生成树了，遍历输出A
        for (int i = 0; i < A.size(); i++) {
            Edge edge = A.get(i);
            System.out.println(edge.getVertex1().getValue()+"----"+edge.getWeight()+"----"+edge.getVertex2().getValue());
        }
    }
    public static Graph getGraph() {
        Graph graph = new Graph();
        Node A = new Node("A");
        Node B = new Node("B");
        Node C = new Node("C");
        Node D = new Node("D");
        Node E = new Node("E");
        Node F = new Node("F");
        graph.addVertex(A);
        graph.addVertex(B);
        graph.addVertex(C);
        graph.addVertex(D);
        graph.addVertex(E);
        graph.addVertex(F);
        Edge AB = new Edge(A, B, 6);
        Edge AD = new Edge(A, D, 5);
        Edge AC = new Edge(A, C, 1);
        Edge BC = new Edge(B, C, 5);
        Edge CD = new Edge(C, D, 5);
        Edge BE = new Edge(B, E, 3);
        Edge DF = new Edge(D, F, 2);
        Edge CF = new Edge(C, F, 4);
        Edge EF = new Edge(E, F, 6);
        Edge EC = new Edge(E, C, 6);
        graph.addEdage(AB);
        graph.addEdage(AD);
        graph.addEdage(AC);
        graph.addEdage(BC);
        graph.addEdage(CD);
        graph.addEdage(BE);
        graph.addEdage(DF);
        graph.addEdage(CF);
        graph.addEdage(EF);
        graph.addEdage(EC);
        return graph;
    }
    public static void main(String[] args) {
        //获取一个图
        Graph graph = getGraph();
        graph.printGraph();
        //获取该图的最小生成树
        List<Edge> A = kruskal(graph);
        System.out.println("打印最小生成树的边");
        printKruskal(A);
    }
}
/**
 * 有一个树对象，开始每一个节点就是一棵树
 * @author pc
 *
 */
class Tree{
    private List<Node> nodes=new ArrayList<Node>();
    public void addNode(Node node) {
        nodes.add(node);
    }
    public List<Node>  getNodes() {
        return nodes;
    }
}
/**
 * 图的节点，因为Kruskal要判断每个节点是否属于同一颗树，所以这里要有个标志标志该节点
 * 属于哪一颗树
 * @author pc
 *
 */
class Node{
    private Tree tree;//每个接点都有属于哪一颗树
    private String value;//节点名称
    public Node(String value) {
        super();
        this.value = value;
    }
    public Tree getTree() {
        return tree;
    }
    public void setTree(Tree tree) {
        this.tree = tree;
    }
    public String getValue() {
        return value;
    }
    public void setValue(String value) {
        this.value = value;
    }
}
/**
 * 边，这里要有两个属性，两个节点以及边的权重
 */
class Edge{
    private Node vertex1;
    private Node vertex2;
    private int weight;
    public Edge(Node vertex1, Node vertex2, int weight) {
        this.vertex1 = vertex1;
        this.vertex2 = vertex2;
        this.weight = weight;
    }
    public Node getVertex1() {
        return vertex1;
    }
    public void setVertex1(Node vertex1) {
        this.vertex1 = vertex1;
    }
    public Node getVertex2() {
        return vertex2;
    }
    public void setVertex2(Node vertex2) {
        this.vertex2 = vertex2;
    }
    public int getWeight() {
        return weight;
    }
    public void setWeight(int weight) {
        this.weight = weight;
    }
    @Override
    public String toString() {
        return "Edge [vertex1=" + vertex1 + ", vertex2=" + vertex2 + ", weight=" + weight + "]";
    }
}
//定义图：无向图
class Graph{
    //顶点
    private List<Node> vertexs;
    //边
    private List<Edge> edges;
    //初始化
    public Graph() {
        this.vertexs=new ArrayList<Node>();
        this.edges=new ArrayList<Edge>();
    }
    //添加顶点
    public void addVertex(Node node) {
        vertexs.add(node);
    }
    //添加顶点
    public void addEdage(Edge edge) {
        edges.add(edge);
    }
    public List<Node> getVertexs() {
        return vertexs;
    }
    public void setVertexs(List<Node> vertexs) {
        this.vertexs = vertexs;
    }
    public List<Edge> getEdges() {
        return edges;
    }
    public void setEdges(List<Edge> edges) {
        this.edges = edges;
    }
    /**
     * 打印图
     * @param index
     */
    public void printGraph() {
        System.out.println("节点：");
        for (Node vertex: vertexs) {
            System.out.print(vertex.getValue()+"\t");
        }
        System.out.println();
        System.out.println("边：");
        for (Edge edge: edges) {
            System.out.println(edge.getVertex1().getValue()+"----"+edge.getWeight()+"----"+edge.getVertex2().getValue());
        }
    }
}

运行测试，结果如下：

节点：
A    B    C    D    E    F    
边：
A----6----B
A----5----D
A----1----C
B----5----C
C----5----D
B----3----E
D----2----F
C----4----F
E----6----F
E----6----C
打印最小生成树的边
A----1----C
D----2----F
B----3----E
C----4----F
B----5----C

跟上面的图中的结果一样！大功搞成！比Prim简单的多，没有花费多长时间，不过优化空间很大！

转载请注明来自个人随笔：
https://www.suibibk.com
https://www.suibibk.com/topic/709532222259986432