克鲁斯卡尔（Kruskal）算法之加权连通图的最小生成树问题

比眉伴天荒 2023-07-20 08:28 11阅读 0赞

**1.图的几个概念**

（1）连通图：在无向图中，若任意两个顶点vi与vj都有路径相通，则称该无向图为连通图  
（2）强连通图：在有向图中，若任意两个顶点vi与vj都有路径相通，则称该有向图为强连通图  
（3）连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数值，称为权，权代表着连接两个顶点的代价，称这种连通图叫做连通网  
（4）生成树：一个连通图的生成树是指一个连通子图，它含有图中全部 n 个顶点，但只有足以构成一棵树的n-1条边。一棵有n个顶点的生成树有且仅有 n-1 条边，如果生成树中再添加一条边，则必定成环  
（5）最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树(Minimum Cost Spanning Tree)，简称 MST

![Ã¨Â¿Ã©Ã¥Ã¥Â¾Ã§Ã¦Ã¨Â¿Â°][20160714130435508]

**2.并查集的基本介绍**

需要详情，自行百度

// 初始化的模板
    int[] pre = new int[n];
    for(int i = 0; i < n; i++) {
       pre[i] = i;
    }
    
    // 查询的模板(含路径压缩)
    int find(int x){
       if(pre[x] == x) {
    	   return x;
       }
       // 递归
       return pre[x] = find(pre[x]);
    }
    
    // 合并的模板
    void merge(int x, int y){
       int fx = find(x),
       int fy = find(y);
       if(fx != fy) {
           pre[fx] = fy;
       }
    }

**3.克鲁斯卡尔（Kruskal）算法的概述**

用于求解图的最小生成树  
贪心策略：每次都选择权值最小的边作为最小生成树的边

**4.克鲁斯卡尔（Kruskal）算法的基本思路**

（1）构造只有 n 个（图 graph 的顶点集合的大小）顶点的森林，即构造一个数组结构的并查集，初始化为各个顶点的终点为顶点自身  
（2）把图 graph 中顶点连通的边按照权值从小到大进行排序  
（3）按边的权值从小到大取出来，加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止  
（4）此时最小生成树有 n 个顶点，n-1 条边，并且 n-1 条边不构成回路  
加入边需要注意的事项：  
a.判断待加入的边 edge ，加入到当前子图后是否会构成回路，如果构成回路，则取出下一条权值较小的边继续判断，  
b.如果不构成回路，则加入当前边 edge 到当前子图中，逐渐构成最小生成树  
c.构成回路的判断标准：当前待加入的边所对应的两个顶点在当前子图中的终点是否相同  
d.终点的理解：在当前子图中，与待加入的顶点连通的最后顶点（并查集的查询操作）  
比如：已知 A->B 连通（A 的终点为 B），B->C 连通（B 的终点为 C），则通过 并查集 可知 A 的终点为 C（A->C 连通） （可理解为终点的传递性）

**注意**：在使用普里姆算法（Prim）构造最小生成树的过程中，最小生成树必定不会构成回路，因为顶点 ui 是从已经被访问过的顶点集合 U 中获取到的顶点，顶点 vj 是从未被访问过的顶点集合 V-U（差集） 中获取到的顶点，（ui,vj）构成的边加入到最小生成树中必定不会构成回路，但是使用 克鲁斯卡尔算法（Kruskal） 构造最小生成树时，添加边到最小生成树中，存在构成回路的可能，因此要判断加入的边是否会构成回路，使用 并查集 判断是否会构成回路

**5.克鲁斯卡尔（Kruskal）算法的代码实现**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70][]

