并查集

• 并查集(Java) -- 关系网
• • 并查集 -- 实现

并查集(Java) – 关系网

  其实际意义就是可快速找到两个元素是否同属一个集合，可将两点是否连通的图论问题简化为其根是否一致；主要涉及到的方法是find和union，用数组进行实现可以元素与父节点的对应关系，元素可为数组中的index，父节点则为数组中的值；~~
  并查集的优化的两种方式以高为秩和以元素个数为秩，也就是要么越高的当集合合并后的新老大，要么越多的当集合合并后的新老大；实际感觉两种优化差不多，按顺眼度来吧～～

并查集 – 实现

// 并查集
public class UnionFind {
    private int boss[]; // index为元素，值为根；若为根则为负值，负值越小则秩越大
    private int size;  // 容量

    // 构造函数，传入需要设定容量
    public UnionFind(int size) {
        this.size = size;
        boss = new int[size];

        for(int i=0; i<size; i++) {
            boss[i] = -1;
        }
    }

    // 查；顺便进行路径压缩
    public int find(int target) {
        assert(target>=0 && target<size);

        // 路径压缩，每循环一次使boss[target]的子树整体上移
        while(boss[target] >= 0 && boss[boss[target]] >= 0) {
            boss[target] = boss[boss[target]];
            target = boss[target];
        }
        // 如果父节点大于0，说明根在祖父节点
        if(boss[target] >= 0) return boss[boss[target]];

        // 根在父节点
        return boss[target];
    }

    // 合并；按秩归并，以元素个数为秩，负值越小，秩越大
    // 注意：这里合并要遵循一个原则才能使并查集具有实际意义，当传入a和b时，a和b之间必须存在连接，否则并查集的意义无存
    public void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);

        // 按元素个数判断谁当两个集合的老大
        if(boss[a] <= boss[b]) {
            boss[a] += boss[b];
            boss[b] = rootA;
        } else if(boss[a] > boss[b]) {
            boss[b] += boss[a];
            boss[a] = rootB;
        }
    }

    public boolean isConnected(int a, int b) {

        return find(a) == find(b);
    }
}