前言

并查集是一種非常有用且高效的數(shù)據(jù)結(jié)構(gòu)，千萬不要被這個(gè)極具專業(yè)性的名字嚇到了，它的算法思想和代碼實(shí)現(xiàn)都非常簡(jiǎn)單，不需要花太大力氣就可以輕松掌握。下面就通過畫圖等方式為大家介紹一下這種神奇的數(shù)據(jù)結(jié)構(gòu)。

一、 圖解并查集

并查集有兩個(gè)英文名：1、Disjoint Set，2、Union Find。它的作用就是把一個(gè)數(shù)據(jù)集分成若干個(gè)子集，每個(gè)子集內(nèi)部數(shù)據(jù)可以互聯(lián)互通，而子集之間則不具有連通性。并查集的底層結(jié)構(gòu)類似于堆(不熟悉堆的同學(xué)趕緊去復(fù)習(xí)一下堆排序，面試頻率很高哦)，也是用數(shù)組描述一種樹結(jié)構(gòu)，但不同的是，堆是一棵獨(dú)立的二叉樹，并查集的樹是多叉樹，而且可能不止一棵樹(也就是森林)。在并查集中，我們把相互獨(dú)立的數(shù)據(jù)集稱為連通分量，連通分量在邏輯上可以形象地描述為一棵樹，每棵樹都有一個(gè)根節(jié)點(diǎn)，其他的元素都會(huì)直接或間接指向根節(jié)點(diǎn)。

比如下圖這個(gè)并查集，我們維護(hù)一個(gè)parent數(shù)組，每個(gè)元素初始化為對(duì)應(yīng)的數(shù)組下標(biāo)，代表自己是獨(dú)立的一棵樹，且是樹根。以第一棵樹為例，在后續(xù)數(shù)據(jù)處理過程中，我們把與所有與"2"同屬一個(gè)連通分量的元素都連到"2"上，并把數(shù)組對(duì)應(yīng)下標(biāo)的元素賦值為2，其中"5"先連接到了"1"上，"1"又連接到了"2"上。最后，數(shù)組每個(gè)元素都代表其指向的父節(jié)點(diǎn)。

并查集底層結(jié)構(gòu)

知道了并查集的底層結(jié)構(gòu)，那我們?cè)撊绾稳?gòu)建這個(gè)結(jié)構(gòu)并進(jìn)行查找操作呢？并查集有兩個(gè)最重要的方法：union 和 find，這里先給出UnionFind 最完善的 API 框架偽代碼：

public class UnionFind {
  public UnionFind(int N) {}                       // 構(gòu)造方法
  
  public int find(int x) {}                        //查找某個(gè)元素的根節(jié)點(diǎn)
  public void union(int x, int y) {}               // 為x和y建立聯(lián)系
  public boolean connected(int x, int y) {}        //判斷x和y是否相連(在同一棵樹也就是連通分量中)
  public int count() {}                            // 返回連通分量的個(gè)數(shù)，也就是多少棵樹
}

1. find 方法實(shí)現(xiàn)

find方法的目的是尋找某個(gè)元素所在樹的根節(jié)點(diǎn)，代碼如下：

public int find(int x) {
  while (x != parent[x]) {
    x = parent[x];
  }
  return x;
}

解釋一下這短短幾行代碼做了什么，前面的介紹我們已經(jīng)知道，根節(jié)點(diǎn)元素的數(shù)組值就是自身的下標(biāo)，也就是parent[x] = x; 那么當(dāng)數(shù)組元素值不等于其下標(biāo)時(shí)，說明它不是根節(jié)點(diǎn)，就一直循環(huán)找下去，直到找到根節(jié)點(diǎn)。 如下圖是尋找5的根節(jié)點(diǎn)的過程：

find 操作

2. union 方法實(shí)現(xiàn)

union 方法顧名思義就是把兩個(gè)元素聯(lián)系起來，具體的做法先找到各自的根節(jié)點(diǎn)，再把其中一個(gè)元素的根節(jié)點(diǎn)連接到另一個(gè)元素的根節(jié)點(diǎn)上，代碼如下：

public void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    // 根節(jié)點(diǎn)相同則無需操作
    if (rootX == rootY) {
        return;
    }
    parent[rootX] = rootY;
}

下圖是對(duì)元素 4 和 5 進(jìn)行 union 的操作示意圖：

union 操作

union 操作

3. 并查集優(yōu)化：路徑壓縮和按秩合并

