查找最小生成树:克鲁斯克尔算法(Kruskal)算法

一、算法介绍

  Kruskal算法是一种用来查找最小生成树的算法,由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法Boruvka算法等。三种算法都是贪心算法的应用。和Boruvka算法不同的地方是,Kruskal 算法在图中存在相同权值的边时也有效。最小生成树是一副连通加权无向图中一棵权值最小生成树(minimum spanning tree,简称MST生成树的权重是赋予生成树的每条边的权重之和。最小生成树具有 (V – 1) 个边,其中 V 是给定图中的顶点数。关于最小生成树,它可以应用在网络设计、NP难题之类的问题,还可以用于聚类分析,还可以间接应用于其他问题。

二、Kruskal算法查找MST的步骤

  1.  按权重的顺序方式来对所有边进行排序

  2.  选择权重最小的边。检查它是否与形成的生成树形成一个循环。如果未形成循环,则包括该边。否则,将其丢弃

  3.  重复步骤2,直到生成树中有(V-1)个边。

   这个算法是贪婪算法。“贪婪的选择”是选择迄今为止不会造成MST成环的最小的权重边。下面来一个例子来理解:

查找最小生成树:克鲁斯克尔算法(Kruskal)算法

  该图包含9个顶点(V)和14个边(E)。因此,形成的最小生成树将具有(9 – 1)= 8 个边。

  步骤1:每条边按顺序来排序

  /**
         * 排序后:
         * 权重-src-dest
         * 1 6 7
         * 2 2 8
         * 2 5 6
         * 4 0 1
         * 4 2 5
         * 6 6 8
         * 7 2 3
         * 7 7 8
         * 8 0 7
         * 8 1 2
         * 9 3 4
         * 10 4 5
         * 11 1 7
         * 14 3 5
         */

  步骤2+步骤3::利用按权重排好序的边数组,每次选取最小边,并检测是否成环MST不能有环,所以这里涉及一个并查集的概念,并查集是对这个 Kruskal 算法进行优化的。

  1)数组中一个接一个地选取所有边取边6-7:不形成循环,将其包括在内。

查找最小生成树:克鲁斯克尔算法(Kruskal)算法

  2)选取边2-8:不形成循环,将其包括在内。

查找最小生成树:克鲁斯克尔算法(Kruskal)算法

  3)选取边5-6:不形成循环,将其包括在内。

查找最小生成树:克鲁斯克尔算法(Kruskal)算法

4)选取边0-1:不形成循环,将其包括在内。

查找最小生成树:克鲁斯克尔算法(Kruskal)算法

  5)选取边2-5:不形成循环,将其包括在内。

查找最小生成树:克鲁斯克尔算法(Kruskal)算法

  6)选取边6-8:由于包括该边会导致成环,因此将其丢弃。

  7)选取边2-3:不形成循环,将其包括在内。

查找最小生成树:克鲁斯克尔算法(Kruskal)算法

  8)选取边7-8:由于包括该边会导致循环,因此请将其丢弃。

  9)选取边0-7不形成循环,将其包括在内。

查找最小生成树:克鲁斯克尔算法(Kruskal)算法

    10)选取边1-2:由于包括该边会导致循环,因此请将其丢弃。

    11)选取边3-4:不形成循环,将其包括在内。

查找最小生成树:克鲁斯克尔算法(Kruskal)算法

   由于包含的边数等于(V – 1),因此算法结束。

三、算法代码

并查集:

  在计算机科学中,并查集是一种树型的数据结构,用于处理一些不交集(Disjoint Sets)的合并及查询问题。有一个联合-查找算法union-find algorithm)定义了两个用于此数据结构的操作:

  • Find:确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。

  • Union:将两个子集合并成同一个集合。

  并查集树是一种将每一个集合以表示的数据结构,其中每一个节点保存着到它的父节点的引用。

在并查集树中,每个集合的代表即是集合的根节点。“查找”根据其父节点的引用向根行进直到到底树根。“联合”将两棵树合并到一起,这通过将一棵树的根连接到另一棵树的根。实现这样操作的一种方法是:

  查找元素 i 的集合,根据其父节点的引用向根行进直到到底树根

private int find(Subset[] subsets, int i) {
        if (subsets[i].parent != i)
            subsets[i].parent = find(subsets, subsets[i].parent);   // 路径压缩,找到最久远的祖先时“顺便”把它的子孙直接连接到它上面
        return subsets[i].parent;
    }

  将两组不相交集合 x 和 y 进行并集,找到其中一个子集最父亲的父亲(也就是最久远的祖先),将另外一个子集的最久远的祖先的父亲指向它

