知識(shí)總覽：

并查集：

并查集就是一種集合，合并+查找====》集合

集合中元素只有2種關(guān)系，屬于這個(gè)集合或者屬于另外一個(gè)集合(或者說(shuō)不屬于這個(gè)集合)

一個(gè)集合里有好多元素，把同類型的元素構(gòu)造成一棵樹(shù)，其他類元素構(gòu)造成另外一棵樹(shù)，這個(gè)元素屬于哪個(gè)集合就用這棵樹(shù)的根節(jié)點(diǎn)表示，討論哪個(gè)元素屬于哪個(gè)集合，就是找這個(gè)元素所在樹(shù)的根節(jié)點(diǎn)。森林是由多個(gè)互不相交的樹(shù)構(gòu)成的

用互不相交的樹(shù)來(lái)表示集合的用途：

1.判斷某個(gè)元素屬于哪個(gè)集合------》從該元素出發(fā)，一路向北查到該元素所在根節(jié)點(diǎn)，根節(jié)點(diǎn)是哪個(gè)就是哪個(gè)樹(shù)，哪個(gè)集合

2.判斷2個(gè)元素是否從屬相同集合---》各個(gè)元素一路向北查到各元素所在根節(jié)點(diǎn)，就是各元素所在哪個(gè)樹(shù)，哪個(gè)集合，再判斷2個(gè)根節(jié)點(diǎn)是否相等，相等即為在同一個(gè)集合，不相等即為在不同集合

3.合并子集操作。即把2個(gè)集合合并成一個(gè)集合，可以把一個(gè)子集放到另外一個(gè)子集里成為另外一個(gè)子集的子集。即把一棵樹(shù)放到另外一棵樹(shù)里成為另外一棵樹(shù)的孩子。如例子喜歡紫葡萄、綠葡萄的人各自為一個(gè)子集，則可把2個(gè)子集合并成一個(gè)都喜歡葡萄的集合，即可讓喜歡紫葡萄的樹(shù)歸屬到喜歡綠葡萄樹(shù)的子樹(shù)即可

?

為什么用樹(shù)的雙親表示法表示并查集：用孩子節(jié)點(diǎn)字段中的parent指針指向該節(jié)點(diǎn)的父節(jié)點(diǎn)所在的數(shù)組下標(biāo)，查詢父節(jié)點(diǎn)快，查找孩子節(jié)點(diǎn)慢(因?yàn)橐闅v所有的節(jié)點(diǎn)，找parent是該節(jié)點(diǎn)的)，而并查集的查是一路向北找父節(jié)點(diǎn)的，所以用雙親表示法更容易找父節(jié)點(diǎn)，并且并查集的并是把一棵樹(shù)A合并到另外一棵樹(shù)B下成為樹(shù)B的子樹(shù)，如果用雙親表示法直接把A的根節(jié)點(diǎn)的parent字段改成B的根節(jié)點(diǎn)就可完成合并，綜上，用雙親表示法表示并查集很方便。

并查集的存儲(chǔ)結(jié)構(gòu)：

就是長(zhǎng)度為n的int型數(shù)組S。和樹(shù)的雙親表示法類似，即假如所有元素個(gè)數(shù)為n，則定義一個(gè)長(zhǎng)度為n的int型數(shù)組S，把元素依次放在數(shù)組中，每個(gè)元素對(duì)應(yīng)一個(gè)下標(biāo)，數(shù)組中的值即為父節(jié)點(diǎn)的數(shù)組下標(biāo)，即實(shí)際數(shù)組存儲(chǔ)的是該元素父節(jié)點(diǎn)的索引下標(biāo)，注意的是該數(shù)組S存儲(chǔ)的是所有元素的父節(jié)點(diǎn)的數(shù)組下標(biāo)，即使有的節(jié)點(diǎn)元素不屬于同一集合，沒(méi)有父節(jié)點(diǎn)的數(shù)組值為-1，如最后一張圖，三個(gè)樹(shù)三個(gè)集合統(tǒng)一放到S數(shù)組里，根節(jié)點(diǎn)ACD在數(shù)組中的值為-1，如果要把C合并到A，則直接修改C對(duì)應(yīng)的數(shù)組值為為A節(jié)點(diǎn)的下標(biāo)即可，即從-1修改為0，就完成了并查集的合并，并查集的查找即查找父節(jié)點(diǎn)直接查找S中的值可根據(jù)下標(biāo)直接定位到父節(jié)點(diǎn)元素

