# Java如何实现并查集 ## 一、什么是并查集 并查集（Disjoint-Set Union，简称DSU）是一种树型的数据结构，用于处理一些不交集合（Disjoint Sets）的合并及查询问题。它主要支持两种操作： 1. **查找（Find）**：确定某个元素属于哪个子集 2. **合并（Union）**：将两个子集合并成一个集合 并查集在解决连通性问题、图论算法（如Kruskal最小生成树算法）等方面有广泛应用。 ## 二、并查集的核心思想 并查集通过维护一个父指针数组（或字典）来表示元素的归属关系： - 每个元素最初都是自己的父节点 - 通过路径压缩优化查找操作 - 通过按秩合并优化合并操作 ## 三、基础实现 ### 3.1 基本数据结构 ```java class UnionFind { private int[] parent; // 初始化并查集 public UnionFind(int size) { parent = new int[size]; for (int i = 0; i < size; i++) { parent[i] = i; // 每个元素初始父节点是自己 } } // 查找操作（未优化） public int find(int x) { while (parent[x] != x) { x = parent[x]; } return x; } // 合并操作（未优化） public void union(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX != rootY) { parent[rootY] = rootX; } } } 这种基础实现存在两个主要问题： 1. 查找操作在最坏情况下是O(n)时间复杂度 2. 合并操作可能导致树的不平衡
路径压缩通过在查找过程中将节点直接连接到根节点，来降低后续查找的时间复杂度。
// 查找操作（带路径压缩） public int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); // 递归进行路径压缩 } return parent[x]; } 按秩合并通过总是将较小的树合并到较大的树下，保持树的平衡。
class OptimizedUnionFind { private int[] parent; private int[] rank; // 秩（树的高度） public OptimizedUnionFind(int size) { parent = new int[size]; rank = new int[size]; for (int i = 0; i < size; i++) { parent[i] = i; rank[i] = 1; // 初始高度为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; } } } } 优化后的并查集操作时间复杂度如下：
| 操作 | 时间复杂度 |
|---|---|
| 初始化 | O(n) |
| 查找（Find） | O(α(n))（近似常数） |
| 合并（Union） | O(α(n))（近似常数） |
其中α(n)是反阿克曼函数，增长极其缓慢，可以认为是常数时间。
题目：有n个人，给出m对朋友关系，朋友的朋友也是朋友，求有多少个朋友圈。
public int findCircleNum(int[][] M) { int n = M.length; UnionFind uf = new UnionFind(n); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (M[i][j] == 1) { uf.union(i, j); } } } Set<Integer> circles = new HashSet<>(); for (int i = 0; i < n; i++) { circles.add(uf.find(i)); } return circles.size(); } 题目：给定一个由’1’（陆地）和’0’（水）组成的二维网格，计算岛屿的数量。
public int numIslands(char[][] grid) { if (grid == null || grid.length == 0) return 0; int rows = grid.length; int cols = grid[0].length; UnionFind uf = new UnionFind(rows * cols); int count = 0; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (grid[i][j] == '1') { count++; // 检查四个方向 if (i > 0 && grid[i-1][j] == '1') { uf.union(i * cols + j, (i-1) * cols + j); } if (j > 0 && grid[i][j-1] == '1') { uf.union(i * cols + j, i * cols + (j-1)); } } } } Set<Integer> roots = new HashSet<>(); for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (grid[i][j] == '1') { roots.add(uf.find(i * cols + j)); } } } return roots.size(); } 可以维护额外的信息，如集合的大小、元素到根节点的距离等。
class WeightedUnionFind { private int[] parent; private int[] weight; // 到父节点的权重 public WeightedUnionFind(int size) { parent = new int[size]; weight = new int[size]; for (int i = 0; i < size; i++) { parent[i] = i; weight[i] = 0; } } public int find(int x) { if (parent[x] != x) { int origin = parent[x]; parent[x] = find(parent[x]); weight[x] += weight[origin]; } return parent[x]; } public void union(int x, int y, int value) { int rootX = find(x); int rootY = find(y); if (rootX != rootY) { parent[rootX] = rootY; weight[rootX] = weight[y] - weight[x] + value; } } public int getWeight(int x, int y) { if (find(x) != find(y)) { return -1; // 不在同一集合 } return weight[x] - weight[y]; } } 使用HashMap实现动态扩容的并查集：
class DynamicUnionFind { private Map<Integer, Integer> parent; private Map<Integer, Integer> rank; public DynamicUnionFind() { parent = new HashMap<>(); rank = new HashMap<>(); } public void add(int x) { if (!parent.containsKey(x)) { parent.put(x, x); rank.put(x, 1); } } public int find(int x) { if (!parent.containsKey(x)) { throw new IllegalArgumentException("Element not found"); } if (parent.get(x) != x) { parent.put(x, find(parent.get(x))); } return parent.get(x); } public void union(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX != rootY) { if (rank.get(rootX) > rank.get(rootY)) { parent.put(rootY, rootX); } else if (rank.get(rootX) < rank.get(rootY)) { parent.put(rootX, rootY); } else { parent.put(rootY, rootX); rank.put(rootX, rank.get(rootX) + 1); } } } } 并查集是一种高效处理不相交集合合并与查询的数据结构，通过路径压缩和按秩合并优化后，可以达到近乎常数时间复杂度。Java实现并查集时需要注意：
掌握并查集对于解决许多算法问题（尤其是图论和连通性问题）非常有帮助，是算法工具箱中的重要工具之一。 “`
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
