【算法】并查集基础讲解

一、定义

一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个集合，只要找到了某个元素的的树根，就能确定它在哪个集合里。

二、例题

让我们一起通过一道题目理解一下并查集解决的问题：
https://leetcode.cn/problems/satisfiability-of-equality-equations/description/

分析上述问题，如果我们用脑子去想的话，该问题是很简单的，但是我们如何用程序解决该问题呢，就需要并查集了

三、核心思想

节点

并查集是一个森林，森林由树组成，树由节点构成，节点就是并查集的元素。

对本题来讲，以 示例1 为例：a 和 b 就是并查集中的两个元素，即两个节点。

树根（父节点）

节点有其父节点，节点组成树结构，树结构有根节点。如果两个节点具有相同的根节点，那么他们就位于同一树中，即两个节点位于同一集合中。

对本题来讲，以 示例4 为例：

• a==b
• b!=c
• c==a

a，b，c 组成一个 ==（等于） 树 ，可以将 a 看作根节点。

所以并查集解决了什么问题？

通过上面的分析，我们可以看出构建并查集后，解决的是 元素是否位于同一集合问题

并查集的构建

下面以 Java 代码为例，解释并查集的构建过程。

初始化并查集

• 使用 parent 数组表示节点的父节点
• 初始化并查集的父节点为其自身

public class UnionFind {// 表示元素（节点）i的父亲节点// parent[0] = 1 , 即 节点0 的 父亲节点是 1int[] parent;// 初始化并查集元素的父亲节点为其自身public void init(int n){for (int i=0; i<n; i++){parent[i] = i;}}
}

找到根节点

• 通过上文，我们得知了如果判断两个元素是否位于同一集合的方法为：判断两个元素是否具有相同的根节点
• 根节点的判断：根节点的根节点为其自身
• 寻找根节点的过程使用递归

    public int findRoot(int u){// 如果节点 u 的父亲节点为其自身，说明当前节点为根节点if(u == parent[u]){return u;}// 递归寻找根节点return findRoot(parent[u]);}

合并元素

• 如果节点 u 与 v 具有关联关系（位于同一集合），就需要合并元素 u 和 v
• 合并过程：将节点 v 的根设置为节点 u 的根节点

    public void merge(int u, int v){u = findRoot(u);v = findRoot(v);parent[v] = u;}

四、综合解决问题

通过上面的内容已经对并查集有了基础了解，下面我们来看如何使用上面的内容，结合一点思考，完整解决例题。

分析

• 构建等式并查集
• 遍历不等式，如若不等式 b != a，但 b 与 a 位于同一等式集合（树），则说明不可能成立。
• 一些细节处理

代码

package leet;import java.util.HashMap;
import java.util.Map;class Solution {// 表示元素（节点）i的父亲节点// parent[0] = 1 , 即 节点0 的 父亲节点是 1int[] parent;// 初始化并查集元素的父亲节点为其自身public void init(int n){for (int i=0; i<n; i++){parent[i] = i;}}public int findRoot(int u){// 如果节点 u 的父亲节点为其自身，说明当前节点为根节点if(u == parent[u]){return u;}// 递归寻找根节点return findRoot(parent[u]);}// 合并元素 u v 到同一集合public void merge(int u, int v){u = findRoot(u);v = findRoot(v);parent[v] = u;}// 核心方法public boolean equationsPossible(String[] equations) {// 得到并查集元素数量 n 并进行编号Map<Character, Integer> map;map = countN(equations);int n = map.size();// 初始化并查集parent = new int[n];init(n);// 构建并查集，建立等式之间的元素关系for (int i=0; i<equations.length; i++){char a = equations[i].charAt(0);char b = equations[i].charAt(3);if(equations[i].charAt(1) == '=') {merge(map.get(a), map.get(b));}}// 遍历所有不等式for (int i=0; i<equations.length; i++) {char a = equations[i].charAt(0);char b = equations[i].charAt(3);// 第一种不成立情况 a != a (自身不等于自身)if( a == b && equations[i].charAt(1) == '!'){return false;}// 如果元素未出现在等式中，第一次出现在不等式中 无影响 即：a == b  b != c —— c 不在 map 中，c 也不影响结果if (map.containsKey(a) && map.containsKey(b)) {if (equations[i].charAt(1) == '!') {// 判断 a,b 是否在同一集合// a,b在同一相等集合中，则说明不成立if (findRoot(map.get(a)) == findRoot(map.get(b))) {return false;}}}}return true;}// 工具类// 为字符编号public Map<Character, Integer> countN(String[] equations){Map<Character, Integer> map = new HashMap<>();int index = 0;for (int i=0; i<equations.length; i++){char a = equations[i].charAt(0);char b = equations[i].charAt(3);if(equations[i].charAt(1) == '='){if(!map.containsKey(a)){map.put(a, index);index++;}if(!map.containsKey(b)){map.put(b, index);index++;}}}return map;}
}