并查集数据结构详解与实战应用

一、认识并查集

1. 并查集的定义

并查集是一种用于管理不相交集合（Disjoint Set）的数据结构。它主要用于处理一些需要动态维护集合的合并和查询操作的问题。并查集的核心功能是高效地支持以下两个基本操作：

Find（查询）：确定某个元素属于哪一个集合。 Union（合并）：将两个元素所在的集合合并为一个集合。

2. 基本概念

2.1. 集合的表示

并查集通过一个数组（通常称为 parent 数组）来表示每个元素的'父节点'，从而形成一个森林结构。每个集合用一个树来表示，树的根节点即为该集合的代表元素。 例如，假设我们有 5 个元素（0, 1, 2, 3, 4），初始时每个元素都是一个独立的集合： 0 1 2 3 4 对应的 parent 数组为：[0, 1, 2, 3, 4] 每个元素的父节点指向自己，表示每个元素都是一个独立的集合。

2.2. 合并操作

当我们需要将两个元素所在的集合合并时，可以通过将一个集合的根节点指向另一个集合的根节点来实现。例如，将元素 1 和元素 0 所在的集合合并：

0 1 2 3 4 \ / 1

此时对应的 parent 数组变为：[1, 1, 2, 3, 4] 此时，元素 1 和元素 0 属于同一个集合，集合的根节点是 1。

2.3. 查询操作

查询某个元素属于哪个集合时，我们只需要找到该元素所在树的根节点。例如，查询元素 2 属于哪个集合：find(0) -> find(1) -> 1

元素 0 的根节点是 1，因此元素 2 属于根节点为 1 的集合。

3. 基本操作

3.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
        }
    }
}

3.2. 查找

查找操作的目的是找到某个元素所在的集合的根节点。为了提高效率，通常会使用路径压缩技术，即将查找路径上的所有节点直接指向根节点。

// 查找操作，带路径压缩
public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 路径压缩
    }
    return parent[x];
}

3.3. 合并

合并操作是将两个元素所在的集合合并为一个集合。通常会使用**按秩合并（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;
        }
    }
}

4. 优化技巧

4.1. 路径压缩

路径压缩是在查找操作中，将查找路径上的所有节点直接指向根节点，从而减少后续查找的深度。路径压缩的实现非常简单，只需要在 find 函数中添加一行代码即可。

public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 路径压缩
    }
    return parent[x];
}

4.2. 按秩合并

按秩合并是在合并操作中，总是将秩（树的高度或深度）较小的树合并到秩较大的树上，从而避免树变得过高。秩可以用一个额外的数组 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;
        }
    }
}

5. 代码完整实例

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;
            } else {
                parent[rootY] = rootX;
                rank[rootX] += 1;
            }
        }
    }

    // 判断两个元素是否属于同一个集合
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }

    // 打印当前的父节点数组（用于调试）
    public void printParent() {
        for (int i = 0; i < parent.length; i++) {
            System.out.print(parent[i] + " ");
        }
        System.out.println();
    }

    // 打印当前的秩数组（用于调试）
    public void printRank() {
        for (int i = 0; i < rank.length; i++) {
            System.out.print(rank[i] + " ");
        }
        System.out.println();
    }
}

// 测试并查集
public class Main {
    public static void main(String[] args) {
        int n = 10; // 假设有 10 个元素
        UnionFind uf = new UnionFind(n);
        // 合并一些元素
        uf.union(1, 2);
        uf.union(2, 5);
        uf.union(6, 7);
        uf.union(3, 8);
        uf.union(8, 9);
        // 查询一些元素是否连通
        System.out.println("Is 1 and 5 connected? " + uf.isConnected(1, 5)); // true
        System.out.println("Is 6 and 7 connected? " + uf.isConnected(6, 7)); // true
        System.out.println("Is 1 and 3 connected? " + uf.isConnected(1, 3)); // false
        // 打印当前的父节点数组和秩数组
        System.out.print("Parent array: "); uf.printParent();
        System.out.print("Rank array: "); uf.printRank();
    }
}

