克鲁斯卡尔算法

ゝ一世哀愁。 2022-11-15 03:58 170阅读 0赞

一：克鲁斯卡尔算法介绍

1) 克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。 
    2) 基本思想：按照权值从小到大的顺序选择 n-1 条边，并保证这 n-1 条边不构成回路 
    3) 具体做法：首先构造一个只含 n 个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止

克鲁斯卡尔算法图解说明

以城市公交站问题来图解说明 克鲁斯卡尔算法的原理和步骤：

在含有  n  个顶点的连通图中选择  n-1  条边，构成一棵极小连通子图，并使该连通子图中  n-1  条边上权值之和达到最小，则称其为连通网的最小生成树。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70][]

例如，对于如上图  G4  所示的连通网可以有多棵权值总和不相同的生成树。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 1][]

## 1：**克 鲁 斯 卡 尔 算 法 图 解** ##

以上图  G4  为例，来对克鲁斯卡尔进行演示 ( 假设，用数组  R  保存最小生成树结果 ) 。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 5][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 6][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 7][]

第 1 步：将边<E,F>加入 R 中。 边<E,F>的权值最小，因此将它加入到最小生成树结果 R 中。
    第 2 步：将边<C,D>加入 R 中。 上一步操作之后，边<C,D>的权值最小，因此将它加入到最小生成树结果 R 中。 
    第 3 步：将边<D,E>加入 R 中。 上一步操作之后，边<D,E>的权值最小，因此将它加入到最小生成树结果 R 中。 
    第 4 步：将边<B,F>加入 R 中。 上一步操作之后，边<C,E>的权值最小，但<C,E>会和已有的边构成回路；因此，跳过边<C,E>。同理，跳 过边<C,F>。将边<B,F>加入到最小生成树结果 R 中。 
    第 5 步：将边<E,G>加入 R 中。 上一步操作之后，边<E,G>的权值最小，因此将它加入到最小生成树结果 R 中。 
    第 6 步：将边<A,B>加入 R 中。 上一步操作之后，边<F,G>的权值最小，但<F,G>会和已有的边构成回路；因此，跳过边<F,G>。同理，跳 过边<B,C>。将边<A,B>加入到最小生成树结果 R 中。 此时，最小生成树构造完成！它包括的边依次是：<E,F> <C,D>

## 2：**克 鲁 斯 卡 尔 算 法 分 析** ##

根据前面介绍的克鲁斯卡尔算法的基本思想和做法，我们能够了解到，克鲁斯卡尔算法重点需要解决的以下两个问题：

**问题一：** 对图的所有边按照权值大小进行排序。

**问题二：** 将边添加到最小生成树中时，怎么样判断是否形成了回路。

问题一很好解决，采用排序算法进行排序即可。

问题二，处理方式是：记录顶点在 " 最小生成树 " 中的终点，顶点的终点是 " 在最小生成树中与它连通的最大顶点 " 。然后每次需要将一条边添加到最小生存树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。

3： **如 何 判 断 是 否 构 成 回 路 -举 例 说 明 (如 图 )**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 8][]

在将<E,F> <C,D> <D,E>加入到最小生成树 R 中之后，这几条边的顶点就都有了终点：
    (01) C 的终点是 F。 
    (02) D 的终点是 F。 
    (03) E 的终点是 F。 
    (04) F 的终点是 F。

关于终点的说明：

1)  就是将所有顶点按照从小到大的顺序排列好之后；某个顶点的终点就是 " 与它连通的最大顶点 " 。

2)  因此，接下来，虽然 <C,E> 是权值最小的边。但是  C  和  E  的终点都是  F ，即它们的终点相同，因此，将 <C,E> 加入最小生成树的话，会形成回路。这就是判断回路的方式。也就是说，**我们加入的** **边** **的** **两个顶点** **不能** **都指向同一** **个终点** **，否则将构成回路** 。

# 二：克鲁斯卡尔最佳实践\-公交站问题  #

看一个公交站问题：

1) 有北京有新增 7 个站点(A, B, C, D, E, F, G) ，现在需要修路把 7 个站点连通
    2) 各个站点的距离用边线表示(权) ，比如 A – B 距离 12 公里
    3) 问：如何修路保证各个站点都能连通，并且总的修建公路总里程最短?

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 9][]

代码实现：

EData实体类：