package com.zzb.algorithm.kruskal;
    
    import java.io.Serializable;
    import java.util.ArrayList;
    import java.util.Comparator;
    
    /**
     * @Auther: Administrator
     * @Date: 2020/3/31 22:08
     * @Description: 克鲁斯卡尔算法：求加权连通图的最小生成树的算法
     * 贪心策略：每次都选择权值最小的边作为最小生成树的边
     */
    public class Kruskal {
        public static void main(String[] args) {
            // 顶点值数组
            String[] vertexArray = {"A", "B", "C", "D", "E", "F", "G"};
            // 邻接矩阵
            final int N = Integer.MAX_VALUE/2; // 表示不可以连接
            int[][] matrix = new int[vertexArray.length][vertexArray.length];
            matrix[0]=new int[]{N,5,7,N,N,N,2};
            matrix[1]=new int[]{5,N,N,9,N,N,3};
            matrix[2]=new int[]{7,N,N,N,8,N,N};
            matrix[3]=new int[]{N,9,N,N,N,4,N};
            matrix[4]=new int[]{N,N,8,N,N,5,4};
            matrix[5]=new int[]{N,N,N,4,5,N,6};
            matrix[6]=new int[]{2,3,N,N,4,6,N};
            // 创建图对象
            Graph graph = new Graph(vertexArray, matrix);
            // 构造最小生成树
            Edge[] edgeArrayOfMST = graph.createMST();
            // 查看详情
            int sum = 0;
            for(int i = 0; i < edgeArrayOfMST.length; i++) {
                System.out.println(edgeArrayOfMST[i]);
                sum += edgeArrayOfMST[i].getWeight();
            }
            System.out.println("总权值 == " + sum);
            /*
            边 <A,G> 权值 2
            边 <B,G> 权值 3
            边 <D,F> 权值 4
            边 <E,G> 权值 4
            边 <E,F> 权值 5
            边 <A,C> 权值 7
            总权值 == 25*/
        }
    }
    
    /**
     * 图类
     */
    class Graph implements Serializable {
        private static final long serialVersionUID = 7611879468252933629L;
    
        // 存储图中各个顶点的集合
        private String[] vertexArray;
        // 存储图中各条边的邻接矩阵
        private int[][] edgeArray;
        // 记录图中各个顶点的终点，用于判断是否构成回路
        // 数组下标代表当前顶点在 vertexArray 中的下标（对应），数组的值代表当前顶点的终点的下标（并查集的使用）
        private int[] endPointArray;
    
        /**
         * 构造器初始化
         *
         * @param vertexArray 顶点
         * @param edgeArray 连接矩阵
         */
        public Graph(String[] vertexArray, int[][] edgeArray) {
            this.vertexArray = vertexArray;
            this.edgeArray = edgeArray;
            // 记录图中各个顶点的终点，用于判断是否构成回路
            // 数组下标代表当前顶点在 vertexArray 中的下标（对应），数组的值代表当前顶点的终点的下标（并查集的使用）
            // 初始化各个顶点的终点为自身（并查集的初始化）
            endPointArray = new int[this.vertexArray.length];
            for(int i = 0; i < endPointArray.length; i++) {
                endPointArray[i] = i;
            }
        }
    
        /**
         * 构造最小生成树
         *
         * @return 以边的数组方式保存最小生成树
         */
        public Edge[] createMST() {
            // 克鲁斯卡尔算法
            Edge[] edgeArrayOfMST = kruskal(this);
            return edgeArrayOfMST;
        }
    
        /**
         * 克鲁斯卡尔算法
         * 贪心策略：每次都选择权值最小的边作为最小生成树的边
         *
         * @param graph 由哪个图来构造最小生成树
         * @return 以边的数组方式保存最小生成树
         */
        private Edge[] kruskal(Graph graph) {
            // 以边的数组方式保存最小生成树
            int index = 0;
            Edge[] edgeArrayOfMST = new Edge[graph.getVertexArray().length - 1];
    
            // graph 的两点之间连通的边封装成 Edge 对象
            // graph 的邻接矩阵的边取值要么是具体的权值，要么就是代表不连通的值 Integer.MAX_VALUE/2
            ArrayList<Edge> edgeList = new ArrayList<>();
            for(int i = 0; i < graph.getEdgeArray().length; i++) {
                for(int j = i+1; j < graph.getEdgeArray()[0].length; j++) {
                    if(graph.getEdgeArray()[i][j] != Integer.MAX_VALUE/2) {
                        edgeList.add(new Edge(graph.vertexArray[i], graph.vertexArray[j], graph.getEdgeArray()[i][j]));
                    }
                }
            }
    
            // 按边的权值从小到大排序
            edgeList.sort(new Comparator<Edge>() {
                @Override
                public int compare(Edge o1, Edge o2) {
                    if(o1.getWeight() < o2.getWeight()) {
                        return -1;
                    }else if(o1.getWeight() > o2.getWeight()) {
                        return 1;
                    }else {
                        return 0;
                    }
                }
            });
    
            int startIndex; // 一条边的开始点的索引
            int endIndex; // 一条边的结束点的索引
            int endPointOfStartIndex; // 一条边的开始点的终点
            int endPointOfEndIndex; // 一条边的结束点的终点
            // 按边的权值从小到大取出来，加入到最小生成树中
            for(Edge edge : edgeList) {
                // 判断待加入的边 edge ，加入到当前子图后是否会构成回路，如果构成回路，则取出下一条权值较小的边继续判断，
                // 如果不构成回路，则加入当前边 edge 到当前子图中，逐渐构成最小生成树
                // 构成回路的判断标准：当前待加入的边所对应的两个顶点在当前子图中的终点是否相同
                // 终点的理解：在当前子图中，与待加入的顶点连通的最后顶点（并查集的查询操作）
                // 比如：A->B 连通（A 的终点为 B），B->C 连通（B 的终点为 C），则通过 并查集 可知 A 的终点为 C （可理解为终点的传递性）
                startIndex = graph.getIndexOfVertex(edge.getStart()); // 顶点
                endIndex = graph.getIndexOfVertex(edge.getEnd()); // 顶点
                endPointOfStartIndex = graph.getIndexOfEndPoint(startIndex); // 终点
                endPointOfEndIndex = graph.getIndexOfEndPoint(endIndex); // 终点
                if(endPointOfStartIndex != endPointOfEndIndex) {
                    edgeArrayOfMST[index] = edge;
                    index++;
                    // 设置 endPointOfStartIndex 的终点为 endPointOfEndIndex
                    graph.merge( endPointOfStartIndex, endPointOfEndIndex);
                }
            }
            // 返回最小生成树
            return edgeArrayOfMST;
        }
    
        /**
         * 获取某个顶点的终点（并查集的查询操作）
         * 
         * @param index 某个顶点在图的顶点集合 vertexArray 中的索引
         * @return 某个顶点的终点
         */
        private int getIndexOfEndPoint(int index) {
            if(this.endPointArray[index] == index) {
                return index;
            }
            // 递归
            return this.endPointArray[index] = getIndexOfEndPoint(this.endPointArray[index]);
        }
    
        /**
         * 设置 endPointOfStartIndex 的终点为 endPointOfEndIndex（并查集的合并操作）
         *
         * @param endPointOfStartIndex 开始点
         * @param endPointOfEndIndex 结束点
         */
        private void merge(int endPointOfStartIndex, int endPointOfEndIndex) {
            this.endPointArray[endPointOfStartIndex] = endPointOfEndIndex;
        }
    
        /**
         * 获取各个顶点所对应的索引
         *
         * @param vertex 顶点所在集合的值
         * @return 获取各个顶点所对应的索引
         */
        private int getIndexOfVertex(String vertex) {
            for(int i = 0; i < this.vertexArray.length; i++) {
                if(vertex.equals(this.vertexArray[i])) {
                    return i;
                }
            }
            return -1;
        }
    
        public String[] getVertexArray() {
            return vertexArray;
        }
    
        public void setVertexArray(String[] vertexArray) {
            this.vertexArray = vertexArray;
        }
    
        public int[][] getEdgeArray() {
            return edgeArray;
        }
    
        public void setEdgeArray(int[][] edgeArray) {
            this.edgeArray = edgeArray;
        }
    }
    
    /**
     * 边类
     */
    class Edge implements Serializable {
        private static final long serialVersionUID = 5009546370782229661L;
    
        // 边的开始点
        private String start;
        // 边的结束点
        private String end;
        // 边的权值
        private int weight;
    
        /**
         * 构造器初始化
         *
         * @param start 边的开始点
         * @param end 边的结束点
         * @param weight 边的权值
         */
        public Edge(String start, String end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
    
        @Override
        public String toString() {
            return "边 <" + this.getStart() + "," + this.getEnd() + "> " + "权值 " + this.getWeight();
        }
    
        public String getStart() {
            return start;
        }
    
        public void setStart(String start) {
            this.start = start;
        }
    
        public String getEnd() {
            return end;
        }
    
        public void setEnd(String end) {
            this.end = end;
        }
    
        public int getWeight() {
            return weight;
        }
    
        public void setWeight(int weight) {
            this.weight = weight;
        }
    }

[20160714130435508]: /images/20230528/1080aff59ade409e80cd07a8ff2e952b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE2NjQ1MDk5_size_16_color_FFFFFF_t_70]: /images/20230528/fe9477389d4e4b7192934c51e927c3d0.png