淺談Union-Find并查集
Union-Find并查集作為一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于高效進行不相交集合的合并、查詢
基本原理
并查集的基本思路是用一個數(shù)組表示整個森林，其中樹的根節(jié)點唯一標(biāo)識了一個集合。當(dāng)我們搜索找到了某元素的的根節(jié)點時，就能確定其所屬的集合。顧名思義，對于一個并查集而言，其支持的操作方法自然包括：union、find。前者用于對指定的兩個元素建立連接，將二者歸屬為一個集合，即所謂的屬于同一個連通分量；后者用于查找指定元素所在連通分量的標(biāo)識。同時如果期望判斷兩個元素是否存在連接，即判斷并查集中的兩個元素是否存在于同一個連通分量。則可以通過find方法進行實現(xiàn)。具體地，分別查詢兩個元素的連通分量標(biāo)識，然后判斷是否相同即可。并查集常見的API操作，如下所示
//?建立p節(jié)點、q節(jié)點之間的連接
public?void?union(int?p,?int?q);
//?獲取p節(jié)點所在連通分量的標(biāo)識
public?int?find(int?p);
//?獲取連通分量的數(shù)量
public?int?getCount();
//?判斷兩個節(jié)點是否存在于同一個連通分量當(dāng)中
public?boolean?isConnected(int?p,?int?q);
樸素實現(xiàn)
假設(shè)存在編號分別為0～N-1的N個節(jié)點，那么在實現(xiàn)一個包含N個節(jié)點的并查集過程時。一個樸素的思想：我們可以通過一個數(shù)組進行維護。其中，數(shù)組的索引為節(jié)點編號，數(shù)組的值為該節(jié)點對應(yīng)的連通分量標(biāo)識。具體地，在union操作過程中，當(dāng)兩個節(jié)點的連通分量標(biāo)識不一致時，需要遍歷數(shù)組，將其中一個節(jié)點的連通分量標(biāo)識全部修改為其中另外一個節(jié)點的連通分量標(biāo)識。具體實現(xiàn)過程如下所示，可以看到這里直接將節(jié)點編號用來作為連通分量標(biāo)識。不難看出該實現(xiàn)非常簡單，雖然find操作非?？?。但對于union操作而言，效率卻不容樂觀。因為其需要遍歷整個數(shù)組
/**
?*?并查集
?*?@author?Aaron?Zhu
?*?@date?2022-02-20
?*/
public?class?UnionFind?{
????/**
?????*?Key:?節(jié)點;?Value:?節(jié)點對應(yīng)的連通分量標(biāo)識
?????*/
????private?int[]?id;
????/**
?????*?連通分量的數(shù)量
?????*/
????private?int?count;
????/**
?????*?構(gòu)造并查集實例
?????*?@param?size?節(jié)點數(shù)量
?????*/
????public?UnionFind(int?size)?{
????????count?=?size;
????????id?=?new?int[size];
????????for?(int?i=0;?i????????????id[i]?=?i;
????????}
????}
????/**
?????*?獲取連通分量的數(shù)量
?????*?@return
?????*/
????public?int?getCount()?{
????????return?count;
????}
????/**
?????*?判斷兩個節(jié)點是否存在于同一個連通分量當(dāng)中
?????*?@param?p
?????*?@param?q
?????*?@return
?????*/
????public?boolean?isConnected(int?p,?int?q)?{
????????return?find(p)?==?find(q);
????}
????/**
?????*?獲取p節(jié)點所在連通分量的標(biāo)識
?????*?@param?p
?????*?@return
?????*/
????public?int?find(int?p)?{
????????return?id[p];
????}
????/**
?????*?建立p節(jié)點、q節(jié)點之間的連接
?????*?@param?p
?????*?@param?q
?????*/
????public?void?union(int?p,?int?q)?{
????????int?pId?=?find(p);
????????int?qId?=?find(q);
????????if(?pId?==?qId?)?{
????????????//?p節(jié)點、q節(jié)點已經(jīng)位于同一連通分量當(dāng)中,?故直接返回
????????????return;
????????}
????????//?將p節(jié)點所在連通分量的標(biāo)識全部更改為q節(jié)點所在連通分量的標(biāo)識
????????for(int?i=0;?i????????????if(?id[i]?==?pId?)?{
????????????????id[i]?=?qId;
????????????}
????????}
????????//?連通分量的數(shù)量減1
????????count--;
????}
}
一種改進版本的并查集實現(xiàn)方案，即是提高優(yōu)化union操作的時間效率。這時數(shù)組的值不再直接存儲該節(jié)點對應(yīng)的連通分量標(biāo)識，而是存儲當(dāng)前節(jié)點所在連通分量的下一個節(jié)點。顯然當(dāng)數(shù)組的索引、值相同時，此時該索引對應(yīng)的節(jié)點即是該連通分量的標(biāo)識。事實上，這就是find操作的邏輯。而對于union操作而言，同樣需要先通過find分別獲取兩個節(jié)點各自的根節(jié)點。如果不一致，則將其中一個節(jié)點的根節(jié)點指向另外一個節(jié)點的根節(jié)點即可。具體實現(xiàn)如下所示。不難看出在該實現(xiàn)下，Union操作效率得到了顯著提高。一個連通分量中的各節(jié)點實際上構(gòu)成了一種樹形結(jié)構(gòu)
/**
?*?Quick?Union版本的并查集
?*?@author?Aaron?Zhu
?*?@date?2022-02-20
?*/
public?class?QuickUnionUF?{
????/**
?????*?Key:?節(jié)點;?Value:?當(dāng)前節(jié)點所在連通分量的下一個節(jié)點
?????*/
????private?int[]?parent;
????/**
?????*?連通分量的數(shù)量
?????*/
????private?int?count;
????/**
?????*?構(gòu)造并查集實例
?????*?@param?size?節(jié)點數(shù)量
?????*/
????public?QuickUnionUF(int?size)?{
????????count?=?size;
????????parent?=?new?int[size];
????????for?(int?i=0;?i????????????parent[i]?=?i;
????????}
????}
????/**
?????*?獲取連通分量的數(shù)量
?????*?@return
?????*/
????public?int?getCount()?{
????????return?count;
????}
????/**
?????*?判斷兩個節(jié)點是否存在于同一個連通分量當(dāng)中
?????*?@param?p
?????*?@param?q
?????*?@return
?????*/
????public?boolean?isConnected(int?p,?int?q)?{
????????return?find(p)?==?find(q);
????}
????/**
?????*?獲取p節(jié)點所在連通分量的標(biāo)識
?????*?@param?p
?????*?@return
?????*/
????public?int?find(int?p)?{
????????//?直到找到根節(jié)點
????????while?(p?!=?parent[p])?{
????????????p?=?parent[p];
????????}
????????return?parent[p];
????}
????/**
?????*?建立p節(jié)點、q節(jié)點之間的連接
?????*?@param?p
?????*?@param?q
?????*/
????public?void?union(int?p,?int?q)?{
????????int?pRoot?=?find(p);
????????int?qRoot?=?find(q);
????????if(?pRoot==qRoot?)?{
????????????//?p節(jié)點、q節(jié)點的根節(jié)點一樣,?故直接返回
????????????return;
????????}
????????//?將?p節(jié)點的根節(jié)點?指向?q節(jié)點的根節(jié)點
????????parent[pRoot]?=?qRoot;
????????//?連通分量的數(shù)量減1
????????count--;
????}
}
優(yōu)化
按秩合并
在Quick Union版本的并查集QuickUnionUF中，當(dāng)進行union操作的兩個節(jié)點并不是屬于同一連通分量時。我們需要將其中一棵樹的根節(jié)點指向另一顆樹的根節(jié)點，以實現(xiàn)將兩顆樹合并為一棵樹。但上述實現(xiàn)過程中，合并過程是隨意的。可能是將大樹的根節(jié)點指向小樹的根節(jié)點，也可能是將小樹的根節(jié)點指向大樹的根節(jié)點。這里就引出另外一個問題了——何為大樹？何為小樹？理論上來說，按樹的高度、樹中節(jié)點的數(shù)量都可以作為樹的比較標(biāo)準(zhǔn)。甚至從某種意義上來說，按樹的高度可能更為貼切。但這樣即會導(dǎo)致在同時使用路徑壓縮的場景時，樹的實際高度也會發(fā)生變化。換言之這兩種優(yōu)化策略將會不完全兼容，樹的高度實際上只是一個估計值了。故這里將樹中節(jié)點的數(shù)量定義為秩Rank，將樹中節(jié)點的數(shù)量作為樹的比較標(biāo)準(zhǔn)。因為理論上來說，樹越小、樹中節(jié)點的數(shù)量越少，則樹的高度自然也越小。而且其還能很好地與路徑壓縮優(yōu)化策略進行兼容，因為一棵樹無論怎么壓縮路徑，節(jié)點數(shù)都不會發(fā)生變化。至此，所謂按秩合并的策略就是在union操作過程中始終將 小樹的根節(jié)點 指向 大樹的根節(jié)點，以盡可能避免將二者合并為一顆高度更大的樹
路徑壓縮
在Quick Union版本的并查集QuickUnionUF中，在不斷進行union操作后。樹的高度會越來越大，即使使用了按秩合并這一策略，也無法避免。所以一旦樹中的節(jié)點距離根節(jié)點的路徑過長，其顯然會大大降低find操作的效率。為此我們需要在find操作中引入路徑壓縮這一優(yōu)化策略，具體可分為：隔代路徑壓縮、完全路徑壓縮
「1. 隔代路徑壓縮」
所謂隔代路徑壓縮指的是在find操作過程中遍歷某條路徑時，不斷將當(dāng)前節(jié)點直接指向祖父節(jié)點(即父節(jié)點的父節(jié)點)?？梢钥吹礁舸窂綁嚎s雖然壓縮的不夠徹底，但只需遍歷一次效率較高
「2. 完全路徑壓縮」
如果期望將待查找節(jié)點到根節(jié)點到路徑進行徹底壓縮，即該條路徑上點全部直連根節(jié)點。這就是所謂的完全路徑壓縮。而實現(xiàn)方式上較為簡單的就是通過遞歸的方式進行實現(xiàn)；否則如果期望通過非遞歸的方式實現(xiàn)，則需要進行兩次遍歷。具體地：第一次遍歷先找到根節(jié)點，第二次遍歷則需將此條路徑上的所有節(jié)點全部指向根節(jié)點
優(yōu)化實現(xiàn)
這里我們將在樸素的Quick Union版本實現(xiàn)的基礎(chǔ)上，對上述提到的兩種優(yōu)化思路進行實踐落地、集中展示
package?com.aaron.Algo;
/**
?*?優(yōu)化版本的并查集
?*?@author?Aaron?Zhu
?*?@date?2022-02-20
?*/
public?class?UF2?{
????/**
?????*?Key:?節(jié)點;?Value:?當(dāng)前節(jié)點所在連通分量的下一個節(jié)點
?????*/
????public?int[]?parent;
????/**
?????*?根節(jié)點對應(yīng)的秩,?即連通分量中的節(jié)點數(shù)
?????*/
????private?int[]?rank;
????/**
?????*?連通分量的數(shù)量
?????*/
????private?int?count;
????/**
?????*?構(gòu)造并查集實例
?????*?@param?size?節(jié)點數(shù)量
?????*/
????public?UF2(int?size)?{
????????count?=?size;
????????parent?=?new?int[size];
????????rank?=?new?int[size];
????????for(int?i=0;?i????????????parent[i]?=?i;
????????????rank[i]?=?1;
????????}
????}
????/**
?????*?獲取連通分量的數(shù)量
?????*?@return
?????*/
????public?int?getCount()?{
????????return?count;
????}
????/**
?????*?判斷兩個節(jié)點是否存在于同一個連通分量當(dāng)中
?????*?@param?p
?????*?@param?q
?????*?@return
?????*/
????public?boolean?isConnected(int?p,?int?q)?{
????????return?find(p)?==?find(q);
????}
????/**
?????*?獲取p節(jié)點所在連通分量的標(biāo)識
?????*?@param?p
?????*?@return
?????*?@apiNote?路徑壓縮:?隔代路徑壓縮
?????*/
????public?int?find(int?p)?{
????????//?直到找到根節(jié)點
????????while?(p?!=?parent[p])?{
????????????//?隔代路徑壓縮:?將當(dāng)前節(jié)點直接指向祖父節(jié)點(即父節(jié)點的父節(jié)點)
????????????parent[p]?=?parent[?parent[p]?];
????????????p?=?parent[p];
????????}
????????return?parent[p];
????}
????/**
?????*?獲取p節(jié)點所在連通分量的標(biāo)識
?????*?@param?p
?????*?@return
?????*?@apiNote?路徑壓縮:?完全路徑壓縮(迭代版本)
?????*/
/*
????public?int?find(int?p)?{
????????if(?p?!=?parent[p]?)?{
????????????parent[p]?=?find(?parent[p]?);
????????}
????????return?parent[p];
????}
*/
????/**
?????*?獲取p節(jié)點所在連通分量的標(biāo)識
?????*?@param?p
?????*?@return
?????*?@apiNote?路徑壓縮:?完全路徑壓縮(循環(huán)版本)
?????*/
/*
????public?int?find(int?p)?{
????????//?1.?找到根節(jié)點Root
????????int?root?=?p;
????????while(root!=parent[root])?{
????????????root?=?parent[root];
????????}
????????//?2.?循環(huán)壓縮?p->...->root?的路徑
????????while(?p?!=?root?)?{
????????????//?暫存當(dāng)前節(jié)點的下一個節(jié)點
????????????int?temp?=?parent[p];
????????????//?將當(dāng)前節(jié)點直接指向Root
????????????parent[p]?=?root;
????????????//?繼續(xù)處理下一個節(jié)點
????????????p?=?temp;
????????}
????????return?root;
????}
*/
????/**
?????*?建立p節(jié)點、q節(jié)點之間的連接
?????*?@param?p
?????*?@param?q
?????*/
????public?void?union(int?p,?int?q)?{
????????int?pRoot?=?find(p);
????????int?qRoot?=?find(q);
????????if(?pRoot==qRoot?)?{
????????????//?p節(jié)點、q節(jié)點的根節(jié)點一樣,?故直接返回
????????????return;
????????}
????????//?將?小樹的根節(jié)點?指向?大樹的根節(jié)點
????????//?同時,?更新大樹根節(jié)點對應(yīng)的節(jié)點數(shù)
????????if(rank[pRoot]?????????????parent[pRoot]?=?qRoot;
????????????rank[qRoot]?+=?rank[pRoot];
????????}?else?{
????????????parent[qRoot]?=?pRoot;
????????????rank[pRoot]?+=?rank[qRoot];
????????}
????????//?連通分量的數(shù)量減1
????????count--;
????}
}
參考文獻
算法·第4版 Robert Sedgewick、Kevin Wayne著