?

代碼實(shí)現(xiàn)：

并查集的初始化操作：初始化S[]數(shù)組中的值都為-1。并查集就是用一個(gè)Int型的數(shù)組進(jìn)行表示即UFSets，開(kāi)始并不知道這些元素是否屬于一個(gè)集合，所以把每個(gè)元素都初始化為一個(gè)個(gè)單獨(dú)的子集，即一個(gè)元素一個(gè)集合，完成這個(gè)操作只需要把數(shù)組上的每個(gè)元素的值設(shè)為-1即可，即表示每個(gè)元素都是單獨(dú)的子集。然后開(kāi)始進(jìn)行并查操作，應(yīng)該屬于同一個(gè)集合的元素就合并成一個(gè)集合。

并查集的查Find操作：

即找某個(gè)元素的所在樹(shù)的根節(jié)點(diǎn)。Find中x指的是元素所在數(shù)組中的下標(biāo)(注意不是S[]數(shù)組中的值，S[]數(shù)組中的值是元素下標(biāo)的父節(jié)點(diǎn)下標(biāo)值)，目前看數(shù)組S好像就是存的是元素的父節(jié)點(diǎn)數(shù)組下標(biāo)，數(shù)組中沒(méi)其他字段內(nèi)容。如要查L(zhǎng)元素即下標(biāo)為11即x=11的屬于哪個(gè)集合，一路向北查到根節(jié)點(diǎn)，S[11]=4>=0,即下一輪while循環(huán)，X=4，S[4]=1>= 0，下一輪while循環(huán)，X=1,S[1]=0>=0,下一輪while循環(huán)，X=0，S[0]=-1<=0，退出while循環(huán)，返回X=0，依次為查找L的父節(jié)點(diǎn)為E，E的父節(jié)點(diǎn)B，B的父節(jié)點(diǎn)A，A沒(méi)有父節(jié)點(diǎn)，結(jié)束。即L屬于A節(jié)點(diǎn)所在集合。

并查集的并Union操作：

即將2個(gè)不想交的集合合并成一個(gè)，修改其中一個(gè)集合中的父節(jié)點(diǎn)為另外一個(gè)節(jié)點(diǎn)的下標(biāo)。要傳入2個(gè)集合(2個(gè)樹(shù))的根節(jié)點(diǎn)下標(biāo)，如合并AC集合，要傳入A數(shù)組下標(biāo)0，C數(shù)組下標(biāo)2，即Root1=0，Root2=2，即把Root2合并到Root1即合并C到A，先判斷Root1==Root2直接返回即2個(gè)相同集合的不用合并，再把S[Root2]=Root1，即S[2]=0，即把要變成子樹(shù)的根節(jié)點(diǎn)S[]中的值變成另外一個(gè)樹(shù)的根節(jié)點(diǎn)數(shù)組下標(biāo)，即修改Root2的父節(jié)點(diǎn)數(shù)組索引下標(biāo)由-1改為0

如果在合并的時(shí)候給的Root1和Root2節(jié)點(diǎn)并不是集合的根節(jié)點(diǎn)，那么先通過(guò)Find操作找到這倆節(jié)點(diǎn)的根節(jié)點(diǎn)，再進(jìn)行Union操作

時(shí)間復(fù)雜度分析：

union操作只需修改數(shù)組中的值，時(shí)間復(fù)雜度為O(1)