public void union(Subset[] subsets, int x, int y) {
        int xroot = find(subsets, x);
        int yroot = find(subsets, y);

        /* 在高秩树的根下附加秩低树(按秩划分合并) */
        if (subsets[xroot].rank < subsets[yroot].rank) {
            subsets[xroot].parent = yroot;
        } else if (subsets[xroot].rank > subsets[yroot].rank){
            subsets[yroot].parent = xroot;
        } else {    // 当两棵秩同为r的树联合(作并集)时,它们的秩r+1
            subsets[yroot].parent = xroot;
            subsets[xroot].rank++;
        }
    }

  同时使用路径压缩、按秩(rank)合并优化的程序每个操作的平均时间仅为 O(α (n)),其中α (n) 是 n=f(x)=A(x, x) 的反函数,A 是急速增加的阿克曼函数。因为 α(n) 是其反函数,故 α (n) 在 n 十分巨大时还是小于 5。因此,平均运行时间是一个极小的常数。实际上,这是渐近最优算法。

Kruskal算法

  使用算法的思想来构造MST。

/**
     * 使用Kruskal算法构造MST
     */
    public void kruskalMST() {
        Edge[] result = new Edge[V]; // 将存储生成的MST
        int e = 0;                   // 用于result[]的索引变量
        int i = 0;                   // 用于排序的边缘索引变量
        for (i = 0; i < V; ++i) {
            result[i] = new Edge();
        }

        /* 步骤一:对点到点的边的权重进行排序 */
        Arrays.sort(edges);

        /* 创建V个子集*/
        Subset[] subsets = new Subset[V];
        for (i = 0; i < V; i++) {
            subsets[i] = new Subset();
        }

        /* 使用单个元素创建V子集 */
        for (int v = 0; v < V; v++) {
            subsets[v].parent = v;
            subsets[v].rank = 0;    // 单元素的树的秩定义为0
        }

        /* 用于挑选下一个边的索引 */
        i = 0;

        while (e < V-1) {
            /* 步骤2:选取最小的边缘, 并增加下一次迭代的索引 */
            Edge next_edge = edges[i++];

            int x = find(subsets, next_edge.src);
            int y = find(subsets, next_edge.dest);

            /* 如果包括此边不引起mst成环(树本无环),则将其包括在结果中并为下一个边增加结果索引存下一条边 */
            /* 这里判断两个元素是否属于一个子集 */
            if (x != y) {
                result[e++] = next_edge;
                union(subsets, x, y);
            }
            /* 否则丢弃next_edge */
        }

        /* 打印result[]的内容以显示里面所构造的MST */
        System.out.println("Following are the edges in the constructed MST");
        for (i = 0; i < e; ++i) {
            System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);
        }
    }

平均时间复杂度为O (|E|·log |V|),其中 E 和 V 分别是图的边集和点集。

本文源代码:

package algorithm.mst;

import java.util.Arrays;

public class KruskalAlgorithm {
    /* 顶点数和边数 */
    private int V, E;
    /* 所有边的集合 */
    private Edge[] edges;

    /**
     * 创建一个V个顶点和E条边的图
     *
     * @param v
     * @param e
     */
    public KruskalAlgorithm(int v, int e) {
        V = v;
        E = e;
        edges = new Edge[E];
        for (int i = 0; i < e; i++) {
            edges[i] = new Edge();
        }
    }

    /**
     * 查找元素i的集合(路径压缩)
     * 根据其父节点的引用向根行进直到到底树根
     *
     * @param subsets
     * @param i
     * @return
     */
    private int find(Subset[] subsets, int i) {
        if (subsets[i].parent != i)
            subsets[i].parent = find(subsets, subsets[i].parent);   // 路径压缩,找到最久远的祖先时“顺便”把它的子孙直接连接到它上面
        return subsets[i].parent;
    }

    /**
     * 将两组不相交集合x和y进行并集(按秩合并)
     * 这个方法找到其中一个子集最父亲的父亲(也就是最久远的祖先),将另外一个子集的最久远的祖先的父亲指向它。
     * <p>
     *     并查集树的最基础的表示方法,这个方法不会比链表法好,
     *     这是因为创建的树可能会严重不平衡。
     *     所以采用“按秩合并”来优化。
     * </p>
     * <p>
     *     即总是将更小的树连接至更大的树上。因为影响运行时间的是树的深度,
     *     更小的树添加到更深的树的根上将不会增加秩除非它们的秩相同。
     *     在这个算法中,术语“秩”替代了“深度”,因为同时应用了路径压缩时秩将不会与高度相同。
     * </p>
     *
     * @param subsets
     * @param x
     * @param y
     */
    public void union(Subset[] subsets, int x, int y) {
        int xroot = find(subsets, x);
        int yroot = find(subsets, y);

        /* 在高秩树的根下附加秩低树(按秩划分合并) */
        if (subsets[xroot].rank < subsets[yroot].rank) {
            subsets[xroot].parent = yroot;
        } else if (subsets[xroot].rank > subsets[yroot].rank){
            subsets[yroot].parent = xroot;
        } else {    // 当两棵秩同为r的树联合(作并集)时,它们的秩r+1
            subsets[yroot].parent = xroot;
            subsets[xroot].rank++;
        }
    }

