亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

Java數(shù)據(jù)結(jié)構(gòu)之并查集的實(shí)現(xiàn)

 更新時間:2022年01月23日 15:51:04   作者:chaojilaji  
并查集是一種用來管理元素分組情況的數(shù)據(jù)結(jié)構(gòu)。并查集可以高效地進(jìn)行如下操作。本文將通過Java實(shí)現(xiàn)并查集,感興趣的小伙伴可以了解一下

并查集就是將原本不在一個集合里面的內(nèi)容合并到一個集合中。

在實(shí)際的場景中用處不多。

除了出現(xiàn)在你需要同時去幾個集合里面查詢,避免出現(xiàn)查詢很多次,從而放在一起查詢的情況。

下面簡單實(shí)現(xiàn)一個例子,我們來舉例說明一下什么是并查集,以及究竟并查集解決了什么問題。

代碼解析

package com.chaojilaji.book.andcheck;

public class AndCheckSet {


    public static Integer getFather(int[] father, int u) {
        if (father[u] != u) {
            father[u] = getFather(father, father[u]);
        }
        return father[u];
    }

    public static void join(int[] father,int x, int y) {
        int fx = getFather(father,x);
        int fy = getFather(father,y);
        if (fx != fy){
            father[fx] = fy;
        }
    }

    public static void main(String[] args) {
        int n = 10;
        int[] a = new int[n];
        for (int i = 0;i<n;i++){
            a[i] = i; // 初始化定義一百個集合
        }
        for (int i=0;i<n;i++){
            System.out.println(i+" "+getFather(a, i)); // 對于每個集合,父節(jié)點(diǎn)都是自己
        }
    }
}

首先,我們定義了兩個函數(shù),分別為getFather和join,分別表示獲取u所在集合的根以及合并兩個集合。

先來看看getFather方法

public static Integer getFather(int[] father, int u) {
    if (father[u] != u) {
        father[u] = getFather(father, father[u]);
    }
    return father[u];
}

是找出值u所在集合的根節(jié)點(diǎn)是多少。一般來說,father[u]如果等于u本身,那么說明u所在節(jié)點(diǎn)就是根節(jié)點(diǎn),而這個算法是直到相等才退出,也就是說,對于從u到根節(jié)點(diǎn)的每個節(jié)點(diǎn)的father都被直接置為根節(jié)點(diǎn),同時返回了當(dāng)前節(jié)點(diǎn)的根節(jié)點(diǎn)。

然后來看看join方法

public static void join(int[] father,int x, int y) {
    int fx = getFather(father,x);
    int fy = getFather(father,y);
    if (fx != fy){
        father[fx] = fy;
    }
}

分別找出x和y兩個節(jié)點(diǎn)所在集合的根節(jié)點(diǎn),如果根節(jié)點(diǎn)不一樣,則將其中一個節(jié)點(diǎn)的father節(jié)點(diǎn)置為另一個節(jié)點(diǎn)即可,這樣就合并成了一個集合。

代碼應(yīng)用

public static void main(String[] args) {
    int n = 10;
    int[] a = new int[n];
    for (int i = 0;i<n;i++){
        a[i] = i; // 初始化定義n個集合
    }
    for (int i=0;i<n;i++){
        System.out.println(i+" "+getFather(a, i)); // 對于每個集合,父節(jié)點(diǎn)都是自己
    }
    System.out.println("-------------------------");
    join(a,0,1); // 合并 0 和 1
    for (int i=0;i<n;i++){
        System.out.println(i+" "+getFather(a, i));
    }
    // 由于合并了0和1,所以集合變成了9個,節(jié)點(diǎn)0和節(jié)點(diǎn)1的根都是節(jié)點(diǎn)1
    System.out.println("-------------------------");
    join(a,2,3); // 合并 2 和 3
    for (int i=0;i<n;i++){
        System.out.println(i+" "+getFather(a, i));
    }
    // 由于合并了2和3,所以集合變成8個,節(jié)點(diǎn)2和節(jié)點(diǎn)3的根都是節(jié)點(diǎn)3
    System.out.println("-------------------------");
    join(a,1,3); // 合并 1 和 3
    for (int i=0;i<n;i++){
        System.out.println(i+" "+getFather(a, i));
    }
    // 由于合并了1和3,所以集合變成7個,節(jié)點(diǎn)0,1,2,3的根都是節(jié)點(diǎn)3
}

首先,我們定義了n個集合,這n個集合的值是0~n-1,然后此時他們的父節(jié)點(diǎn)均等于他們本身,所以這就是n個獨(dú)立的集合,結(jié)果如下

0的父節(jié)點(diǎn)為 0 1的父節(jié)點(diǎn)為 1 2的父節(jié)點(diǎn)為 2 3的父節(jié)點(diǎn)為 3 4的父節(jié)點(diǎn)為 4 5的父節(jié)點(diǎn)為 5 6的父節(jié)點(diǎn)為 6 7的父節(jié)點(diǎn)為 7 8的父節(jié)點(diǎn)為 8 9的父節(jié)點(diǎn)為 9

然后調(diào)用 join(a,0,1)合并0集合和1集合,再輸出節(jié)點(diǎn)父集合情況為

0的父節(jié)點(diǎn)為 1 1的父節(jié)點(diǎn)為 1 2的父節(jié)點(diǎn)為 2 3的父節(jié)點(diǎn)為 3 4的父節(jié)點(diǎn)為 4 5的父節(jié)點(diǎn)為 5 6的父節(jié)點(diǎn)為 6 7的父節(jié)點(diǎn)為 7 8的父節(jié)點(diǎn)為 8 9的父節(jié)點(diǎn)為 9

可以看見,由于合并了0和1,所以集合變成了9個,節(jié)點(diǎn)0和節(jié)點(diǎn)1的根都是節(jié)點(diǎn)1。
然后調(diào)用 join(a,2,3) 合并2集合和3集合,輸出節(jié)點(diǎn)父集合情況為

0的父節(jié)點(diǎn)為 1 1的父節(jié)點(diǎn)為 1 2的父節(jié)點(diǎn)為 3 3的父節(jié)點(diǎn)為 3 4的父節(jié)點(diǎn)為 4 5的父節(jié)點(diǎn)為 5 6的父節(jié)點(diǎn)為 6 7的父節(jié)點(diǎn)為 7 8的父節(jié)點(diǎn)為 8 9的父節(jié)點(diǎn)為 9

可以看見,由于合并了2和3,所以集合變成8個,節(jié)點(diǎn)2和節(jié)點(diǎn)3的根都是節(jié)點(diǎn)3。
最后,我們再調(diào)用join(a,1,3) 合并1集合和3集合,輸出節(jié)點(diǎn)父集合情況為

0的父節(jié)點(diǎn)為 3 1的父節(jié)點(diǎn)為 3 2的父節(jié)點(diǎn)為 3 3的父節(jié)點(diǎn)為 3 4的父節(jié)點(diǎn)為 4 5的父節(jié)點(diǎn)為 5 6的父節(jié)點(diǎn)為 6 7的父節(jié)點(diǎn)為 7 8的父節(jié)點(diǎn)為 8 9的父節(jié)點(diǎn)為 9

可以看出來,由于合并了1和3,所以集合變成7個,節(jié)點(diǎn)0,1,2,3的根都是節(jié)點(diǎn)3。

實(shí)際應(yīng)用

代碼的層面來講,并查集很好實(shí)現(xiàn)。但是我們卻也可以發(fā)現(xiàn),其應(yīng)用場景似乎非常局限。
首先,我們需要定義出一個father[x] = x的數(shù)組,然后我們再去合并。似乎很難想到應(yīng)用場景。

那么我們可以想象一個場景,現(xiàn)在有個網(wǎng)絡(luò)拓?fù)鋱D,里面有n和網(wǎng)絡(luò)設(shè)施設(shè)備,然后又給了你這n個設(shè)施設(shè)備之間的連接關(guān)系,問你一共有多少個局部聯(lián)通網(wǎng)。
對于這個問題,我們就可以首先定義每個設(shè)備自己跟自己相連,然后每出現(xiàn)一條邊,就對這兩個設(shè)備采取join操作。最終我們在遍歷完所有的節(jié)點(diǎn),得到多少個不同的father,即表示有多少個不同的局部聯(lián)通網(wǎng)。