Find操作要根據(jù)樹(shù)的形態(tài)確定時(shí)間復(fù)雜度，如果是最壞單支情況可能需要進(jìn)行n次while循環(huán)即O(n)，好的情況可能只需找一層或不用找吧即O(1)，即讓樹(shù)的高度h變低有助于減少時(shí)間復(fù)雜度

union操作的優(yōu)化

讓樹(shù)的時(shí)間復(fù)雜度變小，即讓樹(shù)的高度h變小，則在合并時(shí)讓小樹(shù)合大樹(shù)。因?yàn)樾?shù)合大樹(shù)只是讓小樹(shù)的父節(jié)點(diǎn)變成大樹(shù)的，大樹(shù)的高度h不會(huì)改變(大樹(shù)一般會(huì)比小樹(shù)高，合到大樹(shù)之后，小樹(shù)只是作為一個(gè)子樹(shù)出現(xiàn)，一般應(yīng)該不會(huì)影響大樹(shù)的高度)，如果讓大樹(shù)合到小樹(shù)上，大樹(shù)的高度h一般>小樹(shù)高度h，合過(guò)去之后大樹(shù)作為子樹(shù)出現(xiàn)，則起碼大樹(shù)高度h還高一層，且大樹(shù)節(jié)點(diǎn)數(shù)>小樹(shù)節(jié)點(diǎn)數(shù)，則大樹(shù)節(jié)點(diǎn)在進(jìn)行Find操作時(shí)都要再至少加一層高度

具體優(yōu)化：

如果是各個(gè)集合的根節(jié)點(diǎn)，優(yōu)化前根節(jié)點(diǎn)在S[]中的值為-1，優(yōu)化后讓S[]中的值<0，但是S[]代表的值為整個(gè)樹(shù)的節(jié)點(diǎn)個(gè)數(shù)，比如A集合即A樹(shù)有6個(gè)節(jié)點(diǎn)，A的index=0，優(yōu)化前S[0]=-1，優(yōu)化后S[0]=-6，同理C集合，S[2]=-1變成S[2]=-2，小樹(shù)合大樹(shù)即C合到A(因?yàn)镃有2個(gè)節(jié)點(diǎn)，A有6個(gè)節(jié)點(diǎn)，A是大樹(shù))，合并之后，A中多了2個(gè)節(jié)點(diǎn)，即A共有8個(gè)節(jié)點(diǎn)，S[0]=-8,C不再是根節(jié)點(diǎn)，變成S[2]=S[0]

優(yōu)化代碼實(shí)現(xiàn)如下：

1.用根節(jié)點(diǎn)的絕對(duì)值表示樹(shù)的節(jié)點(diǎn)總數(shù)2.union操作，小樹(shù)合并大樹(shù)

過(guò)程：目前認(rèn)為傳入的2個(gè)節(jié)點(diǎn)都是根節(jié)點(diǎn)，如果不是先去做find操作。判斷Root1和Root2是否相等即是否是相同集合，相同集合不做操作直接return。如果S[Root2]>S[Root1]則Root2合并到Root1(2個(gè)S值都為負(fù)數(shù)的情況下，證明root1的節(jié)點(diǎn)數(shù)更多)，Root1是大樹(shù)Root2是小樹(shù)，讓S[Root1]+=S[Root2]，S[Root2]=Root1，即Root1總節(jié)點(diǎn)數(shù)增加，Root2父節(jié)點(diǎn)改變成Root1，相反同上個(gè)過(guò)程

優(yōu)化之后結(jié)果：Find操作時(shí)間復(fù)雜度變成O(log2n),union操作時(shí)間復(fù)雜度不變還是O(1)，合并后構(gòu)造的樹(shù)的高度不超過(guò)log2n向下取整+1

知識(shí)回顧：

寫得好羅里吧嗦，其實(shí)知識(shí)點(diǎn)并不復(fù)雜。。。。。。。。。。。。?

?