在一些應用的問題中，需將n個不同的元素劃分成一組不相交的集合。開始時，每個元素自成一格單元素集合，然后按一定順序將屬于同一組的元素的集合合并。其間要反復用到查詢某個元素屬于哪個集合的運算。適合于描述這類問題的抽象數據類型稱為并查集。
1. 并查集的概述
并查集的數學模型是一組不相交的動態集合的集合S={A,B,C,...}，它支持以下的運算：
(1)union(A,B)：將集合A和B合并，其結果取名為A或B；
(2)find(x)：找出包含元素x的集合，并返回該集合的名字。
在并查集中需要兩個類型的參數：集合名字的類型和元素的類型。在許多情況下，可以用整數作為集合的名字。如果集合中共有n個元素，可以用范圍【1：n】以內的整數表示元素。實現并查集的一個簡單方法是使用數組表示元素及其所屬子集的關系。其中，用數組下標表示元素，用數組單元記錄該元素所屬的子集名字。如果元素類型不是整型，則可以先構造一個映射，將每個元素映射成一個整數。這種映射可以用散列表或其他方式實現。
2. 并查集的實現
采用數結構實現并查集的基本思想是，每個集合用一棵樹表示。樹的結點用于存儲集合中的元素名。每個樹結點還存放一個指向其父結點的指針。數根結點處的元素代表該數所表示的集合。利用映射可以找到集合中所對應的數結點。
父親數組是實現上述數結構的有效方法。
Java實現代碼：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
public class UnionFind { Node[] node; //父親數組 //并查集中的結點 private static class Node{ int parent; boolean root; private Node(){ parent = 1; root = true; } } //將每個元素初始化為一顆單結點樹 public UnionFind(int n){ node = new Node[n + 1]; for(int e= 0; e <= n; e++){ node[e] = new Node(); } }} |
find運算就是從元素e相應的結點走到樹根處，找出所在集合的名字。
|
1
2
3
4
5
6
|
public int find(int e){ while(!node[e].root){ e = node[e].parent; } return e; } |
union運算，合并兩個集合，只要將表示其中一個集合的樹的數根改為表示另一個集合的樹的數根的兒子結點。
|
1
2
3
4
5
|
public void union(int a, int b){ node[a].parent += node[b].parent; node[b].root = false; node[b].parent = a; } |
3. 快速并查集的實現
容易看出，在最壞情況下，合并可能使n個結點的樹退化成一條鏈，導致對所有元素各執行一次find將耗時O(n^2)。可做出以下改進來加速find運算。
1.）小樹合并到大樹
在union操作中，將表示小樹的數根改為表示大樹的數根的兒子結點。于是并查集中每個結點至多被移動O(logn)次，從而每個結點到數根的距離不會超過O(logn)。所有，每次find運算只需O(logn)時間。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
/** 合并兩個集合(加速)* 將表示小樹的數根改為表示大樹的數根的兒子結點*/public void union(int a, int b){if(node[a].parent < node[b].parent){node[b].parent += node[a].parent;node[a].root = false;node[a].parent = a;}else{node[a].parent += node[b].parent;node[b].root = false;node[b].parent = a;}} |
2.）路徑壓縮技術
在執行find時，實際上找到了從一個結點到數根的一條路徑。路徑壓縮就是把這條路上所有的結點都提升1層，以加快找到根結點的時間。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
/** find運算(加速)* 從元素e相應的結點走到樹根處，找出所在集合的名字*/public int find(int e){int current = e, p ,gp;/*排除當前結點或其父結點為根的情況后，加速find*/if(node[current].root){return current;}p = node[current].parent;if(node[current].root){return p;}gp = node[current].parent;while(true){node[current].parent = gp;if(node[gp].root){return gp;}current = p;p = gp;gp = node[p].parent;}} |
(并查集實現的詳細代碼及更多相關數據結構的代碼均在git)
參考資料：
1.《算法設計與分析》
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：https://blog.csdn.net/why_still_confused/article/details/51497973
