Java數據機構中關於並查集的詳解

image-20210905162056592

本期文章源碼:GitHub

一文徹底搞懂《並查集》!

概念

並查集是一種樹型的數據結構,用於處理一些不相交集合的合並及查詢問題(即所謂的並、查)。比如說,我們可以用並查集來判斷一個森林中有幾棵樹、某個節點是否屬於某棵樹等。

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

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

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

image-20210905145035613

說簡單一點,並查集就是將一些數據進行分類,這樣數據為一組,那些數據為另一組。如何判斷其中兩個數據,在不在一個組?我們就會去找每個組的代表,看這兩個數據的代表是不是同一個?如果是,那就是在一個組;如果不是,那就不在一個組。所以並查集的大致框架就是下面這樣:

//並查集大致框架---代碼中的數據(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); //第一個參數是這個組的代表,第二個參數是大小
    }
}

image-20210905153047158

判斷是不是同一個組

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中的進行修改,直接將這些節點的代表節點,寫成這個組的代表節點,可能聽糊塗瞭,看下圖:

image-20210905155005868

這樣的設計,就能使查找的時間復雜度控制在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);
        }
    }
}

上面就是並查集的所有操作瞭,是不是很簡單呢?

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

到此這篇關於Java數據機構中關於並查集的詳解的文章就介紹到這瞭,更多相關Java 數據機構 並查集內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: