​一、什么是并查集

對(duì)于一種數(shù)據(jù)結(jié)構(gòu)，肯定是有自己的應(yīng)用場(chǎng)景和特性，那么并查集是處理什么問(wèn)題的呢？

并查集是一種樹(shù)型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不相交集合（disjoint sets）的合并及查詢(xún)問(wèn)題,常常在使用中以森林來(lái)表示。在一些有N個(gè)元素的集合應(yīng)用問(wèn)題中，我們通常是在開(kāi)始時(shí)讓每個(gè)元素構(gòu)成一個(gè)單元素的集合，然后按一定順序?qū)儆谕唤M的元素所在的集合合并，其間要反復(fù)查找一個(gè)元素在哪個(gè)集合中。其特點(diǎn)是看似并不復(fù)雜，但數(shù)據(jù)量極大，若用正常的數(shù)據(jù)結(jié)構(gòu)來(lái)描述的話(huà)，往往在空間上過(guò)大，計(jì)算機(jī)無(wú)法承受；即使在空間上勉強(qiáng)通過(guò)，運(yùn)行的時(shí)間復(fù)雜度也極高，根本就不可能在比賽規(guī)定的運(yùn)行時(shí)間（1～3秒）內(nèi)計(jì)算出試題需要的結(jié)果，只能用并查集來(lái)描述。

你可能還有點(diǎn)迷糊并查集能怎么玩，看完這篇然后回頭看這兩個(gè)問(wèn)題(分別杭電1232和杭電1272)。

問(wèn)題1：

某省調(diào)查城鎮(zhèn)交通狀況，得到現(xiàn)有城鎮(zhèn)道路統(tǒng)計(jì)表，表中列出了每條道路直接連通的城鎮(zhèn)。省政府“暢通工程”的目標(biāo)是使全省任何兩個(gè)城鎮(zhèn)間都可以實(shí)現(xiàn)交通（但不一定有直接的道路相連，只要互相間接通過(guò)道路可達(dá)即可）。問(wèn)最少還需要建設(shè)多少條道路？

這個(gè)問(wèn)題很容易，給定的關(guān)系看看需要合并多少次就知道最少的建設(shè)道路數(shù)量。

問(wèn)題二：

小希希望任意兩個(gè)房間有且僅有一條路徑可以相通（除非走了回頭路）。小?，F(xiàn)在把她的設(shè)計(jì)圖給你，讓你幫忙判斷她的設(shè)計(jì)圖是否符合她的設(shè)計(jì)思路。比如下面的例子，前兩個(gè)是符合條件的，但是最后一個(gè)卻有兩種方法從5到達(dá)8。

​

這個(gè)問(wèn)題也很容易了，根據(jù)關(guān)系集合進(jìn)行合如果兩個(gè)元素已經(jīng)屬于一個(gè)集合，那就說(shuō)明不滿(mǎn)足要求啦。

二、并查集解析

通過(guò)上面介紹，相信你已經(jīng)清楚并查集就是解決集合中一些元素的合并和查詢(xún)問(wèn)題，現(xiàn)在就帶你解析這個(gè)算法。

2.1、初始化

開(kāi)始時(shí)候森林中每個(gè)元素沒(méi)有任何操作，它們之間是相互獨(dú)立的。我們通常會(huì)使用數(shù)組來(lái)表示這個(gè)森林(數(shù)組下標(biāo)對(duì)應(yīng)第幾個(gè)元素)，在初始化的時(shí)候數(shù)組中的各個(gè)值為-1，表示各自自己是一個(gè)集合(各自為王)，你可能會(huì)問(wèn)為啥是-1而不是一個(gè)其他的數(shù)，那是因?yàn)橛秘?fù)數(shù)可以代表這個(gè)元素是某個(gè)集合的根，然后它的權(quán)值表示集合中元素的個(gè)數(shù)。

​

2.2、并 union(int a,int b)