    /**
     * 使用Kruskal算法构造MST
     */
    public void kruskalMST() {
        Edge[] result = new Edge[V]; // 将存储生成的MST
        int e = 0;                   // 用于result[]的索引变量
        int i = 0;                   // 用于排序的边缘索引变量
        for (i = 0; i < V; ++i) {
            result[i] = new Edge();
        }

        /* 步骤一:对点到点的边的权重进行排序 */
        Arrays.sort(edges);

        /* 创建V个子集*/
        Subset[] subsets = new Subset[V];
        for (i = 0; i < V; i++) {
            subsets[i] = new Subset();
        }

        /* 使用单个元素创建V子集 */
        for (int v = 0; v < V; v++) {
            subsets[v].parent = v;
            subsets[v].rank = 0;    // 单元素的树的秩定义为0
        }

        /* 用于挑选下一个边的索引 */
        i = 0;

        while (e < V-1) {
            /* 步骤2:选取最小的边缘, 并增加下一次迭代的索引 */
            Edge next_edge = edges[i++];

            int x = find(subsets, next_edge.src);
            int y = find(subsets, next_edge.dest);

            /* 如果包括此边不引起mst成环(树本无环),则将其包括在结果中并为下一个边增加结果索引存下一条边 */
            /* 这里判断两个元素是否属于一个子集 */
            if (x != y) {
                result[e++] = next_edge;
                union(subsets, x, y);
            }
            /* 否则丢弃next_edge */
        }

        /* 打印result[]的内容以显示里面所构造的MST */
        System.out.println("Following are the edges in the constructed MST");
        for (i = 0; i < e; ++i) {
            System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);
        }
    }

    public static void main(String[] args) {
        /**
         * 排序后:
         * 权重-src-dest
         * 1 6 7
         * 2 2 8
         * 2 5 6
         * 4 0 1
         * 4 2 5
         * 6 6 8
         * 7 2 3
         * 7 7 8
         * 8 0 7
         * 8 1 2
         * 9 3 4
         * 10 4 5
         * 11 1 7
         * 14 3 5
         */
        int V = 9;
        int E = 14;
        KruskalAlgorithm graph = new KruskalAlgorithm(V, E);

        /* 另一个用例的图:
              1 --- 2 --- 3
            / |     | \   | 151            0  |     8  \  |  4
            \ |  /  |   \ | /
              7 --- 6 --- 5
         */

        // 添加边 0-1
        graph.edges[0].src = 0;
        graph.edges[0].dest = 1;
        graph.edges[0].weight = 4;

        // 添加边 0-7
        graph.edges[1].src = 0;
        graph.edges[1].dest = 7;
        graph.edges[1].weight = 8;

        // 添加边 1-2
        graph.edges[2].src = 1;
        graph.edges[2].dest = 2;
        graph.edges[2].weight = 8;

        // 添加边 1-7
        graph.edges[3].src = 1;
        graph.edges[3].dest = 7;
        graph.edges[3].weight = 11;

        // 添加边 2-3
        graph.edges[4].src = 2;
        graph.edges[4].dest = 3;
        graph.edges[4].weight = 7;

        // 添加边 2-5
        graph.edges[5].src = 2;
        graph.edges[5].dest = 5;
        graph.edges[5].weight = 4;

        // 添加边 2-8
        graph.edges[6].src = 2;
        graph.edges[6].dest = 8;
        graph.edges[6].weight = 2;

        // 添加边 3-4
        graph.edges[7].src = 3;
        graph.edges[7].dest = 4;
        graph.edges[7].weight = 9;

        // 添加边 3-5
        graph.edges[8].src = 3;
        graph.edges[8].dest = 5;
        graph.edges[8].weight = 14;

        // 添加边 4-5
        graph.edges[9].src = 4;
        graph.edges[9].dest = 5;
        graph.edges[9].weight = 10;

        // 添加边 5-6
        graph.edges[10].src = 5;
        graph.edges[10].dest = 6;
        graph.edges[10].weight = 2;

        // 添加边 6-7
        graph.edges[11].src = 6;
        graph.edges[11].dest = 7;
        graph.edges[11].weight = 1;

        // 添加边 6-8
        graph.edges[12].src = 6;
        graph.edges[12].dest = 8;
        graph.edges[12].weight = 6;

        // 添加边 7-8
        graph.edges[13].src = 7;
        graph.edges[13].dest = 8;
        graph.edges[13].weight = 7;

        graph.kruskalMST();

        /* 用例通过算法得出的MST如下:
               1    2 -- 3
             /      | \   231             0       8  \   4
             \          233                7 -- 6 -- 5
         */
    }

    /**
     * 每条边的信息,实现了{@link Comparable}接口,
     *      可以使用{@link Arrays}的方法随其边的权重的集合进行自然排序。
     */
    class Edge implements Comparable<Edge> {
        /* 这条边的两个顶点和它的权重 */
        private int src, dest, weight;

        @Override
        public int compareTo(Edge o) {
            return this.weight - o.weight;
        }
    }

    /**
     * 联合查找子集的类
     */
    class Subset {
        /* 其祖先和秩 */
        private int parent, rank;
    }
}

相关推荐