【唐叔学算法】第八天：并查集-图论连通性的大杀器

你是否曾为如何高效地解决图论中的连通性问题而烦恼？并查集算法，就像一张无形的网，能帮你轻松连接所有节点。今天，就让我们一起揭开并查集算法的神秘面纱，探索它在Java编程中的应用。

并查集是什么？

并查集（Union-Find）是一种数据结构，用于处理一些不交集的合并及查询问题。它支持两种操作：

• 合并（Union）：将两个集合合并为一个集合。
• 查询（Find）：查询某个元素所属的集合。

并查集算法通常采用树形结构表示，每个节点包含一个指向父节点的指针。通过不断向上回溯，可以找到该节点所属的集合的代表元素。

并查集的应用场景

并查集算法广泛应用于以下场景：

• 动态连通性问题：处理动态加入或删除边的情况。
• 网络流问题：判断两个节点是否在同一个网络流中。
• 图的连通性检测：判断两个顶点是否在同一个连通分量内。
• 社交网络分析：判断两个用户是否属于同一个社交圈。
• 等价类划分：将具有相同属性的元素划分到同一个集合中。

并查集的使用

使用并查集算法的关键在于：

1. 初始化：创建一个并查集，并为每个元素设置一个父节点，指向自身。
2. 查询（Find）：使用路径压缩技术，将查询路径上的所有节点都指向代表元素，从而提高查询效率。
3. 合并（Union）：使用按秩合并技术，将两个集合合并为一个集合，并保持树的高度最小。

说明：

• 路径压缩：在查找过程中，将查找路径上的所有节点直接指向根节点，以加速后续查找。
• 按秩合并：在合并时，优先将较小的树合并到较大的树上，以保持树的平衡。

注意事项

在使用并查集算法时，需要注意以下几点：

• 初始化：确保每个元素的初始状态正确，避免后续操作出错。
• 路径压缩：可以显著提高查询效率，但会增加合并操作的复杂度。
• 按秩合并：可以保持树的高度最小，从而提高查询和合并的效率。
• 时间复杂度：并查集算法的查询和合并操作的平均时间复杂度通常为 O(α(n))，其中 α(n) 是阿克曼函数的反函数，增长非常缓慢。

LeetCode实战

入门题目 - 200. 岛屿数量

题目描述： 给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

解题思路

将每个岛屿视为一个集合，通过并查集算法判断两个陆地单元格是否属于同一个岛屿。遍历所有单元格，如果是陆地，则将其与周围陆地单元格进行合并。

Java代码实现

public class Solution {
    public int numIslands(char[][] grid) {
        int m = grid.length, n = grid[0].length;
        UnionFind uf = new UnionFind(m * n);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    int idx = i * n + j;
                    if (i > 0 && grid[i - 1][j] == '1') {
                        uf.union(idx, (i - 1) * n + j);
                    }
                    if (j > 0 && grid[i][j - 1] == '1') {
                        uf.union(idx, i * n + (j - 1));
                    }
                }
            }
        }
        return uf.getCount();
    }
}

/**
 * 并查集类
 */
class UnionFind {
    private int[] parent;
    private int[] rank;
    private int count;

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        count = size;
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i] = 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[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            count--;
        }
    }

    public int getCount() {
        return count;
    }
}

中等难度题目 - 547. 省份数量

题目描述： 有 n 个城市和一些双向连接这些城市的道路。每个城市与相邻城市直接相连，共计有 m 条道路。返回城市的省份数量。

解题思路

与岛屿数量类似，将每个城市视为一个集合，通过并查集算法判断两个城市是否属于同一个省份。遍历所有道路，将相邻城市进行合并。

Java代码实现

public int findCircleNum(int[][] isConnected) {
    int n = isConnected.length;
    UnionFind uf = new UnionFind(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (isConnected[i][j] == 1) {
                uf.union(i, j);
            }
        }
    }
    return uf.getCount();
}

更多LeetCode题目推荐

如果您对并查集算法感兴趣，希望挑战更多题目，以下是一些LeetCode上推荐的题目：

• 130. 被围绕的区域

• 399. 除法求值

• 684. 冗余连接

• 990. 等式方程的可满足性

结语

并查集算法就像一张无形的网，能帮你轻松连接所有节点。希望本文能让你对并查集算法有更深入的理解，并在实际编程中灵活运用。

如果喜欢这篇文章，别忘了点赞和分享哦！