初探并查集

Chemlez

数据结构与算法

发布于：Mar 17, 2021

本文用来记录对并查集的学习与总结，并通过leetcode的两道题目来加深对其的理论与实战学习(实现代码Java)。学习一种数据结构，最高效的方式，就是学以致用，所以这里，以leetcode的题目为例。

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一：”a==b” 或 “a!=b”。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。

只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。

示例1：

输入：["a==b","b!=a"]
输出：false
解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。

示例2：

输入：["b==a","a==b"]
输出：true
解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。

一、并查集介绍

并查集：并查集支持查找和合并两种操作的数据结构。并查集是一种树型的数据结构，用于处理一些不相交集合(disjoint sets)的合并及查询问题。常常在使用中以森林来表示。主要用于解决一些元素分组的问题。管理一系列不相交的集合。

本质：用集合中的某个元素来代表整个集合，该元素称为集合的代表元。

操作：

合并(Union):把两个不相交的集合合并为一个集合。
查询(Find):查询两个元素是否在一个集合中。

并查集的基本使用场景：

相等传递(例如：等式判断的连通性)。由于相等关系具有传递性，所有相等的变量属于一个集合中。
只关心连通性，不关心距离。

具有以上的条件，就可以考虑并查集。

特点：

并查集用于判断一个元素是否相连，它们的关系是动态添加的，这一类问题叫做动态连通性问题。
主要支持合并与查询是否在同一个集合的操作。
底层结构是数组或者哈希表，用于表示节点指向的父节点，初始化时指向自己。
合并就是把一个集合的根节点指向另一个集合的根节点，只表示在同一个集合里。
这种表示不相交集合的方法称为代表元法，以每个节点的根节点作为一个集合的代表元。

典型应用：最小生成树、Kruskal算法。

优化：采用压缩算法。路径压缩，按秩压缩。

以上是理论部分：

结合：算法学习笔记:并查集，简单易懂，强烈推荐。

二、题解

针对题一：

==看作是连接两个节点的边。变量看作是图中的一个节点。所有相等的变量属于同一个连通分量。

首先遍历所有的等式，构造并查集。同一个等式中的两个变量属于同一个连通分量，因此将两个变量进行合并。
遍历所有的不等式。同一个不相等的两个变量不能属于同一个连通分量，因此对两个变量分别查找其所在的连通分量，如果两个变量在同一个连通分量中，则产生矛盾，返回false。
实现方式：使用一个数组parent存储每个变量的连通分量信息，其中的每个元素表示当前变量所在的连通分量的父节点信息，如果父节点是自身，说明该变量为所在的连通分量的根节点。一开始所有变量的父节点都是它们自身。对于合并操作，我们将第一个变量的根节点的父节点指向第二个变量的根节点；对于查找操作，我们沿着当前变量的父节点一路向上查找，直到找到根节点。

public boolean unionSetMethod(String[] equations){
    /**
        思路：采用并查集。
        1.首先遍历所有的等式，将等式中的character添加到同一个集合中；如果出现相交情况就将两个集合进行合并。
        2.其次对所有的不等式进行遍历，对不等式两边的字母进行查询，如果属于同一个集合，就返回false;
        3.当遍历完所有的不等式后，如果未返回false，则表示所有的不等式\等式成立。

        注意：字符串的长度为 定长4.
    **/

    int[] union = new int[26]; // 代表26个字符; 0->a,1->b,2->c,3->d,....,25->z
    
    // 初始化并查集，当前每个元素的根节点就是其自身
    for(int i = 0;i < union.length;++i){
        union[i] = i;
    }

    // 遍历全部的等式，添加到union中
    for(int i = 0;i < equations.length;++i){
        String currentString = equations[i];
        if(currentString.charAt(1) == '=') { // 当前式子 是等式 其中 char 是基本类型，直接使用 == 比较即可，对等式两边进行merge操作
            int indexOne = currentString.charAt(0) - 'a';
            int indexTwo = currentString.charAt(3) - 'a';
            merge(indexOne,indexTwo,union);
        }
    }

    for(int i = 0;i < equations.length;++i){
        String currentString = equations[i];
        if(currentString.charAt(1) == '!') { // 当前等式是 不等式，对不等式两边进行查询操作，判断两变量是否在同一个集合中
            int indexOne = currentString.charAt(0) - 'a';
            int indexTwo = currentString.charAt(3) - 'a';
            if(find(indexOne,union) == find(indexTwo,union)) { 
                return false; // 同属于同一个集合中，矛盾。返回 false.
            }
        }
    }
    return true;
}

