java代码如何实现并查集及路径压缩 java代码并查集数据结构的实用编写教程-java教程-PHP中文网

java代码如何实现并查集及路径压缩 java代码并查集数据结构的实用编写教程

看不見的法師

发布： 2025-08-11 17:13:02

原创

756人浏览过

使用路径压缩是为了降低树的高度，使find操作的均摊时间复杂度接近o(α(n))，从而显著提升查询效率；1. 路径压缩在每次find时将路径上所有节点直接连到根节点，减少后续查找时间；2. 基于rank的合并策略通过将低rank树合并到高rank树上，防止树过深；3. 当rank相同时合并后需将新根的rank加1；4. 并查集适用于图的连通性判断、kruskal算法、网络连接、图像处理和社交网络等场景。

java代码如何实现并查集及路径压缩 java代码并查集数据结构的实用编写教程

并查集是一种用于处理集合合并和查询问题的高效数据结构。它能快速判断两个元素是否属于同一集合，以及将两个集合合并成一个。Java实现并查集，重点在于

find

登录后复制

（查找根节点）和

union

登录后复制

（合并集合）这两个核心操作，而路径压缩则是一种优化手段，能显著提升查找效率。

public class UnionFind {
    private int[] parent;
    private int[] rank; // 用于优化合并，记录树的高度

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i; // 初始时，每个元素都是一个独立的集合，父节点指向自己
            rank[i] = 0; // 初始时，每个树的高度为0
        }
    }

    // 查找根节点，同时进行路径压缩
    public int find(int x) {
        if (parent[x] != x) {
            // 递归查找父节点，直到找到根节点
            parent[x] = find(parent[x]); // 路径压缩：将x的父节点直接指向根节点
        }
        return parent[x];
    }

    // 合并两个集合，基于rank的优化
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            // 将rank低的树合并到rank高的树上
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                // 如果rank相同，则随便合并，并增加rank
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

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

    public static void main(String[] args) {
        UnionFind uf = new UnionFind(10);
        uf.union(1, 2);
        uf.union(2, 3);
        uf.union(4, 5);
        uf.union(6, 7);
        uf.union(5, 6);
        uf.union(3, 7);

        System.out.println("1 and 5 are connected: " + uf.isConnected(1, 5)); // true
        System.out.println("4 and 8 are connected: " + uf.isConnected(4, 8)); // false
    }
}

登录后复制