并查集及其C程序實現

等價關系與等價類

從數學上看，等價類是一個對象(或成員)的集合，在此集合中的所有對象應滿足等價關系。若用符號"≡"表示集合上的等價關系，那么對于該集合中的任意對象x,y, z，下列性質成立：

1、自反性：x ≡ x

2、對稱性：若 x ≡ y 則 y ≡ x

3、傳遞性：若 x ≡ y 且 y ≡ z 則 x ≡ z

因此，等價關系是集合上的一個自反、對稱、傳遞的關系。

通過金屬線連接起來的電器的連通性，就是一種等價關系。這種關系顯然具有自反性，因為任何一個器件都是與自身連通的；如果a 電連通b，那么b一定也電連通a，因此這種關系具有對稱性； 若a連通到b，并且b連通到c，那么a連通到c 。

并查集

并查集的一般用途就是用來維護某種具有自反、對稱、傳遞性質的關系的等價類。并查集一般以樹形結構存儲，多棵樹構成一個森林，每棵樹構成一個集合，樹中的每個節點就是該集合的元素，找一個代表元素作為該樹(集合)的祖先。

并查集支持以下三種操作：

1、Make_Set(x) 把每一個元素初始化為一個集合

初始化后每一個元素的父親節點是它本身，每一個元素的祖先節點也是它本身。

2、Find_Set(x) 查找一個元素所在的集合

查找一個元素所在的集合，只要找到這個元素所在集合的祖先即可。判斷兩個元素是否屬于同一集合，只要看他們所在集合的祖先是否相同即可。

3、Union(x,y) 合并x,y所在的兩個集合

合并兩個不相交集合操作很簡單：首先設置一個數組Father[x]，表示x的"父親"的編號。那么，合并兩個不相交集合的方法就是，找到其中一個集合的祖先，將另外一個集合的祖先指向它。

并查集的優化

1、Find_Set(x)時 路徑壓縮

尋找祖先時我們一般采用遞歸查找，但是當元素很多亦或是整棵樹變為一條鏈時，每次Find_Set(x)都是O(n)的復雜度，有沒有辦法減小這個復雜度呢？

答案是肯定的，這就是路徑壓縮，即當我們經過"遞推"找到祖先節點后，"回歸"的時候順便將它的子孫節點都直接指向祖先，這樣以后再次Find_Set(x)時復雜度就變成O(1)了。

2、Union(x,y)時 按秩合并

即合并的時候將元素少的集合合并到元素多的集合中，這樣合并之后樹的高度會相對較小。

主要代碼實現/* father[x]表示x的父節點 */

int father[MAX];

/* rank[x]表示x的秩 */

int rank[MAX];1

2

3

4

5

6/* 初始化集合 */

void Make_Set(int x)

{

father[x] = x;

rank[x] = 0;

}

1

2

3

4

5

6

7

8

9/* 查找x元素所在的集合,回溯時壓縮路徑 */

int Find_Set(int x)

{

if (x != father[x])

{

father[x] = Find_Set(father[x]);

}

return father[x];

}1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19/* 按秩合并x,y所在的集合 */

void Union(int x, int y)

{

x = Find_Set(x);

y = Find_Set(y);

if (x == y) return;

if (rank[x] > rank[y])

{

father[y] = x;

}

else

{

if (rank[x] == rank[y])

{

rank[y]++;

}

father[x] = y;

}

}

總結

以上是生活随笔為你收集整理的并查集算法c语言版,并查集及其C程序实现.doc的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。