這里合并，并沒(méi)有你想象的直接合并那么簡(jiǎn)單，這里合并是合并a所在的集合和b所在的集合，但在操作層面a,b可能并不是根節(jié)點(diǎn)，所以也要先判斷一下。

為了便于理解，這里羅列一下最初操作可能的情況，初始時(shí)候各個(gè)元素都是獨(dú)立的集合，那么直接a指向b(或者b指向a)即arr[a]=b,同時(shí)為了表示這個(gè)集合有多少個(gè)，原本-1的b再次-1.即arr[b]=-2.表示以b為父根的集合節(jié)點(diǎn)有|-2|個(gè)。例如進(jìn)行union(1,4)，union(5,7)操作之后如圖所示：

​

正常情況的union(int a,int b)，假設(shè)我們就是a合并到b上，把b當(dāng)成父集合來(lái)看。a、b都可能是葉子節(jié)點(diǎn)，也可能是根節(jié)點(diǎn)。

此時(shí)你可以先分別找到a,b的父節(jié)點(diǎn)fa,fb(這個(gè)根可能是它自己),然后合并fa和fb兩個(gè)節(jié)點(diǎn)，例如上面如果union(1,5)那么其實(shí)就是等價(jià)union(4,7)。

為什么不直接操作a,b而是要找到他們的父親進(jìn)行操作?

原因1是因?yàn)閍,b可能是葉子節(jié)點(diǎn)，其值是正的表示已經(jīng)有父親了，如果直接操作會(huì)使其與原來(lái)的集合分離開(kāi)。另外集合中的數(shù)量(負(fù)數(shù))也不能有效疊加。

原因2是因?yàn)楹喜⒌臅r(shí)候如果合并如果a,b是非根節(jié)點(diǎn)操作，可能會(huì)造成這個(gè)樹(shù)的深度太大，不利于集合a中的查詢(xún)效率。

2.3、查 search(int a)

查詢(xún)，其實(shí)就是查詢(xún)這個(gè)節(jié)點(diǎn)的根節(jié)點(diǎn)是啥(也稱(chēng)代表元)，這個(gè)過(guò)程也有點(diǎn)類(lèi)似遞歸的過(guò)程，葉子節(jié)點(diǎn)值如果為正，那么就繼續(xù)查找這個(gè)值得位置的結(jié)果，一直到值為負(fù)數(shù)的時(shí)候說(shuō)明找到根節(jié)點(diǎn)，可以直接返回。

不過(guò)在查詢(xún)的過(guò)程中可以順便路徑優(yōu)化，這樣在頻繁查詢(xún)能夠大大降低時(shí)間復(fù)雜度。

三、優(yōu)化

你以為上面的就是并查集的全部？不不不，并查集還有不少需要掌握嘞，估計(jì)細(xì)心的人可能也會(huì)發(fā)現(xiàn)一些問(wèn)題。

你可能會(huì)有疑問(wèn)：

如何查看a，b是否在同一個(gè)集合？

查看是否在一個(gè)集合，只需要查看節(jié)點(diǎn)根祖先的結(jié)果是否相同即可。因?yàn)橹挥懈臄?shù)值是負(fù)的，而其他都是正數(shù)表示指向的元素。所以只需要一直尋找直到不為正數(shù)進(jìn)行比較即可！

a,b合并，究竟是a的祖先合并在b的祖先上，還是b的祖先合并在a上？

這里會(huì)遇到兩種情況，這個(gè)選擇也是非常重要的。你要弄明白一點(diǎn)：樹(shù)的高度+1的化那么整個(gè)元素查詢(xún)的效率都會(huì)降低！

所以我們通常是：小樹(shù)指向大樹(shù)(或者低樹(shù)指向高樹(shù))，這個(gè)使得查詢(xún)效率能夠增加！

當(dāng)然，在高度和數(shù)量的選擇上，還需要你自己選擇和考慮。

