一文徹底搞懂《并查集》！

概念

并查集是一種樹型的資料結構，用于處理一些不相交集合的合并及查詢問題（即所謂的并、查），比如說，我們可以用并查集來判斷一個森林中有幾棵樹、某個節點是否屬于某棵樹等，

具體的用法，我們會以下一篇文章《圖的相關演算法》中，有一個克魯斯卡爾演算法，用于生成最小生成樹，會用到并查集，

并查集的主要作用是求連通分支數（如果一個圖中所有點都存在可達關系（直接或間接相連），則此圖的連通分支數為1；如果此圖有兩大子圖各自全部可達，則此圖的連通分支數為2……）

在現實生活中，也是存在著并查集的一些概念，例如最近《天龍八部》里的人物關系，可能你并不認識丐幫的一些小人物，但是你一定認識丐幫幫主喬峰，當你看見一個叫花子，你就會想到他的老大就是幫主喬峰，像這樣的場景，就有了一定的歸屬感， 會自動的認為叫花子就是跟丐幫合并在一起的……

說簡單一點，并查集就是將一些資料進行分類，這樣資料為一組，那些資料為另一組，如何判斷其中兩個資料，在不在一個組？我們就會去找每個組的代表，看這兩個資料的代表是不是同一個？如果是，那就是在一個組；如果不是，那就不在一個組，所以并查集的大致框架就是下面這樣：

//并查集大致框架---代碼中的資料（Node），可以是其他，比如二叉樹節點、圖的邊、節點等等 抽象的資料
public class UnionSet {
    private HashMap<Node, Node> fatherMap; //key表示當前這個資料，value表示這個資料的代表（父親）是誰
    private HashMap<Node, Integer> sizeMap; //表示當前這個組（集合）的大小
    
    public UnionSet() { //構造方法
        fatherMap = new HashMap<>();
        sizeMap = new HashMap<>();
    }
    
    public void makeSet(List<Node> list) { //生成初始化狀態的并查集，剛開始每個資料都是獨立的
        
    }
    
    public boolean isSameSet(Node node1, Node node2) { //判斷當前這兩個資料，是不是一個組的？
        
    }
    
    private Node findFather(Node node) { //查找這個資料，它那個組的代表（父親）是誰？
        
    }
    
    public void union(Node node1, Node node2) { //將這兩個資料，放到一個組
         
    }
}

上面就是大致的框架，就是幾個方法：初始化并查集、判斷是不是一個組、查找代表、合并到一個組，四個方法，就是并查集，簡不簡單？

并查集在判斷兩個資料，是否在一個組時，時間復雜度能做到O(1)，所以這種資料結構還是非常有用的，

實作

初始化并查集

我們首先從第一個方法：初始化并查集開始，

傳入進去的引數不一定是List，也可以是Collection等等，表示一組資料即可！ 首先我們的成員變數只有兩個，分別是存盤節點的代表 和 當前這個組的大小，初始化時，我們分別認為 每個節點是自己一個人一組的，也就是說，自己一個組，代表就是自己本身；大小的話，就是自己本身咯，也就是1，

//初始化并查集
public void makeSet(List<Node> list) {
    if (list == null) {
        return;
    }
    fatherMap.clear();
    sizeMap.clear(); //先將表清空
    
    //遍歷list，把每一個節點，都放入哈希表中
    for (Node node : list) {
        fatherMap.put(node, node); //第一個引數是節點本身，第二個引數就是這個組的代表
        sizeMap.put(node, 1); //第一個引數是這個組的代表，第二個引數是大小
    }
}

判斷是不是同一個組

isSameSet 比較簡單，就是判斷兩個資料所在的組的代表，是不是用一個資料即可！如果代表是同一個人，那就是在一個組，反之就不是！

//判斷是不是同一個組
public boolean isSameSet(Node node1, Node node2) {
    if (node1 == null || node2 == null) {
        return false;
    }
    return findFather(node1) == findFather(node2); //查找各自的代表節點，看是不是同一個，
}

查找當前節點的代表節點

findFather，我自己覺得算是并查集的核心，也這是這個方法，是并查集的查找的時間復雜度能在O(1)的主要因素，

思路就跟二叉樹向上查找根結點的思路一樣，也就是說，在fatherMap中一直查找，直到一個節點的代表節點（父節點）是它自己本身時，此時就查找完了；然后最關鍵的一步，就是路徑壓縮，在我們向上查找的程序中，我們需要記錄沿途的所有節點，在查找結束后，我們將沿途的這些節點，在fatherMap中的進行修改，直接將這些節點的代表節點，寫成這個組的代表節點，可能聽糊涂了，看下圖：

這樣的設計，就能使查找的時間復雜度控制在O(1)，

//查找代表節點，并做路徑壓縮
private Node findFather(Node node) {
    if (node == null) {
        return null;
    }
    //查找代表節點
    Stack<Node> path = new Stack<>(); //存盤沿途的節點
    while (node != fatherMap.get(node)) { //代表節點不是自己本身，就繼續查找
        path.push(node);
        node = fatherMap.get(node);
    }
    //路徑壓縮
    while (!path.isEmpty()) {
        Node tmp = path.pop();
        fatherMap.put(tmp, node); //此時的node，就是這個組的代表節點
    }
    
    return node;
}

合并操作

終于來到了最后的操作：合并，合并也比較簡單，記住一個要點：小組掛在大組的下面，也就是說，這一個節點所在的組要小一點，我們直接將他“掛”在另一個組的下面，說簡單一點：這一個組的代表節點的vaule域，直接指向另一個組的代表節點，

//合并操作
public void union(Node node1, Node node2) {
    if (node1 == null || node2 == null) {
        return;
    }
    int node1Size = sizeMap.get(node1);
    int node2Size = sizeMap.get(node2); //分別得到兩個節點所在組的大小
    Node node1Father = fatherMap.get(node1);
    Node node2Father = fatherMap.get(node2); //分別拿到兩個節點的代表節點
    
    if (node1Father != node2Father) { //兩個節點，不在同一個組，就合并
        if (node1Size < node2Size) { //node1 掛在 node2
            fatherMap.put(node1Father, node2Father);
            sizeMap.put(node2Father, node1Size + node2Size); //新的組，大小是原來兩個組的和
            sizeMap.remove(node1Father); //小組的資料，就不需要了，洗掉
        } else { //node2 掛在 node1
            //跟上面操作類似
            fatherMap.put(node2Father, node1Father); 
            sizeMap.put(node1Father, node1Size + node2Size);
            sizeMap.remove(node1Father);
        }
    }
}

上面就是并查集的所有操作了，是不是很簡單呢？

好啦，本期更新到此就結束啦，同學們，下期見！！！