【算法】并查集基础讲解
一、定义
一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。思想是用一个数组表示了整片森林（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 的 父亲节点是 1
int[] 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 的 父亲节点是 1
int[] 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;
}
}