定義
并查集是計算機科學中為了解決
集合之間的合并和查詢操作而存在的一種樹型數據結構摄杂。并查集是由若干個大小不同的子樹來存儲表示的，也可以把整個并查集的存儲結構叫做森林澳叉，每顆子樹表示一個集合。集合的數量又叫做連通分量沐鼠。
基本操作
- find（查詢）：確定元素屬于哪一個子集涎显。它可以被用來確定兩個元素是否屬于同一子集坤检。
- union（合并）：將兩個子集合并成同一個集合。
- isConnected（兩個元素是否相連）：確定兩個元素是否屬于同一子集或者確定兩個元素是否相連期吓。
名詞解釋
- 森林：由若干個大小不同的子樹所表示的數據結構早歇。
- 連通分量：在這里簡單的可以理解為并查集中集合的數量。
- 樹的大刑智凇：樹的節(jié)點數量箭跳。
- 樹中某個節(jié)點的深度：該節(jié)點到樹的根節(jié)點的路徑上的鏈接數。
- 樹的高度：樹中所有節(jié)點中的最大深度悬襟。
解決的問題
- 在社交網絡中判斷兩個人是否屬于同一個交際圈衅码。
- 查詢網絡中的兩個網絡節(jié)點是否相連。
- 數學中判斷兩個元素是否屬于同一個集合脊岳。
- 數學中把兩個不相交的子集合并成一個集合逝段。
并查集的實現
quick find
為每一個集合都選取一個元素做為該集合的唯一編號，如果有兩個元素它們的編號相同割捅，那么就說明它們屬于同一個集合奶躯。
初始化
初始情況下如果有
N個元素，我們認為這個N個元素之間都是相互獨立的亿驾，也就是一共有N個集合嘹黔，每個集合只有一個元素。定義一個叫做ids的數組用來存儲每個集合的編號。每個集合的編號只需要保證不重復即可儡蔓」叮可以循環(huán)N次為每個集合從0到N-1編號。
如圖所示：
代碼實現：
class UnionFind {
private:
// 并查集中的元素個數
unsigned int elementNum = 0;
// 聯通分量喂江，也是集合的數量
unsigned int connectedComponent = 0;
// 存儲每個集合的編號
int *ids;
public:
UnionFind(unsigned int elementNum) {
this->elementNum = elementNum;
// 初始情況下聯通分量為元素個數
this->connectedComponent = elementNum;
this->ids = new int[elementNum];
// 初始化每個集合的編號為0至size-1
for (int i = 0; i < elementNum; i++) {
this->ids[i] = i;
}
}
};
查詢
查詢一個元素屬于哪個集合召锈，只需要查看這個元素的
id。這也是為什么叫quick find获询，因為查詢操作只需要O(1)的時間復雜度涨岁。
下圖中0,1,2這三個元素的id都是0，元素3和元素4的id分別是3和4吉嚣。
代碼實現：
int find(element) {
return this->ids[element];
}
兩個元素是否相連
判斷兩個元素是否屬于同一個集合時梢薪，只需要對比兩個元素的id是否相等即可。
下圖中0,1,2這三個元素的id都是0尝哆，所以它們是相連的秉撇。節(jié)點3和元素0,1,2都不相連，因為它們id不同秋泄。
代碼實現：
bool isConnected(int p ,int q) {
return this->find( p) == this->find(q);
}
合并
合并兩個集合時畜疾，只需要把任意其中一個集合中的所有元素的
id修改成另外一個集合的id即可，這樣一來原先的兩個集合都指向了同一個id印衔，就完成了合并操作啡捶。
如果我們需要把上圖中元素3和元素2合并，就有兩個辦法分別是：
-
把元素
2所在的集合的所有元素的id修改成元素3所在集合的id奸焙。image 把元素
3所在的集合的所有元素修改成元素2所在集合的id瞎暑。
不管選擇哪一種方法最終所表示的集合都是等價的，所以兩種方法都可以与帆。
代碼實現：
void unionElement(int p, int q) {
int pId = this->find(p);
int qId = this->find(q);
// 如果p和q本來就相連就不需要合并
if (pId == qId) {
return;
}
for (int i = 0; i < this->size; i ++) {
// 把其中一個集合中的所有元素的id修改成另外一個集合的id
if (this->id[i] == pId) {
this->ids[i] = qId;
}
}
// 合并之后少了一個集合了赌，connectedComponent就應該-1
this->connectedComponent --;
}
quick find這種實現方式，它的優(yōu)點在于可以快速的查詢元素屬于哪一個集合玄糟。缺點是在每次做合并的時候都需要遍歷整個ids數組然后去修改其中一個集合的所有元素的id勿她，這樣就會導致合并操作在數據量大的時候時間復雜度很高。
quick union
把每個元素看成一個
節(jié)點阵翎，每個節(jié)點指向該節(jié)點的父節(jié)點逢并。這一點跟傳統的樹行結構不太一樣，傳統的樹行結構是節(jié)點指向該節(jié)點的孩子節(jié)點郭卫。并查集中的每棵樹都表示一個集合砍聊，整個并查集所表示的就是一個森林。每棵樹會選取一個節(jié)點作為代表贰军，用來代表這棵樹所表示的集合玻蝌，這個代表節(jié)點也是樹的根節(jié)點。如果兩個元素的根節(jié)點相同則它們屬于同一棵樹也就是屬于同一個集合。
初始化
初始情況下俯树，我們還是認為每個
元素（節(jié)點）之間相互獨立帘腹，每棵樹只有一個根節(jié)點就是其本身，這個根節(jié)點用來代表這棵樹所表示的集合许饿。定義一個叫做parents的數組用來存儲每個節(jié)點的父節(jié)點竹椒。
如圖所示：
代碼實現：
class UnionFind {
private:
// 并查集中的元素個數
unsigned int elementNum = 0;
// 聯通分量，也是集合的數量
unsigned int connectedComponent = 0;
// 存儲每個節(jié)點的父節(jié)點
int *parents;
public:
UnionFind(unsigned int elementNum) {
this->elementNum = elementNum;
// 初始情況下聯通分量為元素個數
this->connectedComponent = elementNum;
this->parents = new int[elementNum];
// 初始化每個節(jié)點的父節(jié)點是其本身
for (int i = 0; i < elementNum; i++) {
this->parents[i] = i;
}
}
};
查詢
查詢一個元素屬于哪個集合米辐，只需要查看該元素所在樹的根節(jié)點的那個元素是誰，就屬于哪個集合书释。
下圖中0,1,2,3這四個元素的根節(jié)點都是0翘贮，元素3的根節(jié)點是3。整個并查集是由兩棵樹組成的一個森林爆惧。
如果要查詢節(jié)點3屬于哪一個集合就需要在parents數組中遞歸去尋找樹的根節(jié)點狸页，直到找到某個節(jié)點的父節(jié)點是其本身的一個節(jié)點，這個節(jié)點就是樹的根節(jié)點扯再。
遞歸實現：
int find(element) {
int parent = parents[element];
// 如果某個節(jié)點的父節(jié)點是其本身的一個節(jié)點芍耘，那么就是一個根節(jié)點
if (parent == element) {
return parent;
}
// 繼續(xù)遞歸查詢
return this->find(parent);
}
循環(huán)實現：
int find(element) {
while (parents[element] != element) {
element = parents[element];
}
return element;
}
兩個元素是否相連
判斷兩個元素是否屬于同一個集合時，只需要對比兩個元素所在樹的根節(jié)點是否是否是同一個節(jié)點即可熄阻。
下圖中0,1,2,3這四個元素的根節(jié)點都是0斋竞，證明它們屬于同一棵樹且相連。元素3的根節(jié)點是3秃殉。所以節(jié)點3和元素0,1,2,3都不相連坝初，因為它們的根節(jié)點不同。
代碼實現：
bool isConnected(int p ,int q) {
return this->find( p) == this->find(q);
}
合并
合并兩個集合時钾军，只需要把其中任意一顆樹的根節(jié)點的父節(jié)點修改成另一個顆樹的根節(jié)點鳄袍，這樣一來原先兩顆樹的根節(jié)點都是同一個節(jié)點，就完成了合并操作吏恭。
下圖中有兩個集合拗小，包含的元素分別是0,1,2,3和4,5,6。對應的兩棵樹的根節(jié)點分別是0和4樱哼。當合并這兩個集合時哀九，我們可以把這兩棵樹中的任意一棵樹的根節(jié)點的父節(jié)點修改成另一棵樹的根節(jié)點就可以完成合并操作。
我們把根節(jié)點為4的這棵樹的根節(jié)點的父節(jié)點修改成0搅幅，就合并成了一個集合勾栗。樹的形狀也就變成了下面這個樣子：
代碼實現：
void unionElement(int p, int q) {
int pRoot = this->find(p);
int qRoot = this->find(q);
// 如果兩個元素的根節(jié)點相同，則代表它們屬于同一個集合盏筐，就不再需要合并
if ( pRoot == qRoot ) {
return;
}
// 修改其中一棵樹根節(jié)點的父節(jié)點
this->parents[qRoot] = pRoot;
// 合并之后少了一個集合围俘，connectedComponent就應該-1
this->connectedComponent --;
}
加權quick union
quick union合并時存在的問題
下圖中兩棵樹所表示的集合相同，都分別表示的是擁有0,1,2,3,4這5個元素的一個集合。
左邊樹中節(jié)點4的深度為3界牡，而右邊樹中節(jié)點4的深度則為1反症。通過quick union的find的實現可以知道饭于，當在左邊樹中執(zhí)行find(4)時需要的時間復雜度是要高于右邊樹中執(zhí)行find(4)的，因為。所以得出一個結論就是：quick union中的find操作的時間復雜度是跟要查找節(jié)點在樹中的深度相關的找田。find操作需要一直向上尋找根節(jié)點，如果要查找的節(jié)點在樹中深度很深香浩，那么需要尋找根節(jié)點的次數也就會越多德挣。
優(yōu)化思路
由于在quick union中對兩個集合進行union操作時，不管是哪棵樹的根節(jié)點的父節(jié)點修改成另外一棵樹的根節(jié)點最終所得到的新樹所表示的集合都是等價的圈匆。
所以我們可以在union操作時把樹的高度較小的那棵樹的根節(jié)點的父節(jié)點修改成樹的高度較大的那顆樹的根節(jié)點漠另，在兩棵樹的高度相等時，就跟先前一樣不管是哪棵樹的根節(jié)點的父節(jié)點修改成另外一棵樹的根節(jié)點最終所得到的新樹所表示的集合和新樹的高度都是一樣的跃赚。
優(yōu)化思路證明
存在兩顆樹分別是A和B笆搓，它們樹的高度分別是Ah和Bh且Ah <Bh。我們有兩種辦法可以來完成union操作纬傲，分別是：
-
樹
A的根節(jié)點的父節(jié)點修改成樹B的根節(jié)點（優(yōu)化思路）修改之后由于在原來樹
A的根節(jié)點新增了一個節(jié)點满败，所以在新的樹中原來樹A的高度為Ah+1。由于Ah <Bh叹括，所以Ah+1<=Bh算墨。得到新樹的最大深度為Bh。 -
樹
B的根節(jié)點的父節(jié)點修改成樹A的根節(jié)點修改之后由于在原來樹
B的根節(jié)點新增了一個節(jié)點汁雷，所以在新的樹中原來樹B的高度為Bh+1米同。由于Ah <Bh，所以Ah<Bh+1摔竿。得到新樹的最大深度為Bh+1面粮。
得到結果Bh<Bh+1就可以證明我們的優(yōu)化思路是可以降低節(jié)點在樹中的深度的。
具體實現
初始化的時候跟
quick union一樣继低，只是多了數組用來存放每個節(jié)點的深度熬苍，我們定義這個數組叫ranks。初始化情況下我們讓每個節(jié)點在樹中的深度為1袁翁。find和isConnected的實現跟之前的quick union一樣柴底。
代碼實現：
class UnionFind {
private:
// 并查集中的元素個數
unsigned int elementNum = 0;
// 聯通分量，也是集合的數量
unsigned int connectedComponent = 0;
// 存儲每個節(jié)點的父節(jié)點
int *parents;
// 記錄每個根節(jié)點所在樹的深度
int *ranks;
public:
UnionFind(unsigned int elementNum) {
this->elementNum = elementNum;
// 初始情況下聯通分量為元素個數
this->connectedComponent = elementNum;
this->parents = new int[elementNum];
this->ranks = new int[elementNum];
for (int i = 0; i < elementNum; i++) {
// 初始化每個節(jié)點的父節(jié)點是其本身
this->parents[i] = i;
this->ranks[i] = 1;
}
}
// 合并元素
void unionElement(int p, int q) {
int pRoot = this->find(p);
int qRoot = this->find(q);
// 如果兩個元素的根節(jié)點相同粱胜，則代表它們屬于同一個集合柄驻，就不再需要合并
if (pRoot == qRoot) {
return;
}
int pRank = this->ranks[pRoot];
int qRank = this->ranks[qRoot];
// 把深度低的樹的根節(jié)點指向深度高的樹的根節(jié)點。
if (pRank > qRank) {
this->parents[qRoot] = pRoot;
} else if (pRank < qRank) {
this->parents[pRoot] = qRoot;
} else {
this->parents[pRoot] = qRoot;
this->ranks[qRoot]++;
}
// 合并之后少了一個集合焙压，connectedComponent就應該-1
this->connectedComponent --;
}
};
路徑壓縮
最優(yōu)樹結構
通過我們優(yōu)化之后的加權quick union還是沒有達到我們最優(yōu)樹結構鸿脓。下圖的兩棵樹都表示的是兩個相同的集合抑钟。左邊樹中的每個節(jié)點與根節(jié)點的距離大于等于1。右邊樹中的每個節(jié)點與根節(jié)點的距離等于1野哭，也就是我們想要的最優(yōu)樹結構在塔。
我們需要一個算法要壓縮路徑使得樹中的每個節(jié)點與根節(jié)點的距離為1。
路徑壓縮思路
把某個節(jié)點的父節(jié)點修改成該節(jié)點
父節(jié)點的父節(jié)點拨黔，一直向上對這條鏈接上的每個節(jié)點做相同的操作直到遇到根節(jié)點終止蛔溃，就可以壓縮每個節(jié)點到根節(jié)點的距離。
路徑壓縮過程演示
左邊樹中節(jié)點4的父節(jié)點的父節(jié)點是2篱蝇，所以把左邊樹中節(jié)點4的父節(jié)點修改成2贺待，得到右邊的樹：
左邊樹中節(jié)點4的父節(jié)點的父節(jié)點是0，所以把左邊樹中節(jié)點4的父節(jié)點修改成0零截，得到右邊的樹：
左邊樹中節(jié)點3的父節(jié)點的父節(jié)點是0麸塞，所以最后把左邊樹中節(jié)點3的父節(jié)點修改成0，就得到右邊的樹：
這樣一番操作之后最終得到結果就是我們想要的樹結構瞻润。
具體實現
由于路徑壓縮的過程跟
find操作有些類似，都是向上尋找節(jié)點甜刻，且都是遇到根節(jié)點終止绍撞，所以把路徑壓縮的過程就直接放在了find操作中。union操作不需要做任何改動得院。
find代碼實現：
int find(int element) {
int parent = parents[element];
if (parent == element) {
return parent;
}
// 路徑壓縮傻铣，parents[parent]得到的就是當前節(jié)點父節(jié)點的父節(jié)點
parents[element] = parents[parent];
return this->find(parents[element]);
}
完整源代碼
源代碼：https://github.com/acodercat/cpp-algorithms/blob/master/include/union_find.h
使用示例：https://github.com/acodercat/cpp-algorithms/blob/master/src/demo/union_find.cpp