// 返回当前节点的根节点
public int find(int x,int[] array){
    
    return array[x] == x ? x : (array[x] = find(array[x],array)); // 路径压缩  边查询 边将 当前节点 接入到根节点上
}

public void merge(int i,int j,int[] array){ // 第一个节点根节点 连接到 第二个节点的根节点上
    array[find(i,array)] = find(j,array);
}

题二：

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。

返回所有问题的答案。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。

注意：输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。

示例一：

输入：equations = [[“a”,”b”],[“b”,”c”]], values = [2.0,3.0], queries = [[“a”,”c”],[“b”,”a”],[“a”,”e”],[“a”,”a”],[“x”,”x”]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]
解释：
条件：a / b = 2.0, b / c = 3.0
问题：a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
结果：[6.0, 0.5, -1.0, 1.0, -1.0 ]

实例二：

输入：equations = [[“a”,”b”],[“b”,”c”],[“bc”,”cd”]], values = [1.5,2.5,5.0], queries = [[“a”,”c”],[“c”,”b”],[“bc”,”cd”],[“cd”,”bc”]]
输出：[3.75000,0.40000,5.00000,0.20000]

实现核心：变量和变量之间具有倍数关系。由于变量之间的倍数关系具有传递性，处理具有传递性关系的问题，可以使用并查集.在并查集的合并和查询操作中维护这些变量之间的倍数关系。
构建方式：采用带权的有向图(其中一个边对应一个权值，每个点都有自己的权值，初始化时，默认的权值是1)；并且，在维护该并查集时，除了根节点以外，所有同在一个连通分量中的父亲节点均为根节点。
路径压缩：在查询一个结点a的根节点同时，把节点a到根节点的沿途所有节点的父亲节点都指向根节点。这样，除了根结点以外，所有结点的父亲结点都指向了根结点。
结果：两个同在一个连通分量中的不同的变量，它们分别到根结点（父亲结点）的权值的比值，就是题目的要求的结果。即先判断两个节点是否在同一个集合中，如果在同一个集合中，就分别取出其对应的weight值，然后求出相应的比值就是结果。
细节点：并查集的查询操作会执行路径压缩。
并查集的特点：一边查询，一边修改节点指向是并查集的特色。(修改的方式：采用路径压缩算法。具体的实现：采用递归的方式)。
tips:
处理数字比处理字母方便的多，因此将变量的值与id进行唯一映射；此后就可以用该id唯一表示这个变量。

具体的实现步骤：

遍历每个等式，并传入相应的value值。
将该等式中的两个value传入相应的集合中。
查询给定的queries中的值，将结果添加到结果集中。
返回结果

UinonFindSet类的设计模式。

初始化构造方法的编写。
union，合并集合的方法。
查找方法。边查找，边调整并查集。（采用递归的方式）

public double[] unionSetMethod(List<List<String>> equations, double[] values, List<List<String>> queries) {

    int id = 0;
    double[] res = new double[queries.size()];
    Map<String,Integer> map = new HashMap<>(); // 用于做出字母和id的映射
    UnionSet unionSet = new UnionSet(equations.size() * 2); // 并查集的创建，这里是其最大的长度

    // 做字母和id的映射
    for(int i = 0;i < equations.size();++i){
        String oString = equations.get(i).get(0);
        String tString = equations.get(i).get(1);
        if(!map.containsKey(oString)){
            map.put(oString,id);
            ++id;
        }
        if(!map.containsKey(tString)) {
            map.put(tString,id);
            ++id;
        }

        unionSet.union(map.get(oString),map.get(tString),values[i]);
    }

    for(int i = 0;i < queries.size();++i){
        Integer x = map.get(queries.get(i).get(0));
        Integer y = map.get(queries.get(i).get(1));
        res[i] = unionSet.isConnection(x,y);
    }

    return res;
}

