算法笔记【1】 Kruskal - 克鲁斯卡尔算法

叁歲伎倆 2023-01-09 03:38 149阅读 0赞

# Kruskal - 克鲁斯卡尔算法求最小生成树 #

本次所介绍的克鲁斯卡尔算法，从边的角度求网的最小生成树时间复杂度为O(NlogN)。和普里姆算法恰恰相反，更适合于求边稀疏的网的最小生成树。

对于任意一个连通网的最小生成树来说，在要求总的权值最小的情况下，最直接的想法就是将连通网中的所有边按照权值大小进行升序排序，从小到大依次选择。

由于最小生成树本身是一棵生成树，所以需要时刻满足以下两点：

*  生成树中任意顶点之间有且仅有一条通路，也就是说，生成树中不能存在回路；
 *  对于具有 n 个顶点的连通网，其生成树中只能有 n-1 条边，这 n-1 条边连通着 n 个顶点。

> 连接 n 个顶点在不产生回路的情况下，只需要 n-1 条边。

所以克鲁斯卡尔算法的具体思路是：将所有边按照权值的大小进行升序排序，然后从小到大一一判断，条件为：如果这个边不会与之前选择的所有边组成回路，就可以作为最小生成树的一部分；反之，舍去。直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。筛选出来的边和所有的顶点构成此连通网的最小生成树。

> 判断是否会产生回路的方法为：在初始状态下给每个顶点赋予不同的标记，对于遍历过程的每条边，其都有两个顶点，判断这两个顶点的标记是否一致，如果一致，说明它们本身就处在一棵树中，如果继续连接就会产生回路；如果不一致，说明它们之间还没有任何关系，可以连接。

假设遍历到一条由顶点 A 和 B 构成的边，而顶点 A 和顶点 B 标记不同，此时不仅需要将顶点 A 的标记更新为顶点 B 的标记，还需要更改所有和顶点 A 标记相同的顶点的标记，全部改为顶点 B 的标记。

![在这里插入图片描述][20210120173315260.jpg_pic_center]

例如，使用克鲁斯卡尔算法找图 1 的最小生成树的过程为：

首先，在初始状态下，对各顶点赋予不同的标记（用颜色区别），如下图所示：

![在这里插入图片描述][20210120173308995.jpg_pic_center]

对所有边按照权值的大小进行排序，按照从小到大的顺序进行判断，首先是（1，3），由于顶点 1 和顶点 3 标记不同，所以可以构成生成树的一部分，遍历所有顶点，将与顶点 3 标记相同的全部更改为顶点 1 的标记，如下图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center]

其次是（4，6）边，两顶点标记不同，所以可以构成生成树的一部分，更新所有顶点的标记为：

![在这里插入图片描述][20210120173253580.jpg_pic_center]

其次是（2，5）边，两顶点标记不同，可以构成生成树的一部分，更新所有顶点的标记为：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 1]

然后最小的是（3，6）边，两者标记不同，可以连接，遍历所有顶点，将与顶点 6 标记相同的所有顶点的标记更改为顶点 1 的标记：

![在这里插入图片描述][20210120173240280.jpg_pic_center]

继续选择权值最小的边，此时会发现，权值为 5 的边有 3 个，其中（1，4）和（3，4）各自两顶点的标记一样，如果连接会产生回路，所以舍去，而（2，3）标记不一样，可以选择，将所有与顶点 2 标记相同的顶点的标记全部改为同顶点 3 相同的标记：

![在这里插入图片描述][20210120173231715.jpg_pic_center]

当选取的边的数量相比与顶点的数量小 1 时，说明最小生成树已经生成。所以最终采用克鲁斯卡尔算法得到的最小生成树为上图所示。

**实现代码**

public static int minCostConnectPoints(int[][] points) { 
        //顶点数
        int n = points.length;
    
        DisjointSetUnion dsu = new DisjointSetUnion(n);
        /* * 获取连通网中的所有的边 并对其进行排序处理 */
        List<Edge> edges = new ArrayList<Edge>();
        for (int i = 0; i < n; i++) { 
            for (int j = i + 1; j < n; j++) { 
                edges.add(new Edge(dist(points, i, j), i, j));
            }
        }
        Collections.sort(edges, Comparator.comparingInt(edge -> edge.len));
    
        int ret = 0, num = 1;
    
        /* * 将所有边按照权值的大小进行升序排序，然后从小到大一一判断，条件为： * 如果这个边不会与之前选择的所有边组成回路，就可以作为最小生成树的一部分；反之，舍去 */
        for (Edge edge : edges) { 
            int len = edge.len, x = edge.x, y = edge.y;
            if (dsu.unionSet(x, y)) { 
                ret += len;
                num++;
                if (num == n) { 
                    break;
                }
            }
        }
        return ret;
    }
    
    public static int dist(int[][] points, int x, int y) { 
        return Math.abs(points[x][0] - points[y][0]) + Math.abs(points[x][1] - points[y][1]);
    }
    
    static class DisjointSetUnion { 
        int[] f;
        int[] rank;
        int n;
    
    
        public DisjointSetUnion(int n) { 
            this.n = n;
            this.rank = new int[n];
            Arrays.fill(this.rank, 1);
            this.f = new int[n];
            for (int i = 0; i < n; i++) { 
                this.f[i] = i;
            }
        }
    
        /** * 找到传入x节点的root节点 * * @param x 顶点 * @return root节点 */
        public int find(int x) { 
            return f[x] == x ? x : (f[x] = find(f[x]));
        }
    
        /** * 判断传入的顶点是否在图中形成回路 */
        public boolean unionSet(int x, int y) { 
            // 找到 x y 的根节点位置 fx fy
            int fx = find(x), fy = find(y);
            // 如果fx = fy 就是同一个根节点 直接返回false
            if (fx == fy) { 
                return false;
            }
    
            if (rank[fx] < rank[fy]) { 
                // 进来代表根节点是fy 为了方便后面rank路径压缩 和 指向root节点 所以交换 fx fy
                int temp = fx;
                fx = fy;
                fy = temp;
            }
            // 选定第一次过来的 fx 为根节点
            rank[fx] += rank[fy];
            // 将fy的位置指向根节点
            f[fy] = fx;
            return true;
        }
    }
    
    static class Edge { 
        int len, x, y;
    
        public Edge(int len, int x, int y) { 
            this.len = len;
            this.x = x;
            this.y = y;
        }
    }

\--------------最后感谢大家的阅读，愿大家技术越来越流弊！--------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]

\--------------也希望大家给我点支持，谢谢各位大佬了！！！--------------

[20210120173315260.jpg_pic_center]: /images/20221119/42317cfbe6204e4eba4d20d8f1a6ce4a.png
[20210120173308995.jpg_pic_center]: /images/20221119/da07acfe30474813a3c80c86a30a806b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/aed964312d32481fbdf28d78eb9d1438.png
[20210120173253580.jpg_pic_center]: /images/20221119/f7da03f45efd4d67aa100c0c82b760b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221119/9d0ae90fc6ab427cac6eaca7e35d394d.png
[20210120173240280.jpg_pic_center]: /images/20221119/453ea9292d254f3ab47a26b4d9172d16.png
[20210120173231715.jpg_pic_center]: /images/20221119/5d04ce6806ab4dbc9537be3b049c9a6d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]: /images/20221119/709c0452ced44acca4d2e705b030f05c.png