package com.kruskal;
    
    /**
     * @author lizhangyu
     * @date 2021/3/30 21:21
     */
    public class EData {
    
        /**
         * 边的一个点
         */
        char start;
    
        /**
         * 边的另外一个点
         */
        char end;
    
        /**
         * 边的权值
         */
        int weight;
    
        /**
         * 构造器
         */
        public EData(char start, char end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
    
        /**
         * 重写 toString, 便于输出边信息
         * @return
         */
        @Override
        public String toString() {
            return "EData [<" + start + ", " + end + ">= " + weight + "]";
        }
    }

KruskalCase实体类：

package com.kruskal;
    
    import java.util.Arrays;
    
    /**
     * @author lizhangyu
     * @date 2021/3/30 21:31
     */
    public class KruskalCase {
    
        /**
         * 边的个数
         */
        private int edgeNum;
    
        /**
         * 顶点数组
         */
        private char[] vertexs;
    
        /**
         * 邻接矩阵
         */
        private int[][] matrix;
    
        /**
         * 使用INF表示两个顶点不能连通
         */
        private static final int INF = Integer.MAX_VALUE;
    
        public static void main(String[] args) {
            char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
            //克鲁斯卡尔算法的邻接矩阵
            int matrix[][] = {
                          /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
                    /*A*/{ 0, 12, INF, INF, INF, 16, 14},
                    /*B*/ { 12, 0, 10, INF, INF, 7, INF},
                    /*C*/ { INF, 10, 0, 3, 5, 6, INF},
                    /*D*/ { INF, INF, 3, 0, 4, INF, INF},
                    /*E*/ { INF, INF, 5, 4, 0, 2, 8},
                    /*F*/ { 16, 7, 6, INF, 2, 0, 9},
                    /*G*/ { 14, INF, INF, INF, 8, 9, 0}
            };
    
            KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);
    
            kruskalCase.print();
    
            System.out.println("开始开启克鲁斯卡尔算法");
            kruskalCase.kruskal();
        }
    
        /**
         * 构造器
         * @param vertexs
         * @param matrix
         */
        public KruskalCase(char[] vertexs, int[][] matrix) {
    
            //初始化顶点数和边的个数
            int vlen = vertexs.length;
    
            //初始化顶点，复制拷贝的方式
            this.vertexs = new char[vlen];
            for (int i = 0; i < vertexs.length; i++) {
                this.vertexs[i] = vertexs[i];
            }
    
            //初始化边，使用的是复制拷贝的方式
            this.matrix = new int[vlen][vlen];
            for (int i = 0; i < vlen; i++) {
                for (int j = 0; j < vlen; j++) {
                    this.matrix[i][j] = matrix[i][j];
                }
            }
    
            //统计边的条数
            for (int i = 0; i < vlen; i++) {
                for (int j = i + 1; j < vlen; j++) {
                    if (this.matrix[i][j] != INF) {
                        edgeNum++;
                    }
                }
            }
    
        }
    
        /**
         * 打印邻接矩阵
         */
        public void print() {
            System.out.println("邻接矩阵为：\n");
            for (int i = 0; i < vertexs.length; i++) {
                for (int j = 0; j < vertexs.length; j++) {
                    System.out.printf("%12d", matrix[i][j]);
                }
                System.out.println();
            }
        }
    
        /**
         * 克鲁斯卡尔算法
         */
        public void kruskal() {
            //表示最后结果数组的索引
            int index = 0;
    
            //用于保存"已有最小生成树"中的每个顶点在最小生成树中的终点
            int[] ends = new int[edgeNum];
    
            //创建结果数组，保存最后的最小生成树
            EData[] rets = new EData[edgeNum];
    
            //获取图中所有的边的集合，一共有12边
            EData[] edges = getEdges();
    
            System.out.println("图的边的集合=" + Arrays.toString(edges) + " 共"+ edges.length);
    
            //按照边的权值大小进行排序（从小到大）
            sortEdges(edges);
    
            System.out.println("排序后的图的边的集合=" + Arrays.toString(edges) + " 共"+ edges.length);
    
            for (int i = 0; i < edgeNum; i++) {
                //获取到第 i 条边的第一个顶点(起点)
                int p1 = getPosition(edges[i].start);
                //获取到第 i 条边的第 2 个顶点
                int p2 = getPosition(edges[i].end);
    
                //获取 p1 这个顶点在已有最小生成树中的终点
                int m = getEnd(ends, p1);
                //获取 p2 这个顶点在已有最小生成树中的终点
                int n = getEnd(ends, p2);
    
                //是否构成回路
                //没有构成回路
                if (m != n) {
                    //设置 m 在"已有最小生成树"中的终点 <E,F> [0,0,0,0,5,0,0,0,0,0,0,0]
                    ends[m] = n;
                    //有一条边加入到 rets 数组
                    rets[index++] = edges[i];
                }
    
            }
    
            //<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。
            // 统计并打印 "最小生成树", 输出 rets
            System.out.println("最小生成树为");
            for (int i = 0; i < index; i++) {
                System.out.println(rets[i]);
            }
        }
    
        /**
         * 功能：对边进行排序处理，冒泡排序
         * @param edges 边的集合
         */
        private void sortEdges(EData[] edges) {
            for (int i = 0; i < edges.length - 1; i++) {
                for (int j = 0; j < edges.length - 1 - i; j++) {
                    if (edges[j].weight > edges[j+1].weight) {
                        EData temp = edges[j];
                        edges[j] = edges[j+1];
                        edges[j+1] = temp;
                    }
                }
            }
        }
    
        /**
         * @param ch 顶点的值，比如'A','B
         * @return 返回 ch 顶点对应的下标，如果找不到，返回-1
         */
        private int getPosition(char ch) {
            for (int i = 0; i < vertexs.length; i++) {
                if (vertexs[i] == ch) {
                    return i;
                }
            }
    
            //找不到
            return -1;
        }
    
        /**
         * 功能: 获取图中边，放到 EData[] 数组中，后面我们需要遍历该数组
         * 通过 matrix 邻接矩阵来获取
         * Data[] 形式 [['A','B', 12], ['B','F',7], .....]
         * @return
         */
        private EData[] getEdges() {
            int index = 0;
    
            EData[] edges = new EData[edgeNum];
    
            for (int i = 0; i < vertexs.length; i++) {
                for (int j = i+1; j < vertexs.length; j++) {
                    if (matrix[i][j] != INF) {
                        edges[index] = new EData(vertexs[i], vertexs[j], matrix[i][j]);
                        index++;
                    }
                }
            }
    
            return edges;
        }
    
        /**
         * 功能: 获取下标为 i 的顶点的终点(), 用于后面判断两个顶点的终点是否相同
         * @param ends 数组就是记录了各个顶点对应的终点是哪个,ends 数组是在遍历过程中，逐步形成
         * @param i 表示传入的顶点对应的下标
         * @return 返回的就是 下标为 i 的这个顶点对应的终点的下标
         */
        private int getEnd(int[] ends, int i) {
            //这里有点不好理解
            while (ends[i] != 0) {
                i = ends[i];
            }
    
            return i;
        }
    }