// 对该并查集类的设计
private class UnionSet {

    int[] parent; // 并查集实现 -- 采用数组的形式实现
    double[] weight; // 每个点的权值 初始化1.0

    public UnionSet(int count) {
        this.parent = new int[count];
        this.weight = new double[count];
        for(int i = 0;i < count;++i){
            this.parent[i] = i; // 当前节点的父节点是其自身
            this.weight[i] = 1.0d; // 权重初始值为 1.0d
        }
    }

    // find Method 查询出当前节点的根节点，并且查询时，采用路径压缩算法，对沿途的节点全指向根节点(根节点除外)
    public int find(int x){ 

        if(x == parent[x]){
            return x;
        }else {
            int origin = parent[x]; // 记录该层的父节点 -- 便于利用当前父节点的权值
            parent[x] = find(parent[x]); // 路径压缩
            weight[x] *= weight[origin]; // 更新权值
            return parent[x];
        }

    }

    // merge Method 合并两个集合
    public void union(int x,int y,double value){

        if(find(x) == find(y)){ // 当前两个元素已经在同一个集合中
            return;
        }

        int rootX = find(x); // x 的根节点
        int rootY = find(y); // y 的根节点
        weight[rootX] = value * weight[y] / weight[x]; // 更新 rootX 的权值
        parent[rootX] = rootY; // 连接两个根节点
    }

    // 结果求解
    public double isConnection(Integer x,Integer y){
        if(x == null || y == null){ // 不在原等式中的字母
            return -1.0d;
        }else if(find(x) != find(y)) { // 当前两个节点 不在同一个集合中，返回false(-1.0d)
            return -1.0d;
        }else {
            return weight[x] / weight[y]; // 返回结果
        }
    }
}

三、总结

初始化：

public void init(int n)
{
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
}

此时每个节点的父节点都是自身。

查询操作：

public int find(int x)
{
    if(fa[x] == x)
        return x;
    else
        return find(fa[x]);
}

递归查询，每个节点都指向其父节点，只有查询到当前集合的根节点时，其父节点是指向其自身，那么就返回当前集合的代表元。即：一层一层访问父节点，直至根节点（根节点的标志就是父节点是本身）。要判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。

合并操作：

public void merge(int i, int j)
{
    fa[find(i)] = find(j);
}

合并操作也是很简单的，先找到两个集合的代表元素，然后将前者的父节点设为后者即可。当然也可以将后者的父节点设为前者，这里暂时不重要。这里没有采用压缩算法，最终造成的结果是树的深度很长，形成一条直链，导致查询效率较低。

路径压缩：把沿途的每个节点的父节点都设为根节点。

public int find(int x)
{
    if(x == fa[x])
        return x;
    else{
        fa[x] = find(fa[x]);  //父节点设为根节点
        return fa[x];         //返回父节点
    }
}

该算法的核心是，边查找边进行压缩。这里是将每个节点都直接指向该集合中的代表元(通过递归的方式)。

按秩合并：将简单的树往复杂的树上合并，因为这样合并后，到根节点距离变长的节点个数比较少。(这里简单和复杂是指树的高度，高度越高越为复杂)

初始化：(按秩合并)

public void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        fa[i] = i;
        rank[i] = 1;
    }
}

合并（按秩合并）

public void merge(int i, int j)
{
    int x = find(i), y = find(j);    //先找到两个根节点
    if (rank[x] <= rank[y])
        fa[x] = y;
    else
        fa[y] = x;
    if (rank[x] == rank[y] && x != y)
        rank[y]++;                   //如果深度相同且根节点不同，则新的根节点的深度+1
}

数组中第K大问题之堆排序

这次在刷Leetcode时，在求解数组中的第K大问题时，想到了使用堆排序，因此本篇文章用于巩固对堆排序的学习以及代码实现。题目描述：在未排序的数组中找到第 k 个最大的元素。请注意，你需要找...

Java比较器之Comparator和Comparable

本文用来简单记录Java中Comparator和Comparable接口特点与使用。首先，分别查看官方对这两个接口的描述定义：一、Comparator接口 This is a functio...

初探并查集

一、并查集介绍

二、题解

三、总结

数据结构之前缀树