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

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

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

下面簡(jiǎn)單實(shí)現(xiàn)一個(gè)例子，我們來(lái)舉例說(shuō)明一下什么是并查集，以及究竟并查集解決了什么問(wè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; // 初始化定義一百個(gè)集合
        }
        for (int i=0;i<n;i++){
            System.out.println(i+" "+getFather(a, i)); // 對(duì)于每個(gè)集合，父節(jié)點(diǎn)都是自己
        }
    }
}

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

先來(lái)看看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)是多少。一般來(lái)說(shuō)，father[u]如果等于u本身，那么說(shuō)明u所在節(jié)點(diǎn)就是根節(jié)點(diǎn)，而這個(gè)算法是直到相等才退出，也就是說(shuō)，對(duì)于從u到根節(jié)點(diǎn)的每個(gè)節(jié)點(diǎn)的father都被直接置為根節(jié)點(diǎn)，同時(shí)返回了當(dāng)前節(jié)點(diǎn)的根節(jié)點(diǎn)。

然后來(lái)看看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兩個(gè)節(jié)點(diǎn)所在集合的根節(jié)點(diǎn)，如果根節(jié)點(diǎn)不一樣，則將其中一個(gè)節(jié)點(diǎn)的father節(jié)點(diǎn)置為另一個(gè)節(jié)點(diǎn)即可，這樣就合并成了一個(gè)集合。

代碼應(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個(gè)集合
    }
    for (int i=0;i<n;i++){
        System.out.println(i+" "+getFather(a, i)); // 對(duì)于每個(gè)集合，父節(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個(gè)，節(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個(gè)，節(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個(gè)，節(jié)點(diǎn)0,1,2,3的根都是節(jié)點(diǎn)3
}

首先，我們定義了n個(gè)集合，這n個(gè)集合的值是0~n-1，然后此時(shí)他們的父節(jié)點(diǎn)均等于他們本身，所以這就是n個(gè)獨(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

可以看見(jiàn)，由于合并了0和1，所以集合變成了9個(gè)，節(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

可以看見(jiàn)，由于合并了2和3，所以集合變成8個(gè)，節(jié)點(diǎn)2和節(jié)點(diǎn)3的根都是節(jié)點(diǎn)3。
最后，我們?cè)僬{(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

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

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

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

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

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

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

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

最新評(píng)論