從上圖中我們可以看出一個(gè)問題，如果 union 操作直接將兩棵樹合并，那么多次 union 之后，樹的高度可能會(huì)很高，那么尋找一個(gè)節(jié)點(diǎn)的根節(jié)點(diǎn)的路徑就會(huì)很長(zhǎng)，導(dǎo)致查找效率降低，那該如何對(duì)其進(jìn)行優(yōu)化呢？主要有兩種優(yōu)化方式，那就是路徑壓縮和按秩合并，路徑壓縮是在 find 方法里進(jìn)行，而按秩合并則是在 union 方法中進(jìn)行，二者選其一即可，前者代碼更簡(jiǎn)潔。

3.1 路徑壓縮

路徑壓縮又有兩種方式：隔代壓縮和徹底壓縮

• 「隔代壓縮」性能比較高，雖然壓縮不完全，不過多次執(zhí)行「隔代壓縮」也能達(dá)到比較好的效果，只需要在原 find 方法中加上一句parent[x] = parent[parent[x]];這句代碼的意思是把路徑上的每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)指向其祖父節(jié)點(diǎn)。
• 「徹底壓縮」需要借助系統(tǒng)棧，使用遞歸的寫法 ?；蛘呤褂玫鷮懛?，先找到當(dāng)前結(jié)點(diǎn)的根結(jié)點(diǎn)，然后把沿途上所有的節(jié)點(diǎn)都指向根節(jié)點(diǎn)，需要遍歷兩次。徹底壓縮需要消耗更多的性能，但是壓縮的更徹底，可以提高查詢效率。

隔代壓縮與徹底壓縮

3.2 按秩合并

這個(gè)“秩”一般是指樹的高度，也有地方解釋為樹節(jié)點(diǎn)個(gè)數(shù)，我們這里取前者。具體實(shí)現(xiàn)就是新增一個(gè)ranks數(shù)組記錄以各個(gè)元素為根節(jié)點(diǎn)的樹的高度，在做合并操作時(shí)，把高度較小的樹的根節(jié)點(diǎn)連接到高度較大的樹的根節(jié)點(diǎn)上。如下圖，在未優(yōu)化前，合并后的樹高度增加為4，而按秩合并后的樹高仍然為3。這里要注意的是，如果兩棵樹高度相同，那么兩者均可作為根節(jié)點(diǎn)，則合并后的新樹高度需要加一。

按秩合并

代碼如下：

// 如果代碼片段看不懂，可以結(jié)合后面的完整版代碼去理解
public void union(int x, int y) {
      int rootX = find(x);
      int rootY = find(y);
      // 根節(jié)點(diǎn)相同則不需要操作
      if (rootX == rootY) {
            return;
      }
      // 比較樹高，高度小的樹合并到另一顆樹上，相等的話兩者均可作為根節(jié)點(diǎn)，并把高度加一
      if (ranks[rootX] > ranks[rootY]) {
            parent[rootY] = rootX;
      } else if (ranks[rootX] < ranks[rootY]) {
            parent[rootX] = rootY;
      } else {
          parent[rootY] = rootX;
          ranks[rootX]++;
      }
      count--;
}

4. 完整代碼

4.1 路徑壓縮版本

class UnionFind {
    private int[] parent;
    // count用來記錄連通分量的個(gè)數(shù)
    private int count;

    public UnionFind(int n) {
        // count初始化為n，也就是最開始有n個(gè)連通分量(n棵樹)
          count = n;
        // parent數(shù)組各個(gè)元素初始化為其自身下標(biāo)，代表自己是一棵樹
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
  
        /**查找根節(jié)點(diǎn)*/
    public int find(int x) {
        while (x != parent[x]) {
            // 路徑壓縮(隔代壓縮)
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
  
        /**合并操作*/
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        // 根節(jié)點(diǎn)相同則不需要操作
        if (rootX == rootY) {
            return;
        }
        parent[rootX] = rootY;
        // 合并之后連通分量(樹)個(gè)數(shù)減一
        count--;
    }
  
        /**判斷x和y是否在同一個(gè)連通分量(同一棵樹)*/
    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }
  
    /**返回連通分量個(gè)數(shù)*/
    public int count() {
        return count;
    }
}

4.2 按秩合并版本

class UnionFind {
    private int[] parent;
    //新加一個(gè)ranks數(shù)組，記錄樹的高度
    private int[] ranks;
    // count記錄連通分量的個(gè)數(shù)
    private int count;

    public UnionFind(int n) {
        count = n;
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        // 高度都初始化為1
        ranks = new int[n];
        for (int i = 0; i < n; i++) {
            ranks[i] = 1;
        }
    }
        /**按秩合并版本的 find 方法不需要做優(yōu)化*/
    public int find(int x) {
        while (x != parent[x]) {
            x = parent[x];
        }
        return x;
    }
        /**按秩合并*/
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return;
        }
        if (ranks[rootX] > ranks[rootY]) {
            parent[rootY] = rootX;
        } else if (ranks[rootX] < ranks[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            ranks[rootX]++;
        }
        count--;
    }

    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }

    public int count() {
        return count;
    }
}