运行结果：

邻接矩阵为：
    
               0          12  2147483647  2147483647  2147483647          16          14
              12           0          10  2147483647  2147483647           7  2147483647
      2147483647          10           0           3           5           6  2147483647
      2147483647  2147483647           3           0           4  2147483647  2147483647
      2147483647  2147483647           5           4           0           2           8
              16           7           6  2147483647           2           0           9
              14  2147483647  2147483647  2147483647           8           9           0
    开始开启克鲁斯卡尔算法
    图的边的集合=[EData [<A, B>= 12], EData [<A, F>= 16], EData [<A, G>= 14], EData [<B, C>= 10], EData [<B, F>= 7], EData [<C, D>= 3], EData [<C, E>= 5], EData [<C, F>= 6], EData [<D, E>= 4], EData [<E, F>= 2], EData [<E, G>= 8], EData [<F, G>= 9]] 共12
    排序后的图的边的集合=[EData [<E, F>= 2], EData [<C, D>= 3], EData [<D, E>= 4], EData [<C, E>= 5], EData [<C, F>= 6], EData [<B, F>= 7], EData [<E, G>= 8], EData [<F, G>= 9], EData [<B, C>= 10], EData [<A, B>= 12], EData [<A, G>= 14], EData [<A, F>= 16]] 共12
    Disconnected from the target VM, address: '127.0.0.1:56523', transport: 'socket'
    最小生成树为
    EData [<E, F>= 2]
    EData [<C, D>= 3]
    EData [<D, E>= 4]
    EData [<B, F>= 7]
    EData [<E, G>= 8]
    EData [<A, B>= 12]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70]: /images/20221022/92b73602b2c8453abc18289beff83e62.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210330235122392.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20210330235234541.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20210330235243708.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20210330235253210.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/2021033023530327.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20210330235312428.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/2021033023532223.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/2021033023562376.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20210330235856935.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NDY5MDU1,size_16,color_FFFFFF,t_70