查找途中能不能路徑壓縮：

每次查詢(xún)，自下向上。當(dāng)我們調(diào)用遞歸的時(shí)候，可以順便壓縮路徑(將當(dāng)前數(shù)組的值等于遞歸返回的根節(jié)點(diǎn)的值)，我們查找一個(gè)元素只需要直接找到它的祖先，所以當(dāng)它距離祖先近那么下次查詢(xún)就很快。并且壓縮路徑的代價(jià)并不大！

試想一下，如果一個(gè)分支的深度為1000，不壓縮路徑那么這個(gè)分支每個(gè)節(jié)點(diǎn)平均查找次數(shù)為500，壓縮一次下次再查找就是1次。

學(xué)會(huì)路徑壓縮，你基本可以秒殺大部分并查集的題。

四、代碼實(shí)現(xiàn)

并查集實(shí)現(xiàn)起來(lái)較為簡(jiǎn)單，直接貼代碼！

import java.util.Scanner;
public class DisjointSet {
    static int tree[]=new int[100000];//假設(shè)有500個(gè)值
    public DisjointSet()    {set(this.tree);}
    public DisjointSet(int tree[]) 
    {
        this.tree=tree;
        set(this.tree);
    }
  //初始化所有都是-1 有兩個(gè)好處，這樣他們指向-1說(shuō)明是自己，
  //第二，-1代表當(dāng)前森林有-（-1）個(gè)
    public void set(int a[])
    {
        int l=a.length;
        for(int i=0;i<l;i++)
        {
            a[i]=-1;
        }
    }
    public int search(int a)//返回頭節(jié)點(diǎn)的數(shù)值
    {
        if(tree[a]>0)//說(shuō)明是子節(jié)點(diǎn)
        {
            return tree[a]=search(tree[a]);//路徑壓縮
        }
        else
            return a;
    }
    public int value(int a)//返回a所在樹(shù)的大?。▊€(gè)數(shù)）
    {
        if(tree[a]>0)
        {
            return value(tree[a]);
        }
        else
            return -tree[a];
    }
    public void union(int a,int b)//表示 a，b所在的樹(shù)合并
    {
        int a1=search(a);//a根
        int b1=search(b);//b根
        if(a1==b1) {System.out.println(a+"和"+b+"已經(jīng)在一棵樹(shù)上");}
        else {
        if(tree[a1]<tree[b1])//這個(gè)是負(fù)數(shù)，為了簡(jiǎn)單減少計(jì)算，不在調(diào)用value函數(shù)
        {
            tree[a1]+=tree[b1];//個(gè)數(shù)相加  注意是負(fù)數(shù)相加
            tree[b1]=a1;       //b樹(shù)成為a的子樹(shù)，直接指向a；
        }
        else
        {
            tree[b1]+=tree[a1];//個(gè)數(shù)相加  注意是負(fù)數(shù)相加
            tree[a1]=b1;       //b樹(shù)成為a的子樹(shù)，直接指向a；
        }
        }
    }
    public static void main(String[] args)
    {       
        DisjointSet d=new DisjointSet();
        d.union(1,2);
        d.union(3,4);
        d.union(5,6);
        d.union(1,6);

        d.union(22,24);
        d.union(3,26);
        d.union(36,24);
        System.out.println(d.search(6));    //頭
        System.out.println(d.value(6));     //大小
        System.out.println(d.search(22));   //頭
        System.out.println(d.value(22));     //大小
    }
}

五、結(jié)語(yǔ)

并查集屬于簡(jiǎn)單但是很高效率的數(shù)據(jù)結(jié)構(gòu)。在集合中經(jīng)常會(huì)遇到。如果不采用并查集而傳統(tǒng)暴力效率太低，而不被采納。

以上就是詳解Java實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)之并查集的詳細(xì)內(nèi)容，更多關(guān)于Java 數(shù)據(jù)結(jié)構(gòu) 并查集的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論