數據庫的并查集怎么理解

本篇內容主要講解“數據庫的并查集怎么理解”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“數據庫的并查集怎么理解”吧!

并查集

并查集被很多人認為是最簡潔而優(yōu)雅的數據結構之一，主要用于解決一些元素分組的問題。比如最小生成圖里的克魯斯卡爾算法就用的此知識點。它管理一系列不相交的集合，并支持兩種操作：

• 合并（Union）：把兩個不相交的集合合并為一個集合。

• 查詢（Find）：查詢兩個元素是否在同一個集合中。

當然，這樣的定義未免太過學術化，看完后恐怕不太能理解它具體有什么用。所以我們先來看看并查集最直接的一個應用小故事：江湖門派。故事讀完，并查集就會了~~~~~

故事會

江湖上散落著各式各樣的大俠，有上千個之多。他們沒有什么正當職業(yè)，整天背著劍在外面走來走去，碰到和自己不是一路人的，就免不了要打一架。但大俠們有一個優(yōu)點就是講義氣，絕對不打自己的朋友。而且他們信奉“朋友的朋友就是我的朋友”，只要是能通過朋友關系串聯起來的，不管拐了多少個彎，都認為是自己人。這樣一來，江湖上就形成了一個一個的幫派，通過兩兩之間的朋友關系串聯起來。而不在同一個幫派的人，無論如何都無法通過朋友關系連起來，于是就可以放心往死了打。但是兩個原本互不相識的人，如何判斷是否屬于一個朋友圈呢？

我們可以在每個朋友圈內推舉出一個比較有名望的人，作為該圈子的代表人物。這樣，每個圈子就可以這樣命名“中國同胞隊”美國同胞隊”……兩人只要互相對一下自己的隊長是不是同一個人，就可以確定敵友關系了。

但是還有問題啊，大俠們只知道自己直接的朋友是誰，很多人壓根就不認識隊長抓狂要判斷自己的隊長是誰，只能漫無目的的通過朋友的朋友關系問下去：“你是不是隊長？你是不是隊長？”這樣，想打一架得先問個幾十年，餓都餓死了，受不了。這樣一來，隊長面子上也掛不住了，不僅效率太低，還有可能陷入無限循環(huán)中。于是隊長下令，重新組隊。隊內所有人實行分等級制度，形成樹狀結構，我隊長就是根節(jié)點，下面分別是二級隊員、三級隊員。每個人只要記住自己的上級是誰就行了。遇到判斷敵友的時候，只要一層層向上問，直到最高層，就可以在短時間內確定隊長是誰了。由于我們關心的只是兩個人之間是否是一個幫派的，至于他們是如何通過朋友關系相關聯的，以及每個圈子內部的結構是怎樣的，甚至隊長是誰，都不重要了。所以我們可以放任隊長隨意重新組隊，只要不搞錯敵友關系就好了。于是，門派產生了。

理論推導

并查集的引入

并查集的重要思想在于，用集合中的一個元素代表集合。我曾看過一個有趣的比喻，把集合比喻成幫派，而代表元素則是幫主。接下來我們利用這個比喻，看看并查集是如何運作的。

最開始，所有大俠各自為戰(zhàn)。他們各自的幫主自然就是自己。（對于只有一個元素的集合，代表元素自然是唯一的那個元素）

現在1號和3號比武，假設1號贏了（這里具體誰贏暫時不重要），那么3號就認1號作幫主（合并1號和3號所在的集合，1號為代表元素）。

現在2號想和3號比武（合并3號和2號所在的集合），但3號表示，別跟我打，讓我?guī)椭鱽硎帐澳悖ê喜⒋碓兀?。不妨設這次又是1號贏了，那么2號也認1號做幫主。

現在我們假設4、5、6號也進行了一番幫派合并，江湖局勢變成下面這樣：

現在假設2號想與6號比，跟剛剛說的一樣，喊幫主1號和4號出來打一架（幫主真辛苦啊）。1號勝利后，4號認1號為幫主，當然他的手下也都是跟著投降了。

好了，比喻結束了。如果你有一點圖論基礎，相信你已經覺察到，這是一個樹狀的結構，要尋找集合的代表元素，只需要一層一層往上訪問父節(jié)點（圖中箭頭所指的圓），直達樹的根節(jié)點（圖中橙色的圓）即可。根節(jié)點的父節(jié)點是它自己。我們可以直接把它畫成一棵樹：
用這種方法，我們可以寫出最簡單版本的并查集代碼。

初始化

int fa[MAXN];void init(int n){
   
   
   for (int i = 1; i <= n; ++i)fa[i] = i;}

假如有編號為1, 2, 3, …, n的n個元素，我們用一個數組fa[]來存儲每個元素的父節(jié)點（因為每個元素有且只有一個父節(jié)點，所以這是可行的）。一開始，我們先將它們的父節(jié)點設為自己。

