并查集

-数据结构与算法 PV:

​ 在我们需要判断某一些事物之间是否存在一定的关系的时候，我们最好的办法不是使用图而是使用并查集。因为我们关心的是他们之间是否有关系，而不是关心的他们到底存在怎样的关系。

​ 并查集，简单来说就是 n 个集合，我们通过 union 操作来建立两个节点之间的关系。通过 connected 来判断两个节点之间的关系。那么现在我们知道了 并查集的基本操作就是 union 和 connected 。

逻辑结构：

并查集一开始我们初始化都是初始化 n 个不相关的独立集合。然后我们在做 union 操作的时候也就是让两个集合进行合并，所谓的合并操作就是让 connected 操作在应用于这两个元素的时候能返回同一个集合我们就逻辑上认为他们处于同一个集合内。

物理结构:

现在我们大致对逻辑结构有了了解，就是集合的合并，以及判断两个元素是否在同一个集合。对于这种问题我们可以使用一个数组来对元素进行存储。这里我们维护一个 id 数组，一开始我们数组存放的就都是自己的下标，这个时候我们认为他们相互独立，当我们需要进行合并操作的时候我们只需要把一个集合的元素 id 值改成另外一个集合的元素的下标即可。这时也许你已经想到了那么 connected 操作就是判断这个 id 内容是否相等就可以了。这里确实也如此！

代码实现的第一个版本：

​ 此时大概了解他们的物理结构和逻辑结构以后我们就可以开始写代码了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class QuickFindUF {
    private int[] id;

    QuickFindUF(int N) {
        id = new int[N];
        for (int i = 0; i < id.length; i++) {
            id[i] = i;
        }
    }

    public boolean connected(int p, int q) {
        return id[p] == id[q];
    }

    public void union(int p, int q) {
        int pid = id[p];
        int qid = id[q];
        if (pid == qid) {
            return;
        }
        for (int i = 0; i < id.length; i++) {
            if (id[i] == pid) {
                id[i] = qid;
            }
        }
    }
}

​ 可以看到以上的代码我们就是维护了一个 id 数组，然后我们根据这个 id 数组进行判断是否联通，以及使用它进行合并操作，也许你已经发现了这个代码的 connected 操作的时间复杂度是常数，但是 union 操作的代价却是 n平方（为什么是 n 平方而不是 n，因为每一次合并的代价是 n 而一般我们最坏情况需要进行 n 次的合并所以就是 n 平方数量级），所以说当我们在处理很大数据量的时候这个复杂大是完全不可以接受的，一般10亿数据在 n 平方的复杂度下面需要的时间大概是 30 年，而 n 复杂度可能就是几秒钟的事情，所以我们说 n 平方是不可接受的慢。

代码实现的第二个版本：

​ 好了上面我们已经分析了第一个版本的代码对于 union 操作的代价太高，所以我们不得不想办法对其进行优化，否则这个算法面对大量的数据是无法使用的。上面的第一个版本我们可以称之为 快速查找 因为他只用了常数的时间完成了操作。

​ 接下来需要看一个快速合并的例子，来改进上述的代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class QuickUnionUF {
    private int[] id;

    QuickUnionUF(int N) {
        id = new int[N];
        for (int i = 0; i < id.length; i++) {
            id[i] = i;
        }
    }

    private int root(int x) {
        while (x != id[x]) {
            x = id[x];
        }
        return x;
    }

    public boolean connected(int p, int q) {
        return root(p) == root(q);
    }

    public void union(int p, int q) {
        if (connected(p, q)) {
            return;
        }
        id[p] = q;
    }
}

​ 这里我们改进的思想就是让这个集合成为一棵树，然后我们在合并的时候只需要调整一次根节点就好了，这样复杂度瞬间就降低了，但是有一个问题就是查找的复杂度变高了，因为此时我们存放的不是一个同一个根节点，而是有可能是一些中间节点，我们为了能够查找我们必须去寻找这个节点的根节点。如下图。无偶一我们需要一个 root 方法帮我们找到他们的根节点。

​ 现在合并只需要线性的时间，但是我们查找则需要 n 最坏的情况就是我们要找的节点刚好就一个子树的最下面的节点，而且这个树根只有一个子节点。也就是极左或者极右的那种。

代码实现的第三个版本：

​ 现在看起来这个数据结构已经比较完美了，合并和查找的时间都比较短，但是仔细想想在上面进行合并的时候我们并没有规定怎么合并，我们只是说了合并就是把一个树的根作为另外一棵树的子树。也许你已经想到了，有时候我们把一颗大的树作为小的树子树会导致树高度变高。这样显然是不明智的，比较好的做法就是把小树作为大树的子树。这里我们采用了权重，我们所说的权重就是树的大小 注意是树的**大小而不是树的高度**，这样我们就只需要再维护一个权重的数组就可以了，每次在合并的时候只需要进行一下判断就能避免树高度大幅度增加，导致不必要的查找开销。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class QuickUnionWeightImprove {
    private int[] id;
    private int[] size;

    QuickUnionWeightImprove(int N) {
        id = new int[N];
        size = new int[N];
        for (int i = 0; i < id.length; i++) {
            id[i] = i;
            size[i] = 1;
        }
    }

    private int root(int x) {
        while (x != id[x]) {
            x = id[x];
        }
        return x;
    }

    public boolean connected(int p, int q) {
        return root(p) == root(q);
    }

    public void union(int p, int q) {
        int rootP = root(p);
        int rootQ = root(q);
        if (connected(p, q)) {
            return;
        }
        if (size[p] > size[q]) {
            id[rootQ] = rootP;
            size[p] += size[q];
        } else {
            id[rootP] = rootQ;
            size[q] += size[p];
        }
    }
}

​ 好了这里需要注意的是：在进行了树的合并以后不要忘记修改根节点的树的大小（权重）

代码实现的第四个版本：

​ 上面的代码其实还可以再进行优化，这里提出的优化方案就是路径压缩。简单来说我们进行查找的时候我们可以把这个节点挂到祖父节点下面这样树的高度明显变低，查找起来很方便。然而这一切我们只需要一行代码就能搞定，并且不影响查找的正确性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class QuickUnionWeightCompressImprove {
    private int[] id;
    private int[] size;

    QuickUnionWeightCompressImprove(int N) {
        id = new int[N];
        size = new int[N];
        for (int i = 0; i < id.length; i++) {
            id[i] = i;
            size[i] = 1;
        }
    }

    private int root(int x){
        while (x!=id[x]){
            //路径压缩只需要一行,这一行就是把节点向上移动一层
            id[x]=id[id[x]];
            x=id[x];
        }
        return x;
    }

    public boolean connected(int p,int q){
        return root(p) == root(q);
    }

    public void union(int p, int q) {
        int root_p = root(p);
        int root_q = root(q);
        if (root_p == root_q) {
            return;
        }
        if (size[root_p] > size[root_q]) {
            id[root_q] = root_p;
        }else {
            id[root_p] = root_q;
        }
    }
}

​ 好了现在代码看起来会比较完美了，该用的技巧我们都已经用上了，现在合并操作的时间复杂度是常数，而查找操作的复杂度则是 n+nlogn

应用：

​ 接下来一个并查集的小应用的例子，就是迷宫是否有解，我们就可以使用并查集来找最上面，和最下面一行之间是不是有联通的节点，如果有的话我们就能找到迷宫的解。

​ 但是这样一来复杂度又上去了，因为我们最上面一层的 n 个节点和最下面一层 n 个节点都要进行 connected 操作，这样我们时间复杂度毫无疑问的成为了 n 平方 又是那个不可接受的慢，这里有一个技巧就是我们为最上面一行，最下面一行的 n 个节点分别建立一个父节点，这样一来我们只需要进行一次 connected 操作即可。

Powered by Hexo and Hexo-theme-hiker

Copyright © 2015 - 2021 昨夜凛雨 All Rights Reserved.

UV : | PV :