這樣的問題還可以延伸到我們的人際交友圈,首先每個人都是單獨(dú)的集合,在不斷認(rèn)識人的過程中,產(chǎn)生連通性。最終讓你確認(rèn)一共有多少個不互通的人際圈。

所以你會發(fā)現(xiàn),這本質(zhì)上就是求圖論中連通塊的個數(shù)。

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之并查集的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java并查集內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • Java中map和flatMap的區(qū)別舉例詳解

    Java中map和flatMap的區(qū)別舉例詳解

    這篇文章主要給大家介紹了關(guān)于Java中map和flatMap區(qū)別的相關(guān)資料,在Java中Stream接口有map()和flatmap()方法,兩者都有中間流操作,并返回另一個流作為方法輸出,需要的朋友可以參考下
    2023-10-10
  • 在MyBatis中使用 # 和 $ 書寫占位符的區(qū)別說明

    在MyBatis中使用 # 和 $ 書寫占位符的區(qū)別說明

    這篇文章主要介紹了在MyBatis中使用 # 和 $ 書寫占位符的區(qū)別說明,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2020-10-10
  • 初識Java基礎(chǔ)之?dāng)?shù)據(jù)類型與運(yùn)算符

    初識Java基礎(chǔ)之?dāng)?shù)據(jù)類型與運(yùn)算符

    Java是一種強(qiáng)類型語言,每個變量都必須聲明其數(shù)據(jù)類型,下面這篇文章主要給大家介紹了關(guān)于Java基礎(chǔ)之?dāng)?shù)據(jù)類型與運(yùn)算符的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2021-10-10
  • Spring Cloud入門教程之Zuul實(shí)現(xiàn)API網(wǎng)關(guān)與請求過濾

    Spring Cloud入門教程之Zuul實(shí)現(xiàn)API網(wǎng)關(guān)與請求過濾

    這篇文章主要給大家介紹了關(guān)于Spring Cloud入門教程之Zuul實(shí)現(xiàn)API網(wǎng)關(guān)與請求過濾的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。
    2018-05-05
  • SpringBoot注冊第三方Bean的方法總結(jié)

    SpringBoot注冊第三方Bean的方法總結(jié)

    眾所周知,SpringBoot默認(rèn)會掃描啟動類所在的包及其子包,一般我們都是在需要的類上通過注解的方式去將Bean注冊交給IOC進(jìn)行管理,但是注冊第三方Bean的方案卻不支持,所以本文給大家介紹了SpringBoot注冊第三方Bean的方法,需要的朋友可以參考下
    2024-01-01
  • Quarkus中filter過濾器跨域cors問題解決方案

    Quarkus中filter過濾器跨域cors問題解決方案

    這篇文章主要為大家介紹了Quarkus中filter過濾器跨域cors問題的解決方案,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2022-02-02
  • java實(shí)現(xiàn)網(wǎng)站微信掃碼支付

    java實(shí)現(xiàn)網(wǎng)站微信掃碼支付

    這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)網(wǎng)站微信掃碼支付,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-07-07
  • Jmeter對響應(yīng)數(shù)據(jù)實(shí)現(xiàn)斷言代碼實(shí)例

    Jmeter對響應(yīng)數(shù)據(jù)實(shí)現(xiàn)斷言代碼實(shí)例

    這篇文章主要介紹了Jmeter對響應(yīng)數(shù)據(jù)實(shí)現(xiàn)斷言代碼實(shí)例,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2020-09-09
  • Java中的Optional處理方法

    Java中的Optional處理方法

    在我們?nèi)粘5拈_發(fā)中,我們經(jīng)常會遇到?NullPointerException,如何才能優(yōu)雅的處理NPE?這里告訴大家一個較為流行的方法,這篇文章主要介紹了Java中的Optional處理方法,需要的朋友可以參考下
    2022-09-09
  • Java實(shí)現(xiàn)簡單訂餐系統(tǒng)

    Java實(shí)現(xiàn)簡單訂餐系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了Java實(shí)現(xiàn)簡單訂餐系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2019-01-01

最新評論