查詢

int find(int x){
   
   
   if(fa[x] == x)return x;elsereturn find(fa[x]);}

我們用遞歸的寫法實現對代表元素的查詢：一層一層訪問父節(jié)點，直至根節(jié)點（根節(jié)點的標志就是父節(jié)點是本身）。要判斷兩個元素是否屬于同一個集合，只需要看它們的根節(jié)點是否相同即可。

合并

void merge(int i, int j){
   
   
   fa[find(i)] = find(j);}

合并操作也是很簡單的，先找到兩個集合的代表元素，然后將前者的父節(jié)點設為后者即可。當然也可以將后者的父節(jié)點設為前者，這里暫時不重要。本文末尾會給出一個更合理的比較方法。

優(yōu)化一

路徑壓縮

最簡單的并查集效率是比較低的。例如，來看下面這個場景：

現在我們要merge(2,3)，于是從2找到1，fa[1]=3，于是變成了這樣：
然后我們又找來一個元素4，并需要執(zhí)行merge(2,4)：
從2找到1，再找到3，然后fa[3]=4，于是變成了這樣：

大家應該有感覺了，這樣可能會形成一條長長的鏈，隨著鏈越來越長，我們想要從底部找到根節(jié)點會變得越來越難。

怎么解決呢？我們可以使用路徑壓縮的方法。既然我們只關心一個元素對應的根節(jié)點，那我們希望每個元素到根節(jié)點的路徑盡可能短，最好只需要一步，像這樣：
其實這說來也很好實現。只要我們在查詢的過程中，把沿途的每個節(jié)點的父節(jié)點都設為根節(jié)點即可。下一次再查詢時，我們就可以省很多事。這用遞歸的寫法很容易實現：

合并（路徑壓縮）

int find(int x){
   
   
   return x == fa[x] ? x : (fa[x] = find(fa[x]));}

路徑壓縮優(yōu)化后，并查集的時間復雜度已經比較低了，絕大多數不相交集合的合并查詢問題都能夠解決。然而，對于某些時間卡得很緊的題目，我們還可以進一步優(yōu)化。

優(yōu)化二

按秩合并

有些人可能有一個誤解，以為路徑壓縮優(yōu)化后，并查集始終都是一個菊花圖（只有兩層的樹的俗稱）。但其實，由于路徑壓縮只在查詢時進行，也只壓縮一條路徑，所以并查集最終的結構仍然可能是比較復雜的。例如，現在我們有一棵較復雜的樹需要與一個單元素的集合合并：
假如這時我們要merge(7,8)，如果我們可以選擇的話，是把7的父節(jié)點設為8好，還是把8的父節(jié)點設為7好呢？

當然是后者。因為如果把7的父節(jié)點設為8，會使樹的深度（樹中最長鏈的長度）加深，原來的樹中每個元素到根節(jié)點的距離都變長了，之后我們尋找根節(jié)點的路徑也就會相應變長。雖然我們有路徑壓縮，但路徑壓縮也是會消耗時間的。而把8的父節(jié)點設為7，則不會有這個問題，因為它沒有影響到不相關的節(jié)點。
這啟發(fā)我們：我們應該把簡單的樹往復雜的樹上合并，而不是相反。因為這樣合并后，到根節(jié)點距離變長的節(jié)點個數比較少。

我們用一個數組rank[]記錄每個根節(jié)點對應的樹的深度（如果不是根節(jié)點，其rank相當于以它作為根節(jié)點的子樹的深度）。一開始，把所有元素的rank（秩）設為1。合并時比較兩個根節(jié)點，把rank較小者往較大者上合并。路徑壓縮和按秩合并如果一起使用，時間復雜度接近O(n)，但是很可能會破壞rank的準確性。

值得注意的是，按秩合并會帶來額外的空間復雜度，可能被一些卡空間的毒瘤題卡掉。

初始化（按秩合并）

void init(int n){
   
   
   for (int i = 1; i <= n; ++i){
   
   
   fa[i] = i;rank[i] = 1;}}

合并（按秩合并）

void merge(int i, int j){
   
   
   int x = find(i), y = find(j);    //先找到兩個根節(jié)點if (rank[x] <= rank[y])fa[x] = y;elsefa[y] = x;if (rank[x] == rank[y] && x != y)rank[y]++;                   //如果深度相同且根節(jié)點不同，則新的根節(jié)點的深度+1}

為什么深度相同，新的根節(jié)點深度要+1？如下圖，我們有兩個深度均為2的樹，現在要merge(2,5)：
這里把2的父節(jié)點設為5，或者把5的父節(jié)點設為2，其實沒有太大區(qū)別。我們選擇前者，于是變成這樣：

顯然樹的深度增加了1。另一種合并方式同樣會讓樹的深度+1。

到此，相信大家對“數據庫的并查集怎么理解”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續(xù)學習！