当前位置：首页 > news >正文

DS | 并查集 Disjoint Set Union

news 2025/8/26 0:59:46

1. 概念

集合与并集：

集合（Set）：是一些不重复元素的集合
并集（Union）：是两个集合的组合

查找与合并操作：

合并（Union）：将两个集合合并成一个集合。（连接两个集合的根节点）
查找（Find）：查找某个元素所属集合的根节点，用于判断两个元素是否在同一个集合内。

并查集：

一种数据结构，用来处理一些不相交的集合的合并和查找操作。广泛应用于动态连通性判断的问题，如图的连通分量、网络连接问题等。

2. 实现

2.1 数据结构

用一个数组来表示，对每个元素 'i' ，'parent[ i ]'表示其父节点。
若 'parent[ i ] == i '，那么 'i' 为这个集合的根节点。

节点：集合中每个元素作为一个节点

父节点：节点 'i' 的父节点为 'parent[ i ]'

根节点：一个节点的祖先节点。其自身为自身的父节点

2.2 基本操作

1、初始化：默认自己指向自己

void init()
{for(int i 0; i < n; i ++){parent[i] = i;}
}

2、Find（查找）：查找一个元素所属集合的根节点，递归实现

int Find(int x)
{if(parent[x] != x){return Find(parent[x]);    //无路径压缩}esle return x;
}

3、Join（合并）：将两个不同集合的根节点连接在一起

void Join(int x, int y)
{int rootx = Find(x);int rooty = Find(y);if(rootx != rooty){parent[rootx] = rooty;}
}

3. 路径压缩与按秩合并

3.1 路径压缩 Path Compression

1、为了加速查找操作，通过将路径上所有的节点直接连接到根节点，降低树的高度。

2、实现：每次执行Find操作时将访问节点直接连接到根节点上

int Find(int x)
{if(parent[x] != x){parent[x] = Find(parent[x]);}return parent[x];
}

3.2 按秩合并 Union by Rank/Size

1、为了平衡树的高度，避免生成过高的树而影响查找效率

2、实现：合并两个集合时，将高度较小的树连接到高度较大的树上

rank较小的树接到rank较大的树上；
若rank相等，随便接，被接树rank++；

void Union(int x, int y)
{int rootx = Find(x);int rooty = Find(y); if(rootx != rootu){if(rank[rootx] > rank[rooty]){parent[rooty] = root x;}else if(rank[rootx] < rank[rooty]){parent[rootx] = rooty;}else{parent[rooty] = rootx;rank[rootx] ++;}}
}

3、rank

rank[]：为了保持并查集中树的高度尽可能小而引入的一个辅助数组。
rank：记录了每个集合根节点的“秩”(rank)，即树的近似高度。

初始rank：每个元素初始时自成一个集合，rank初始化为1，表示每棵树的高度为1

更新rank：
rank不同：rank小节点连接到rank大的节点，rank无需更新
rank相同：连接随意但被接节点rank +1

3.3 完整实现

public class UnionFind
{private int[] parent;private int[] rank;// 初始化，每个元素自成一个集合public UnionFind(int size){parent = new int[size];rank = new int[size];for (int i = 0; i < size; i++){parent[i] = i;rank[i] = 1;}}// 查找操作，带路径压缩public int Find(int x){if (parent[x] != x){parent[x] = Find(parent[x]);  // 路径压缩}return parent[x];}// 合并操作，按秩合并public void Union(int x, int y){int rootX = Find(x);int rootY = Find(y);if (rootX != rootY){if (rank[rootX] > rank[rootY]){parent[rootY] = rootX;}else if (rank[rootX] < rank[rootY]){parent[rootX] = rootY;}else{parent[rootY] = rootX;rank[rootX] += 1;}}}
}