从“1135. 最低成本联通所有城市”理解克鲁斯卡尔算法、并查集之间的关系
ClEyes-KeThink
1370
2023.07.22
2023.07.22
发布于 未知归属地
并查集Java学习分享

1135. 最低成本联通所有城市


给你整数 n 和一个数组 conections，其中 connections[i] = [xi, yi, costi] 
表示将城市 xi 和城市 yi 连接所要的costi（连接是双向的）。

返回连接所有城市的最低成本，每对城市之间至少有一条路径。
如果无法连接所有 n 个城市，返回 -1

该 最小成本 应该是所用全部连接成本的总和。

image.png

输入：n = 3, conections = [[1,2,5],[1,3,6],[2,3,1]]
输出：6
解释：选出任意 2 条边都可以连接所有城市，我们从中选取成本最小的 2 条。

image.png

输入：n = 4, conections = [[1,2,3],[3,4,4]]
输出：-1
解释：即使连通所有的边，也无法连接所有城市。

image.png

操作：

首先是排序，自行找方法解决即可
但是如何判断有无环呢？难道深搜？广搜？恐怕效率太低。
于是我们需要用到并查集算法。

1.首先，找最小权值的边EF，连接起来

已连接集合：{EF}

此时，F是{EF}的最先祖先
image.png

2. 然后是CD，不会成环，连接起来

已连接集合：{CDEF}

此时，F是{EF}的最先祖先，C是{CD}的最先祖先
image.png

3.然后是DE，不会成环，连接起来

已连接集合：{CDEF} （没变）

此时，{EF}与{CD}合并，{EF}的最先祖先变成C（因为F认C做爸爸了），现在C是{CDEF}的最先祖先
image.png

4. 然后是CE，但是C、E的最先祖先都是C，所以CDE成环，所以放弃，同样CF也成环，放弃，找到BF，不成环（每个点初始的最先祖先都是自己），连接起来

已连接集合：{BCDEF}

此时，C是{BCDEF}的最先祖先
image.png

5. 接下来是GE，不成环，连接起来

已连接集合：{BCDEFG}

此时，G是{BCDEFG}的最先祖先
image.png

6.随后的FG，BC都是会成环，所以放弃，连接AB，不成环

已连接集合：{ABCDEFG}

全部到齐，不需要再找边了（再找一定成环），故最小生成树如下，C是最先祖先：
image.png

注意

我们一般约定，后进集合的点，以及家族成员少的树，认先进集合的点以及家族成员多的树做爸爸。

并查集

  • 是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。
  • 对于图中的两个顶点A和B，通过并查集可以判断是否AB之间是否有路径。
  • 同时，也可以判断将A和B相连之后是否可以形成环，因为如果AB之间有路径的话，那么再将A和B相连就会出现环。

并查集的基本操作

包括：初始化，查找，合并，是否联通。

 //初始化n个节点，初始时，每个元素的父节点是自己！
    private void init(int n) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    //查找当前元素所在树的根节点(代表元素)
    private int find(int x) {
        if (parent[x] != x) {
            //父节点的父节点肯定是其本身，parent[x]内存储的是x的父节点
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public boolean isconnected(int x, int y) {
        return find(x) == find(y);
    }
    
    // 合并
    void  unionSet(int x, int y){
        parent[find(x)] = find(y);
    }

思路逻辑

1.对于每一次连接，找需要连接的两个点的祖先（father的father的father....）直到找到他们的最先的祖先，
比较，如果一样，说明已经连通，不能连接，否则说明可以连接

2.对于每一次成功的连接，后加入“已连接”集合的，都认他所连接的那个已经在集合内的点叫做“father”，
如果两个点都是第一次进集合，那么随便认一个点做“father”

3.对于每一次成功的连接，如果是两个家族连接在一起，那么其中一个家族的最先祖先，认另外一个家族的最先祖先做father

可见，只要最先祖先相同，连接起来一定成环

目的

为了提高查找的效率通常会用到路径压缩。

我们使用数组int parent[maxSize]来存储每个顶点的parent，
parent[i]存储的就是顶点i的father，
如果顶点i与顶点j的father相同，说明他们在一个集合中，那么他们可以连通。

克鲁斯卡尔算法（Kruskal）

贪心算法的典型应用。

作用：

构成最小生成树

说明：

需要用到并查集算法来优化判断回路的过程，相较与Prim，算法稍微复杂,
但编程相对简单，在稀疏图中更优越。

思路逻辑

1.将图中所有的边长权值按从小到大的顺序排列，从小的开始选取边：

①如果发现连上会形成环， 放弃这条边，继续寻找下一个边

②如果发现连上不会成环，连接这条边，并且将这条边两侧的点放入到“已连接”集合中，继续寻找下一个边

2.重复步骤1，直到所有的点都在“已连接”集合中，结束。

代码

public class Solu {
    private int[] parent;

    public int minimumCost(int n, int[][] connections) {
        Arrays.sort(connections, Comparator.comparingInt(a -> a[2]));
        parent = new int[n];
        //初始化n个节点，初始时，每个元素的父节点是自己！
        init(n);
        int ans = 0;
        for (int[] e : connections) {
            int x = e[0] - 1;
            int y = e[1] - 1;
            int cost = e[2];
            if (isconnected(x,y)) {
                continue;
            }
            unionSet(x,y);
            ans += cost;
            if (--n == 1) {
                return ans;
            }
        }
        return -1;
    }

    //初始化n个节点，初始时，每个元素的父节点是自己！
    private void init(int n) {
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    //查找当前元素所在树的根节点(代表元素)
    private int find(int x) {
        if (parent[x] != x) {
            //父节点的父节点肯定是其本身，p[x]内存储的是x的父节点
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public boolean isconnected(int x, int y) {
        return find(x) == find(y);
    }
    
    // 合并
    void  unionSet(int x, int y){
        parent[find(x)] = find(y);
    }
}
评论 (0)