Java并查集算法带你领略热血江湖

什么是并查集

并查集是一种用于管理不相交集合（并查集中，“集合”通常是指一个性质相同的元素的集合）的数据结构。它支持在并集、查集两个操作中的任何一个在接近O(1)的时间复杂度完成，且相对简单易懂。

并查集的应用场景

1. 网络的连通性判断
2. 最小生成树算法
3. 图像处理领域的一些应用

并查集的基本操作

1. 初始化：每个元素都由自己单独构成一个集合，每个集合的父节点设置成自己;
2. 查找：判断某个元素所在的集合，可以通过不断地向上查找父节点，直到其父节点是自身。
3. 合并：将两个集合合并为一个，将其中一个的父节点设置为另一个的根节点。

Java并查集算法示例

示例一：判断一个图是否连通

public class ConnectedComponent {
    private int[] father; // 记录每个点的父节点
    private int count; // 连通块数量

    /**
     * 初始化并查集
     * @param n 节点个数
     */
    public ConnectedComponent(int n) {
        father = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            father[i] = i;
        }
        count = n;
    }

    /**
     * 查询节点所在的连通块
     * @param x 节点编号
     * @return 节点所在的连通块代表
     */
    public int find(int x) {
        if (father[x] == x) {
            return x;
        }
        return father[x] = find(father[x]); // 路径压缩
    }

    /**
     * 合并两个连通块
     * @param x 节点 x
     * @param y 节点 y
     * @return true：合并成功；false：两个点已经在同一个连通块中
     */
    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return false;
        }
        father[rootX] = rootY;
        count--;
        return true;
    }

    /**
     * 获取连通块数量
     * @return 连通块数量
     */
    public int getCount() {
        return count;
    }
}

示例二：计算朋友圈数量

给定一个类似于人际关系的矩阵，其中1表示两个人是朋友，0表示不是，计算朋友圈的数量。

public class FriendCircle {
    private int[] father;
    private int count;

    /**
     * 初始化并查集
     */
    public FriendCircle(int n) {
        father = new int[n];
        for (int i = 0; i < n; i++) {
            father[i] = i;
        }
        count = n;
    }

    /**
     * 查找节点所在连通块的代表
     * @param x 节点编号
     * @return 联通块代表
     */
    private int find(int x) {
        if (father[x] == x) {
            return x;
        }
        return father[x] = find(father[x]);
    }

    /**
     * 合并两个节点所在的连通块
     * @param x 节点x
     * @param y 节点y
     */
    private void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return;
        }
        father[rootX] = rootY;
        count--;
    }

    /**
     * 计算朋友圈数量
     * @param M 人际关系矩阵
     * @return 朋友圈数量
     */
    public int findCircleNum(int[][] M) {
        for (int i = 0; i < M.length; i++) {
            for (int j = i + 1; j < M[0].length; j++) {
                if (M[i][j] == 1) {
                    union(i, j);
                }
            }
        }
        return count;
    }
}