Java數(shù)據(jù)機(jī)構(gòu)中并查集的示例分析

這篇文章主要介紹Java數(shù)據(jù)機(jī)構(gòu)中并查集的示例分析，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

概念

并查集是一種樹(shù)型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合的合并及查詢問(wèn)題（即所謂的并、查）。比如說(shuō)，我們可以用并查集來(lái)判斷一個(gè)森林中有幾棵樹(shù)、某個(gè)節(jié)點(diǎn)是否屬于某棵樹(shù)等。

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

在現(xiàn)實(shí)生活中，也是存在著并查集的一些概念，例如最近《天龍八部》里的人物關(guān)系，可能你并不認(rèn)識(shí)丐幫的一些小人物，但是你一定認(rèn)識(shí)丐幫幫主喬峰。當(dāng)你看見(jiàn)一個(gè)叫花子，你就會(huì)想到他的老大就是幫主喬峰，像這樣的場(chǎng)景，就有了一定的歸屬感， 會(huì)自動(dòng)的認(rèn)為叫花子就是跟丐幫合并在一起的……

說(shuō)簡(jiǎn)單一點(diǎn)，并查集就是將一些數(shù)據(jù)進(jìn)行分類，這樣數(shù)據(jù)為一組，那些數(shù)據(jù)為另一組。如何判斷其中兩個(gè)數(shù)據(jù)，在不在一個(gè)組？我們就會(huì)去找每個(gè)組的代表，看這兩個(gè)數(shù)據(jù)的代表是不是同一個(gè)？如果是，那就是在一個(gè)組；如果不是，那就不在一個(gè)組。所以并查集的大致框架就是下面這樣：

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

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

并查集在判斷兩個(gè)數(shù)據(jù)，是否在一個(gè)組時(shí)，時(shí)間復(fù)雜度能做到O(1)，所以這種數(shù)據(jù)結(jié)構(gòu)還是非常有用的。

實(shí)現(xiàn)

初始化并查集

我們首先從第一個(gè)方法：初始化并查集開(kāi)始。

傳入進(jìn)去的參數(shù)不一定是List，也可以是Collection等等，表示一組數(shù)據(jù)即可！ 首先我們的成員變量只有兩個(gè)，分別是存儲(chǔ)節(jié)點(diǎn)的代表 和 當(dāng)前這個(gè)組的大小。初始化時(shí)，我們分別認(rèn)為 每個(gè)節(jié)點(diǎn)是自己一個(gè)人一組的，也就是說(shuō)，自己一個(gè)組，代表就是自己本身；大小的話，就是自己本身咯，也就是1。

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

判斷是不是同一個(gè)組

isSameSet 比較簡(jiǎn)單，就是判斷兩個(gè)數(shù)據(jù)所在的組的代表，是不是用一個(gè)數(shù)據(jù)即可！如果代表是同一個(gè)人，那就是在一個(gè)組，反之就不是！

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

查找當(dāng)前節(jié)點(diǎn)的代表節(jié)點(diǎn)

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

思路就跟二叉樹(shù)向上查找根結(jié)點(diǎn)的思路一樣，也就是說(shuō)，在fatherMap中一直查找，直到一個(gè)節(jié)點(diǎn)的代表節(jié)點(diǎn)（父節(jié)點(diǎn)）是它自己本身時(shí)，此時(shí)就查找完了；然后最關(guān)鍵的一步，就是路徑壓縮，在我們向上查找的過(guò)程中，我們需要記錄沿途的所有節(jié)點(diǎn)，在查找結(jié)束后，我們將沿途的這些節(jié)點(diǎn)，在fatherMap中的進(jìn)行修改，直接將這些節(jié)點(diǎn)的代表節(jié)點(diǎn)，寫成這個(gè)組的代表節(jié)點(diǎn)，可能聽(tīng)糊涂了，看下圖：

這樣的設(shè)計(jì)，就能使查找的時(shí)間復(fù)雜度控制在O(1)。

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

合并操作

終于來(lái)到了最后的操作：合并。合并也比較簡(jiǎn)單，記住一個(gè)要點(diǎn)：小組掛在大組的下面。也就是說(shuō)，這一個(gè)節(jié)點(diǎn)所在的組要小一點(diǎn)，我們直接將他“掛”在另一個(gè)組的下面。說(shuō)簡(jiǎn)單一點(diǎn)：這一個(gè)組的代表節(jié)點(diǎn)的vaule域，直接指向另一個(gè)組的代表節(jié)點(diǎn)。

//合并操作
public void union(Node node1, Node node2) {
    if (node1 == null || node2 == null) {
        return;
    }
    int node1Size = sizeMap.get(node1);
    int node2Size = sizeMap.get(node2); //分別得到兩個(gè)節(jié)點(diǎn)所在組的大小
    Node node1Father = fatherMap.get(node1);
    Node node2Father = fatherMap.get(node2); //分別拿到兩個(gè)節(jié)點(diǎn)的代表節(jié)點(diǎn)
    
    if (node1Father != node2Father) { //兩個(gè)節(jié)點(diǎn)，不在同一個(gè)組，就合并
        if (node1Size < node2Size) { //node1 掛在 node2
            fatherMap.put(node1Father, node2Father);
            sizeMap.put(node2Father, node1Size + node2Size); //新的組，大小是原來(lái)兩個(gè)組的和
            sizeMap.remove(node1Father); //小組的數(shù)據(jù)，就不需要了，刪除
        } else { //node2 掛在 node1
            //跟上面操作類似
            fatherMap.put(node2Father, node1Father); 
            sizeMap.put(node1Father, node1Size + node2Size);
            sizeMap.remove(node1Father);
        }
    }
}

以上是“Java數(shù)據(jù)機(jī)構(gòu)中并查集的示例分析”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對(duì)大家有幫助，更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！