二、并查集的應(yīng)用

了解完并查集，最好可以在實(shí)際場(chǎng)景中實(shí)踐一下，如果沒有合適的生產(chǎn)環(huán)境的話，那就來趁熱打鐵做幾道Leetcode算法題來檢驗(yàn)一下學(xué)習(xí)成果吧。這里舉三個(gè)比較典型且比較簡(jiǎn)單的題目，每個(gè)題目都代表了一個(gè)并查集的應(yīng)用場(chǎng)景。

1、Leetcode原題1319 聯(lián)通網(wǎng)絡(luò)的操作次數(shù)

比如一個(gè)在一整個(gè)計(jì)算機(jī)網(wǎng)絡(luò)中，有的計(jì)算機(jī)可以和其他一部分計(jì)算機(jī)通過線纜連接了起來，但是整個(gè)集群并不是互聯(lián)互通的，那么我們就需要計(jì)算操作多少次可以把整個(gè)集群連接起來。

如果確定了一道題需要用并查集來求解，那我們上來二話就說先把 UnionFind 類寫出來，然后再去處理題目邏輯，這樣會(huì)簡(jiǎn)單很多。

class Solution {
    public int makeConnected(int n, int[][] connections) {
        UnionFind uf = new UnionFind(n);
        // 數(shù)組長(zhǎng)度就是現(xiàn)有線纜數(shù)量
        int cables = connections.length;
        // 如果線纜數(shù)量小于計(jì)算機(jī)數(shù)量減一，那么肯定不可能把所有計(jì)算機(jī)都連接起來
        if (cables < n - 1) return -1;
        // 遍歷數(shù)組，union 所有計(jì)算機(jī)
        for (int[] con : connections) {
            uf.union(con[0], con[1]);
        }
        //need是連通塊的數(shù)量，也就是計(jì)算機(jī)集群的數(shù)量，把他們連起來所需線纜數(shù)量等于need-1
        int need = uf.count();
        return need - 1;
    } 
}
class UnionFind {...}    // 這里是 UnionFind 的完整代碼，選擇以上任一版本均可

2、 Leetcode原題547 朋友圈

典型的就是朋友圈，如果一個(gè)朋友圈里的人和圈外的人沒有任何關(guān)系，那么如何去統(tǒng)計(jì)一群人中的朋友圈數(shù)量；

class Solution {
    public int findCircleNum(int[][] M) {
        int n = M.length;
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (M[i][j] == 1) {
                    uf.union(i, j);
                }
            }
        }
        // 直接返回連通分量個(gè)數(shù)即為朋友圈個(gè)數(shù)
        return uf.count();
    }
}
class UnionFind {...}      // 這里是 UnionFind 的完整代碼，選擇之前任一版本均可

3、Leetcode原題990 等式方程的可滿足性

在編程中，有時(shí)候我們需要聲明一些等價(jià)的變量名(也就是多個(gè)引用指向一個(gè)對(duì)象)，在一系列聲明之后，系統(tǒng)需要判斷這些變量名是否等價(jià)。在下面這道題中，可以把方程等號(hào)兩端的變量看做變量名。

class Solution {
    public boolean equationsPossible(String[] equations) {
        UnionFind uf = new UnionFind(26);
        // 先遍歷一遍將"=="連接的變量進(jìn)行 union 操作
        for (String s : equations) {
            char[] cs = s.toCharArray();
            if (cs[1] == '=') {
                uf.union(cs[0] - 'a', cs[3] - 'a');
            }
        }
        // 再遍歷一遍，如果"!="連接的變量在同一連通分量，則出現(xiàn)矛盾，直接返回false
        for (String s : equations) {
            char[] cs = s.toCharArray();
            if (cs[1] == '!' && uf.isConnected(cs[0] - 'a', cs[3] - 'a')) {
                return false;
            }
        }
        return true;
    }
}
class UnionFind {...}      // 這里是 UnionFind 的完整代碼，選擇之前任一版本均可

可以看出，在提供了完善的 UnionFind API 后，題目的處理變得異常簡(jiǎn)單。 UnionFind 的使用是有固定套路的，那就是先把整個(gè)數(shù)據(jù)集的數(shù)據(jù) union 一遍，然后再根據(jù)實(shí)際需求去判斷兩個(gè)數(shù)據(jù)是否連通或統(tǒng)計(jì)連通分量的個(gè)數(shù)。小伙伴們?nèi)绻雵L試更多并查集相關(guān)算法題，可以在 Leetcode 查看并查集的標(biāo)簽分類。