Javajava算法
并查集数据结构详解与实战应用
并查集（Disjoint Set）数据结构，包括其定义、基本操作（初始化、查找、合并）及优化技巧（路径压缩、按秩合并）。通过 Java 代码实现了完整的并查集类，并结合力扣例题“水位上升的泳池中游泳”和“省份数量”，展示了并查集在动态连通性问题中的实际应用。文章涵盖了时间复杂度分析及核心算法逻辑，适合希望深入理解图论基础数据结构的开发者阅读。
并查集（Disjoint Set）数据结构，包括其定义、基本操作（初始化、查找、合并）及优化技巧（路径压缩、按秩合并）。通过 Java 代码实现了完整的并查集类，并结合力扣例题“水位上升的泳池中游泳”和“省份数量”，展示了并查集在动态连通性问题中的实际应用。文章涵盖了时间复杂度分析及核心算法逻辑，适合希望深入理解图论基础数据结构的开发者阅读。
并查集是一种用于管理不相交集合（Disjoint Set）的数据结构。它主要用于处理一些需要动态维护集合的合并和查询操作的问题。并查集的核心功能是高效地支持以下两个基本操作：
Find（查询）：确定某个元素属于哪一个集合。 Union（合并）：将两个元素所在的集合合并为一个集合。
并查集通过一个数组（通常称为 parent 数组）来表示每个元素的'父节点'，从而形成一个森林结构。每个集合用一个树来表示，树的根节点即为该集合的代表元素。 例如，假设我们有 5 个元素（0, 1, 2, 3, 4），初始时每个元素都是一个独立的集合： 0 1 2 3 4 对应的 parent 数组为：[0, 1, 2, 3, 4] 每个元素的父节点指向自己，表示每个元素都是一个独立的集合。
当我们需要将两个元素所在的集合合并时，可以通过将一个集合的根节点指向另一个集合的根节点来实现。例如，将元素 1 和元素 0 所在的集合合并：
0 1 2 3 4 \ / 1
此时对应的 parent 数组变为：[1, 1, 2, 3, 4] 此时，元素 1 和元素 0 属于同一个集合，集合的根节点是 1。
查询某个元素属于哪个集合时，我们只需要找到该元素所在树的根节点。例如，查询元素 2 属于哪个集合：find(0) -> find(1) -> 1
元素 0 的根节点是 1，因此元素 2 属于根节点为 1 的集合。
初始化时，每个元素的父节点指向自己，表示每个元素初始时都是一个独立的集合。
public class UnionFind {
private int[] parent; // 父节点数组
private int[] rank; // 秩数组（用于按秩合并）
// 初始化并查集
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i; // 每个元素的父节点初始化为自身
rank[i] = 0; // 每个元素的秩初始化为 0
}
}
}
查找操作的目的是找到某个元素所在的集合的根节点。为了提高效率，通常会使用路径压缩技术，即将查找路径上的所有节点直接指向根节点。
// 查找操作，带路径压缩
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩
}
return parent[x];
}
合并操作是将两个元素所在的集合合并为一个集合。通常会使用**按秩合并（Union by Rank）或按大小合并（Union by Size）**来优化合并操作，避免树变得过高。
// 合并操作，带按秩合并
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;
}
}
}
路径压缩是在查找操作中，将查找路径上的所有节点直接指向根节点，从而减少后续查找的深度。路径压缩的实现非常简单，只需要在 find 函数中添加一行代码即可。
public int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩
}
return parent[x];
}
按秩合并是在合并操作中，总是将秩（树的高度或深度）较小的树合并到秩较大的树上，从而避免树变得过高。秩可以用一个额外的数组 rank 来记录。
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;
}
}
}
public class UnionFind {
private int[] parent; // 父节点数组
private int[] rank; // 秩数组（用于按秩合并）
// 初始化并查集
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i; // 每个元素的父节点初始化为自身
rank[i] = 0; // 每个元素的秩初始化为 0
}
}
// 查找操作，带路径压缩
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;
} {
parent[rootY] = rootX;
rank[rootX] += ;
}
}
}
{
find(x) == find(y);
}
{
( ; i < parent.length; i++) {
System.out.print(parent[i] + );
}
System.out.println();
}
{
( ; i < rank.length; i++) {
System.out.print(rank[i] + );
}
System.out.println();
}
}
{
{
;
(n);
uf.union(, );
uf.union(, );
uf.union(, );
uf.union(, );
uf.union(, );
System.out.println( + uf.isConnected(, ));
System.out.println( + uf.isConnected(, ));
System.out.println( + uf.isConnected(, ));
System.out.print();
uf.printParent();
System.out.print();
uf.printRank();
}
}
并查集可以用于判断图中是否存在环，或者判断图中两个节点是否连通。例如，在最小生成树（Kruskal 算法）中，使用并查集来判断边是否会形成环。
在社交网络中，可以使用并查集来判断两个用户是否属于同一个社交圈子。
并查集可以动态地处理元素的合并和查询操作，适用于需要频繁更新连通性状态的场景。
在一个 n x n 的整数矩阵 grid 中，每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。 当开始下雨时，在时间为 t 时，水池中的水位为 t。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。 你从坐标方格的左上平台 (0，0) 出发。返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间。
示例 1：
示例 2：
这道题目可以用并查集来解决，原因在于并查集能够高效地处理动态连通性问题，即在动态变化的环境中判断两个点是否连通。在这个问题中，随着时间的推移（水位的上升），原本不连通的平台可能会因为水位的升高而变得连通。并查集可以动态地维护这些平台之间的连通性，从而帮助我们找到从起点到终点的最短时间。
**动态连通性：**随着时间的推移，水位上升，原本不连通的平台可能会变得连通。并查集可以动态地处理这种连通性的变化。每当水位上升到某个高度时，所有高度小于或等于该水位的平台都会被淹没，这些平台之间可能会形成新的连通关系。
**高效性：**并查集的查找和合并操作在路径压缩和按秩合并的优化下，几乎可以认为是常数时间复杂度（摊还复杂度为 O(α(n))）。这使得它在处理大规模数据时非常高效。
- 初始化并查集： 初始化一个并查集，将矩阵中的每个平台视为一个独立的集合。
- 排序平台高度： 将矩阵中的所有平台高度提取出来，并按高度从小到大排序。这样我们可以按顺序处理每个平台，确保水位逐渐上升。
- 动态合并平台： 按高度从小到大的顺序处理每个平台。对于每个平台，检查其四个方向（上、下、左、右）的相邻平台。如果相邻平台已经被淹没（即高度小于或等于当前水位），则将当前平台与相邻平台合并到同一个集合中。
- 判断连通性： 每次合并后，检查起点（0, 0）和终点（n-1, n-1）是否连通。如果连通，则当前水位即为所需最少时间。
private int N; // 网格的边长
// 定义四个方向的移动：右、左、下、上
public static final int[][] DIRECTIONS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
public int swimInWater(int[][] grid) {
this.N = grid.length; // 获取网格边长
int len = N * N; // 网格中总的格子数
// 下标：方格的高度，值：对应在方格中的坐标
int[] index = new int[len];
// 建立高度到坐标的映射关系
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
index[grid[i][j]] = getIndex(i, j); // 将高度为 grid[i][j] 的格子映射到坐标 (i,j)
}
}
UnionFind unionFind = new UnionFind(len); // 初始化并查集
// 按照时间（高度）顺序处理每个格子
for (int i = 0; i < len; i++) {
index[i] / N;
index[i] % N;
([] direction : DIRECTIONS) {
x + direction[];
y + direction[];
(inArea(newX, newY) && grid[newX][newY] <= i) {
unionFind.union(index[i], getIndex(newX, newY));
}
(unionFind.isConnected(, len - )) {
i;
}
}
}
-;
}
{
x * N + y;
}
{
x >= && x < N && y >= && y < N;
}
{
[] parent;
{
.parent = [n];
( ; i < n; i++) {
parent[i] = i;
}
}
{
(x != parent[x]) {
parent[x] = parent[parent[x]];
x = parent[x];
}
x;
}
{
root(x) == root(y);
}
{
(isConnected(p, q)) {
;
}
parent[root(p)] = root(q);
}
}
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。 给你一个 n x n 的矩阵 isConnected，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。 返回矩阵中 省份 的数量。
- 理解问题 省份：一组直接或间接相连的城市，组内不含其他没有相连的城市。 目标：统计这些省份的数量。
- 使用并查集 并查集是一种用于管理不相交集合的数据结构，特别适合处理动态连通性问题。它支持两个主要操作： Find：确定某个元素属于哪个集合。 Union：将两个元素所在的集合合并。 在这个问题中，我们可以将每个城市视为一个元素，通过并查集来动态维护城市之间的连通性。
- 初始化并查集 创建一个并查集，包含 n 个城市。 初始时，每个城市是一个独立的集合，每个城市的父节点指向自己，秩为 0。
- 遍历矩阵并合并城市 遍历矩阵 isConnected，对于每对直接相连的城市（isConnected[i][j] == 1），使用并查集的 union 操作将它们合并到同一个集合中。 通过 union 操作，我们可以动态地维护城市之间的连通性。
- 统计连通分量的数量 每次成功合并两个集合时，连通分量的数量减 1。 最终，连通分量的数量即为省份的数量。
// 计算省份数量（连接分量数量）
public int findCircleNum(int[][] isConnected) {
// 边界检查：如果矩阵为空，返回 0
if (isConnected == null || isConnected.length == 0) {
return 0;
}
// 获取城市数量
int n = isConnected.length;
// 初始化并查集，每个城市初始为独立的省份
UnionFind uf = new UnionFind(n);
// 遍历邻接矩阵的每一行（每个城市）
for (int i = 0; i < n; i++) {
// 遍历邻接矩阵的每一列（与其他城市的连接情况）
for (int j = 0; j < n; j++) {
// 如果城市 i 和城市 j 直接相连
if (isConnected[i][j] == 1) {
// 将这两个城市合并到同一个省份中
uf.union(i, j);
}
}
}
// 返回最终的省份数量
return uf.getCount();
}
// 并查集类，用于管理城市的连接关系
class UnionFind {
int root[]; // 每个节点的父节点
int rank[]; // 每个节点的秩（树的高度）
int count; // 当前连通分量的数量
// 构造函数，初始化并查集
{
root = [size];
rank = [size];
count = size;
( ; i < size; i++) {
root[i] = i;
rank[i] = ;
}
}
{
(x == root[x]) {
x;
}
root[x] = find(root[x]);
}
{
find(x);
find(y);
(rootX != rootY) {
(rank[rootX] > rank[rootY]) {
root[rootY] = rootX;
} (rank[rootX] < rank[rootY]) {
root[rootX] = rootY;
} {
root[rootY] = rootX;
rank[rootX] += ;
}
count--;
}
}
{
count;
}
}
以上就是本文全部内容，主要介绍了并查集这一数据结构及其相关常用方法，之后引用了两道例题带大家更加清楚的学习了并查集在具体算法中的应用。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online