這里有一篇十分精彩、生動的 并查集詳解 (轉(zhuǎn))；

• “朋友的朋友就是朋友”? 傳遞性，建立連通關(guān)系

disjoint set，并查集（一種集合），也叫不相交集，同時(shí)也是一種樹型的數(shù)據(jù)結(jié)構(gòu)；用于處理一些不相交集合（Disjoint Sets）的合并（merge）及查詢（find）問題。常常在使用中以森林來表示。集就是讓每個元素構(gòu)成一個單元素的集合，也就是按一定順序?qū)儆谕唤M的元素所在的集合合并。

并查集的構(gòu)成：

• 整數(shù)型的數(shù)組

  • 數(shù)組 pre[] 記錄了每個點(diǎn)的前導(dǎo)點(diǎn)是什么，pred[] ? 會形成一棵樹形結(jié)構(gòu)，樹形結(jié)構(gòu)的根，即為整棵樹的代表（reps）
  
  
  

• 兩個函數(shù)構(gòu)成

  • 函數(shù) find 是查找；
  • join 是合并；

1. 簡單實(shí)現(xiàn)

• find（暫不考慮，路徑壓縮的問題，path compression）

  int pred[1000];int find(int x){int r = x;while (r != pred[r]){r = pred[r];}return r; }

• join

  void find(int x, int y){int rx = find(x), ry = find(y);if (rx != ry)pred[rx] = ry;// 因?yàn)?rx 是 x 等的代表 ? pred[rx] == rx// 如此以來，x 所在的樹，y 所在的樹就實(shí)現(xiàn)了連通； }

2. 含有路徑壓縮的實(shí)現(xiàn)

路徑壓縮的概念可通過下圖清晰地展示出來，

路徑壓縮之后，減少了中間的傳遞過程，一步直達(dá)根節(jié)點(diǎn)（總代表）；

但需要注意的是，執(zhí)行一次 find，只把一個分支，統(tǒng)一化為兩層結(jié)構(gòu)；

int find(int x) { int r=x; while(r!=pre[r]) r=pre[r]; int i=x,j; while(pre[i]!=r) { j=pre[i]; pre[i]=r; i=j; } return r; }

轉(zhuǎn)載于:https://www.cnblogs.com/mtcnn/p/9423793.html

總結(jié)

以上是生活随笔為你收集整理的并查集（disjoint set）的实现及应用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。