Java如何实现并查集

# 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;
        }
    }
}

3.2 存在的问题

这种基础实现存在两个主要问题： 1. 查找操作在最坏情况下是O(n)时间复杂度 2. 合并操作可能导致树的不平衡

四、优化实现

4.1 路径压缩优化

路径压缩通过在查找过程中将节点直接连接到根节点，来降低后续查找的时间复杂度。

// 查找操作（带路径压缩）
public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 递归进行路径压缩
    }
    return parent[x];
}

4.2 按秩合并优化

按秩合并通过总是将较小的树合并到较大的树下，保持树的平衡。

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;
            }
        }
    }
}

五、时间复杂度分析

优化后的并查集操作时间复杂度如下：

其中α(n)是反阿克曼函数，增长极其缓慢，可以认为是常数时间。

六、实际应用示例

6.1 朋友圈问题

题目：有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();
}

6.2 岛屿数量问题

题目：给定一个由’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();
}

七、变种与扩展

7.1 带权并查集

可以维护额外的信息，如集合的大小、元素到根节点的距离等。

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];
    }
}

7.2 动态并查集

使用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实现并查集时需要注意：

1. 选择合适的底层数据结构（数组或HashMap）
2. 合理应用优化策略
3. 根据具体问题扩展功能（如维护集合大小、权重等）

掌握并查集对于解决许多算法问题（尤其是图论和连通性问题）非常有帮助，是算法工具箱中的重要工具之一。 “`

亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>