并查集

并查集分为Quick_Find和Quick_Union两种方式。

定义一个抽象类

abstract public class UnionFind {
    int[] parent;

    protected UnionFind(int capacity) {
        if (capacity < 0) {
            throw new IllegalArgumentException("参数小于0");
        }
        parent = new int[capacity];
        // 初始化时每一个节点都指向自己
        for (int i = 0; i < capacity; i++) {
            parent[i] = i;
        }
    }

// 查询根节点
    abstract public int find(int n);

// 合并两块区域
    abstract public void union(int v1, int v2);

// 判断两个节点是否有相同的根节点
    public boolean isSame(int v1, int v2) {
        return find(v1) == find(v2);
    }
}

两种并查集的实现方式

quick_find

查询复杂度为O(1),合并复杂度为O(n),本质是将节点的都指向父节点，使得生成的树高度为1。

如图：

// 查询方法实现
    public int find(int n) {
        return parent[n];
    }
    
// 合并方法实现
    public void union(int v1, int v2) {
    // 查询两个节点的根节点
        int l = parent[v1];
        int r = parent[v2];

        if (l == r) return;
        
        // 将左边节点的父节点拆开，都放到右边的父节点上
        for (int i = 0; i < parent.length; i++) {
            if (parent[i] == l) {
                parent[i] = r;
            }
        }
    }

quick_union

查询时间复杂度为O(log n),合并时间复杂度也为O(log n),本质是左节点的根节点指向右节点的根节点。

如图：

// 查询方法实现
    public int find(int n) {
    // 一层一层找，直到找到根节点
        while (n != parent[n]) {
            n = parent[n];
        }
        return n;
    }
    
// 合并方法实现
    public void union(int v1, int v2) {
    // 找到两个节点的根节点
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) return;
        // 将左边的根节点的父节点指向右边根节点
        parent[p1] = p2;
    }

上面的实现方式可能会导致树过于高，甚至会成为链表形式，有两种优化方式：

• 将节点少的嫁接到节点多的根节点上

如图:

public class QuickUnion_S1 extends QuickUnion {
// 定义一个size数组，定义节点所属的根节点有多少节点
    private int[] sizes;

    public QuickUnion_S1(int capacity) {
        super(capacity);
        sizes = new int[capacity];
        // 初始化时每一个节点都为1
        for (int i = 0; i < capacity; i++) {
            sizes[i] = 1;
        }
    }

    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) return;
        
        // 判断两个根节点下的有多少子节点
        // 少的根节点嫁接到多的根节点上
        if (sizes[p1] < sizes[p2]) {
            parent[p1] = p2;
            sizes[p2] += sizes[p1];
        }else {
            parent[p2] = p1;
            sizes[p1] += sizes[p2];
        }
    }
}

• 将树低的嫁接到树高的根节点上

public class QuickUnion_S2 extends QuickUnion {

// 定义一个rank数组记录节点的根节点的树高
    private int[] ranks;

    public QuickUnion_S2(int capacity) {
        super(capacity);
        ranks = new int[capacity];
        // 每一个树高都是1
        for (int i = 0; i < capacity; i++) {
            ranks[i] = 1;
        }
    }
    
        @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) return;
        
        //判断两个树的高度
        // 将树低的根节点指向树高的根节点
        if (ranks[p1] < ranks[p2]) {
            parent[p1] = p2;
        } else if (ranks[p2] < ranks[p1]) {
            parent[p2] = p1;
        } else {
        // 如果相同，因为多了根节点多了根节点，可以导致树高多一层
            parent[p1] = p2;
            // 被指向的根节点树高加一
            ranks[p2]++;
        }
    }
}

路径压缩

对quick_union优化后，树高的增长速度会慢一些，但是还是会不断增加其高度，所以可以在查询时降低树的高度，调节树的结构，有三种实现方式：

• 普通路径压缩 --> 所有节点在查询时，都指向其根节点

    @Override
    public int find(int n) {
    // 如果不是根节点
        if (parent[n] != n){
        // 查询其父节点的父节点，并赋予当前父节点
            parent[n] = find(parent[n]);
        }
        return parent[n];
    }

该种方法使得结构变化太大，会导致查询速度慢很多，下面两种结构变化相对慢一些

• 路径分裂 --> 每个节点都指向其祖父节点

    @Override
    public int find(int n) {
        while (n != parent[n]) {
            int p = parent[n];
            parent[n] = parent[parent[n]];
            n = p;
        }
        return n;
    }

• 路径减半 --> 每隔一个节点指向其祖父节点

    @Override
    public int find(int n) {
        while (n != parent[n]){
            parent[n] = parent[parent[n]];
            n = parent[n];
        }
        return n;
    }

# 算法学习