欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java數(shù)據(jù)機(jī)構(gòu)中關(guān)于并查集的詳解

 更新時(shí)間:2021年09月15日 15:42:46   作者:飛人01_01  
并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu),用于處理一些不相交集合的合并及查詢問題,如果你還不了解并查集,請(qǐng)看接下來的文章,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值

image-20210905162056592

本期文章源碼:GitHub

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

概念

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

具體的用法,我們會(huì)以下一篇文章《圖的相關(guān)算法》中,有一個(gè)克魯斯卡爾算法,用于生成最小生成樹,會(huì)用到并查集。

并查集的主要作用是求連通分支數(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)你看見一個(gè)叫花子,你就會(huì)想到他的老大就是幫主喬峰,像這樣的場(chǎng)景,就有了一定的歸屬感, 會(huì)自動(dòng)的認(rèn)為叫花子就是跟丐幫合并在一起的……

image-20210905145035613

說簡(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),可以是其他,比如二叉樹節(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ù)的代表(父親)是誰
    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)的并查集,剛開始每個(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è)組的代表(父親)是誰?
        
    }
    
    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è)方法:初始化并查集開始。

傳入進(jìn)去的參數(shù)不一定是List,也可以是Collection等等,表示一組數(shù)據(jù)即可! 首先我們的成員變量只有兩個(gè),分別是存儲(chǔ)節(jié)點(diǎn)的代表 和 當(dāng)前這個(gè)組的大小。初始化時(shí),我們分別認(rèn)為 每個(gè)節(jié)點(diǎn)是自己一個(gè)人一組的,也就是說,自己一個(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ù)是大小
    }
}

image-20210905153047158

判斷是不是同一個(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,我自己覺得算是并查集的核心,也這是這個(gè)方法,是并查集的查找的時(shí)間復(fù)雜度能在O(1)的主要因素。

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

image-20210905155005868

這樣的設(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;
}

合并操作

終于來到了最后的操作:合并。合并也比較簡(jiǎn)單,記住一個(gè)要點(diǎn):小組掛在大組的下面。也就是說,這一個(gè)節(jié)點(diǎn)所在的組要小一點(diǎn),我們直接將他“掛”在另一個(gè)組的下面。說簡(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); //新的組,大小是原來兩個(gè)組的和
            sizeMap.remove(node1Father); //小組的數(shù)據(jù),就不需要了,刪除
        } else { //node2 掛在 node1
            //跟上面操作類似
            fatherMap.put(node2Father, node1Father); 
            sizeMap.put(node1Father, node1Size + node2Size);
            sizeMap.remove(node1Father);
        }
    }
}

上面就是并查集的所有操作了,是不是很簡(jiǎn)單呢?

好啦,本期更新到此就結(jié)束啦,同學(xué)們,下期見?。?!

到此這篇關(guān)于Java數(shù)據(jù)機(jī)構(gòu)中關(guān)于并查集的詳解的文章就介紹到這了,更多相關(guān)Java 數(shù)據(jù)機(jī)構(gòu) 并查集內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • Mybatis?SqlSession案例詳解

    Mybatis?SqlSession案例詳解

    這篇文章主要介紹了Mybatis?SqlSession詳解,本文我們講了如何創(chuàng)建SqlSession的幾個(gè)步驟,最后我們獲得一個(gè)DefaultSqlSession對(duì)象,里面包含了執(zhí)行器Executor和配置對(duì)象Configuration,需要的朋友可以參考下
    2023-04-04
  • Mybatis-plus自動(dòng)填充不生效或自動(dòng)填充數(shù)據(jù)為null原因及解決方案

    Mybatis-plus自動(dòng)填充不生效或自動(dòng)填充數(shù)據(jù)為null原因及解決方案

    本文主要介紹了Mybatis-plus自動(dòng)填充不生效或自動(dòng)填充數(shù)據(jù)為null原因及解決方案,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2022-05-05
  • java數(shù)據(jù)結(jié)構(gòu)算法稀疏數(shù)組示例詳解

    java數(shù)據(jù)結(jié)構(gòu)算法稀疏數(shù)組示例詳解

    這篇文章主要為大家介紹了java數(shù)據(jù)結(jié)構(gòu)算法稀疏數(shù)組示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2022-06-06
  • Spring的編程式事務(wù)TransactionTemplate的用法詳解

    Spring的編程式事務(wù)TransactionTemplate的用法詳解

    TransactionTemplate提供了一種在代碼中進(jìn)行編程式事務(wù)管理的方式,使開發(fā)人員能夠在方法級(jí)別定義事務(wù)的開始和結(jié)束點(diǎn),本文介紹了Spring框架中TransactionTemplate的用法,感興趣的朋友跟隨小編一起看看吧
    2023-07-07
  • Java接口返回省市區(qū)樹形結(jié)構(gòu)的實(shí)現(xiàn)

    Java接口返回省市區(qū)樹形結(jié)構(gòu)的實(shí)現(xiàn)

    本文主要介紹了Java接口返回省市區(qū)樹形結(jié)構(gòu)的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-01-01
  • Java日期時(shí)間及日期相互轉(zhuǎn)換實(shí)現(xiàn)代碼

    Java日期時(shí)間及日期相互轉(zhuǎn)換實(shí)現(xiàn)代碼

    這篇文章主要介紹了Java日期時(shí)間及日期相互轉(zhuǎn)換實(shí)現(xiàn)代碼,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2019-12-12
  • Java的super關(guān)鍵字與instanceof運(yùn)算符使用方法

    Java的super關(guān)鍵字與instanceof運(yùn)算符使用方法

    這篇文章主要介紹了Java的super關(guān)鍵字與instanceof運(yùn)算符使用方法,是Java入門學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下
    2015-09-09
  • java線程并發(fā)semaphore類示例

    java線程并發(fā)semaphore類示例

    Java 5.0里新加了4個(gè)協(xié)調(diào)線程間進(jìn)程的同步裝置,它們分別是Semaphore, CountDownLatch, CyclicBarrier和Exchanger,本例主要介紹Semaphore,Semaphore是用來管理一個(gè)資源池的工具,可以看成是個(gè)通行證
    2014-01-01
  • java之Thread不捕獲異常默認(rèn)處理邏輯

    java之Thread不捕獲異常默認(rèn)處理邏輯

    這篇文章主要介紹了java之Thread不捕獲異常默認(rèn)處理邏輯,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2023-12-12
  • Java中十進(jìn)制和十六進(jìn)制的相互轉(zhuǎn)換方法

    Java中十進(jìn)制和十六進(jìn)制的相互轉(zhuǎn)換方法

    下面小編就為大家?guī)硪黄狫ava中十進(jìn)制和十六進(jìn)制的相互轉(zhuǎn)換方法。小編覺得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧
    2016-08-08

最新評(píng)論