6. 应用场景

6.1. 图的连通性

并查集可以用于判断图中是否存在环，或者判断图中两个节点是否连通。例如，在最小生成树（Kruskal 算法）中，使用并查集来判断边是否会形成环。

6.2. 社交网络分析

在社交网络中，可以使用并查集来判断两个用户是否属于同一个社交圈子。

6.3. 动态连通性问题

并查集可以动态地处理元素的合并和查询操作，适用于需要频繁更新连通性状态的场景。

7. 时间复杂度

初始化：O(n)

查找（带路径压缩）：几乎为常数时间，摊还复杂度为 O(α(n)) ，其中 α(n) 是阿克曼函数的反函数，增长非常缓慢。

合并（带按秩合并）：几乎为常数时间，摊还复杂度为 O(α(n)) 。

二、例题实战

例题一

力扣 778、水位上升的泳池中游泳

1. 题目描述：

在一个 n x n 的整数矩阵 grid 中，每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。 当开始下雨时，在时间为 t 时，水池中的水位为 t 。你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台。假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的。当然，在你游泳的时候你必须待在坐标方格里面。 你从坐标方格的左上平台 (0，0) 出发。返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间。

示例 1：

示例 2：

2. 算法思路：

这道题目可以用并查集来解决，原因在于并查集能够高效地处理动态连通性问题，即在动态变化的环境中判断两个点是否连通。在这个问题中，随着时间的推移（水位的上升），原本不连通的平台可能会因为水位的升高而变得连通。并查集可以动态地维护这些平台之间的连通性，从而帮助我们找到从起点到终点的最短时间。

**动态连通性：**随着时间的推移，水位上升，原本不连通的平台可能会变得连通。并查集可以动态地处理这种连通性的变化。每当水位上升到某个高度时，所有高度小于或等于该水位的平台都会被淹没，这些平台之间可能会形成新的连通关系。

**高效性：**并查集的查找和合并操作在路径压缩和按秩合并的优化下，几乎可以认为是常数时间复杂度（摊还复杂度为 O(α(n)) ）这使得它在处理大规模数据时非常高效。

3. 解题思路：

1. 初始化并查集： 初始化一个并查集，将矩阵中的每个平台视为一个独立的集合。
2. 排序平台高度： 将矩阵中的所有平台高度提取出来，并按高度从小到大排序。这样我们可以按顺序处理每个平台，确保水位逐渐上升。
3. 动态合并平台： 按高度从小到大的顺序处理每个平台。对于每个平台，检查其四个方向（上、下、左、右）的相邻平台。如果相邻平台已经被淹没（即高度小于或等于当前水位），则将当前平台与相邻平台合并到同一个集合中。
4. 判断连通性： 每次合并后，检查起点（0, 0）和终点（n-1, n-1）是否连通。如果连通，则当前水位即为所需最少时间。

4. 代码示例：

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++) {
        int x = index[i] / N; // 根据索引获取当前格子的行坐标
        int y = index[i] % N; // 根据索引获取当前格子的列坐标
        // 检查四个方向的相邻格子
        for (int[] direction : DIRECTIONS) {
            int newX = x + direction[0]; // 计算新行坐标
            int newY = y + direction[1]; // 计算新列坐标
            // 如果新坐标在网格范围内且相邻格子的高度小于等于当前时间
            if (inArea(newX, newY) && grid[newX][newY] <= i) {
                // 将当前格子与相邻格子连接
                unionFind.union(index[i], getIndex(newX, newY));
            }
            // 检查起点 (0,0) 和终点 (N-1,N-1) 是否连通
            if (unionFind.isConnected(0, len - 1)) {
                return i; // 如果连通，返回当前时间
            }
        }
    }
    return -1; // 如果始终未连通，返回 -1
}

// 将二维坐标转换为一维索引
private int getIndex(int x, int y) {
    return x * N + y;
}

// 检查坐标是否在网格范围内
private boolean inArea(int x, int y) {
    return x >= 0 && x < N && y >= 0 && y < N;
}

// 并查集内部类
private class UnionFind {
    private int[] parent; // 父节点数组

    // 初始化并查集，每个节点的父节点初始化为自己
    public UnionFind(int n) {
        this.parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    // 查找根节点，并进行路径压缩优化
    public int root(int x) {
        while (x != parent[x]) {
            parent[x] = parent[parent[x]]; // 路径压缩
            x = parent[x];
        }
        return x;
    }

    // 判断两个节点是否连通
    public boolean isConnected(int x, int y) {
        return root(x) == root(y); // 通过比较根节点判断连通性
    }

    // 合并两个集合
    public void union(int p, int q) {
        if (isConnected(p, q)) { // 如果已经连通则直接返回
            return;
        }
        parent[root(p)] = root(q); // 将 p 的根节点连接到 q 的根节点下
    }
}

例题二

1. 题目链接：省份数量
2. 题目描述：

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。 返回矩阵中 省份 的数量。

3. 示例：

4. 算法思路：

1 . 理解问题 省份：一组直接或间接相连的城市，组内不含其他没有相连的城市。 目标：统计这些省份的数量。 2 . 使用并查集 并查集是一种用于管理不相交集合的数据结构，特别适合处理动态连通性问题。它支持两个主要操作： Find：确定某个元素属于哪个集合。 Union：将两个元素所在的集合合并。 在这个问题中，我们可以将每个城市视为一个元素，通过并查集来动态维护城市之间的连通性。 3 . 初始化并查集 创建一个并查集，包含 n 个城市。 初始时，每个城市是一个独立的集合，每个城市的父节点指向自己，秩为 0。 4 . 遍历矩阵并合并城市 遍历矩阵 isConnected，对于每对直接相连的城市（isConnected[i][j] == 1），使用并查集的 union 操作将它们合并到同一个集合中。 通过 union 操作，我们可以动态地维护城市之间的连通性。 5 . 统计连通分量的数量 每次成功合并两个集合时，连通分量的数量减 1。 最终，连通分量的数量即为省份的数量。

5. 代码示例：

// 计算省份数量（连接分量数量）
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; // 当前连通分量的数量

    // 构造函数，初始化并查集
    public UnionFind(int size) {
        root = new int[size]; // 初始化父节点数组
        rank = new int[size]; // 初始化秩数组
        count = size; // 初始时每个城市都是独立的省份
        // 初始化每个节点的父节点为自己，秩为 1
        for (int i = 0; i < size; i++) {
            root[i] = i; // 每个节点初始时是自己的根节点
            rank[i] = 1; // 每个节点初始秩为 1
        }
    }

    // 查找节点的根节点（带路径压缩优化）
    public int find(int x) {
        // 如果 x 是根节点，直接返回
        if (x == root[x]) {
            return x;
        }
        // 路径压缩：将查找路径上的所有节点直接连接到根节点
        return root[x] = find(root[x]);
    }

    // 合并两个节点所在的集合
    public void union(int x, int y) {
        // 找到 x 和 y 的根节点
        int rootX = find(x);
        int rootY = find(y);
        // 如果两个节点不在同一集合中
        if (rootX != rootY) {
            // 按秩合并：将较小的树合并到较大的树下
            if (rank[rootX] > rank[rootY]) {
                // X 的秩更大，将 Y 的根节点连接到 X 的根节点下
                root[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                // Y 的秩更大，将 X 的根节点连接到 Y 的根节点下
                root[rootX] = rootY;
            } else {
                // 秩相等，任选一个作为根节点，并将其秩加 1
                root[rootY] = rootX;
                rank[rootX] += 1;
            }
            // 合并后连通分量数量减 1
            count--;
        }
    }

    // 获取当前连通分量的数量
    public int getCount() {
        return count;
    }
}

总结

以上就是本文全部内容，主要介绍了并查集这一数据结构及其相关常用方法，之后引用了两道例题带大家更加清楚的学习了并查集在具体算法中的应用。