這一篇我們看看經典又神奇的並查集，顧名思義就是並起來查，可用於處理一些不相交集合的秒殺。
一：場景
有時候我們會遇到這樣的場景，比如:M={1,4,6,8},N={2,4,5,7}，我的需求就是判斷 {1,2} 是否屬於同一個集合，當然實現方法
有很多，一般情況下，普通青年會做出 O(MN) 的複雜度，那麼有沒有更輕量級的複雜度呢？嘿嘿，並查集就是用來解決這個問題的。
二：操作
從名字可以出來，並查集其實只有兩種操作，並 (Union) 和查 (Find)，並查集是一種演演算法，所以我們要給它選擇一個好的資料結構，
通常我們用樹來作為它的底層實現。
1. 節點定義
1 #region 樹節點
2 ///
4 ///
5 public class Node
6 {
7 ///
9 ///
10 public char parent;
11
12 ///
14 ///
15 public int rank;
16 }
17 #endregion
2.Union 操作
<1>原始方案
首先我們會對集合的所有元素進行打散，最後每個元素都是一個獨根的樹，然後我們 Union 其中某兩個元素，讓他們成為一個集合，
最壞情況下我們進行 M 次的 Union 時會存在這樣的一個連結串列的場景。
從圖中我們可以看到，Union 時出現了最壞的情況，而且這種情況還是比較容易出現的，最終導致在 Find 的時候就相當寒酸苦逼了，為 O(N) 。
<2> 按秩合併
我們發現出現這種情況的原因在於我們 Union 時都是將合併後的大樹作為小樹的孩子節點存在，那麼我們在 Union 時能不能判斷一下，
將小樹作為大樹的孩子節點存在，最終也就降低了新樹的深度，比如圖中的 Union(D,{E,F}) 的時候可以做出如下修改。
可以看出，我們有效的降低了樹的深度，在 N 個元素的集合中，構建樹的深度不會超過 LogN 層。 M 次操作的複雜度為 O(MlogN)，從代
碼上來說，我們用 Rank 來統計樹的秩，可以理解為樹的高度，獨根樹時 Rank=0，當兩棵樹的 Rank 相同時，可以隨意挑選合併，在新
根中的 Rank++就可以了。
1 #region 合併兩個不相交集合
2 ///
4 ///
5 ///
6 ///
7 ///
8 public void Union(char root1, char root2)
9 {
10 char x1 = Find(root1);
11 char y1 = Find(root2);
12
13 //如果根節點相同則說明是同一個集合
14 if (x1 == y1)
15 return;
16
17 //說明左集合的深度 < 右集合
18 if (dic[x1].rank < dic[y1].rank)
19 {
20 //將左集合指向右集合
21 dic[x1].parent = y1;
22 }
23 else
24 {
25 //如果 秩 相等，則將 y1 併入到 x1 中，並將 x1++
26 if (dic[x1].rank == dic[y1].rank)
27 dic[x1].rank++;
28
29 dic[y1].parent = x1;
30 }
31 }
32 #endregion
3.Find 操作
我們學演演算法，都希望能把一個問題最佳化到地球人都不能最佳化的地步，針對 logN 的級別，我們還能最佳化嗎？當然可以。
<1>路徑壓縮
在 Union 和 Find 這兩種操作中，顯然我們在 Union 上面已經做到了極致，下面我們在 Find 上面考慮一下，是不是可以在 Find 上運用
伸展樹的思想，這種伸展思想就是壓縮路徑。
從圖中我們可以看出，當我 Find(F) 的時候，找到 “F” 後，我們開始一直回溯，在回溯的過程中給，把該節點的父親指向根節點。最終
我們會形成一個壓縮後的樹，當我們再次 Find(F) 的時候，只要 O(1) 的時間就可以獲取，這裡有個注意的地方就是 Rank，當我們在路
徑壓縮時，最後樹的高度可能會降低，可能你會意識到原先的 Rank 就需要修改了，所以我要說的就是，當路徑壓縮時，Rank 儲存的就
是樹高度的上界，而不僅僅是明確的樹高度，可以理解成” 伸縮椅” 伸時候的長度。
1 #region 查詢 x 所屬的集合
2 ///
4 ///
5 ///
6 ///
7 public char Find(char x)
8 {
9 //如果相等，則說明已經到根節點了，返回根節點元素
10 if (dic[x].parent == x)
11 return x;
12
13 //路徑壓縮 (回溯的時候賦值，最終的值就是上面返回的”x”，也就是一條路徑上全部被修改了)
14 return dic[x].parent = Find(dic[x].parent);
15 }
16 #endregion
我們注意到，在路徑壓縮後，我們將 LogN 的複雜度降低到 Alpha(N)，Alpha(N) 可以理解成一個比 hash 函式還有小的常量，嘿嘿，這
就是演演算法的魅力。
最後上一下總的執行程式碼：
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
//定義 6 個節點
char[] c = new char[] { ‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’ };
DisjointSet set = new DisjointSet();
set.Init(c);
set.Union(‘E’, ‘F’);
set.Union(‘C’, ‘D’);
set.Union(‘C’, ‘E’);
var b = set.IsSameSet(‘C’, ‘E’);
Console.WriteLine(“C,E 是否在同一個集合:{0}”, b);
b = set.IsSameSet(‘A’, ‘C’);
Console.WriteLine(“A,C 是否在同一個集合:{0}”, b);
Console.Read();
}
}
///
///
public class DisjointSet
{
#region 樹節點
///
///
public class Node
{
///
///
public char parent;
///
///
public int rank;
}
#endregion
Dictionary
#region 做單一集合的初始化操作
///
///
public void Init(char[] c)
{
//預設的不想交集合的父節點指向自己
for (int i = 0; i < c.Length; i++)
{
dic.Add(c[i], new Node()
{
parent = c[i],
rank = 0
});
}
}
#endregion
#region 判斷兩元素是否屬於同一個集合
///
///
///
///
///
public bool IsSameSet(char root1, char root2)
{
return Find(root1) == Find(root2);
}
#endregion
#region 查詢 x 所屬的集合
///
///
///
///
public char Find(char x)
{
//如果相等，則說明已經到根節點了，返回根節點元素
if (dic[x].parent == x)
return x;
//路徑壓縮 (回溯的時候賦值，最終的值就是上面返回的”x”，也就是一條路徑上全部被修改了)
return dic[x].parent = Find(dic[x].parent);
}
#endregion
#region 合併兩個不相交集合
///
///
///
///
///
public void Union(char root1, char root2)
{
char x1 = Find(root1);
char y1 = Find(root2);
//如果根節點相同則說明是同一個集合
if (x1 == y1)
return;
//說明左集合的深度 < 右集合 if (dic[x1].rank < dic[y1].rank) { //將左集合指向右集合 dic[x1].parent = y1; } else { //如果 秩 相等，則將 y1 併入到 x1 中，並將 x1++ if (dic[x1].rank == dic[y1].rank) dic[x1].rank++; dic[y1].parent = x1; } } #endregion } } 文章來自網際網路部落格網站，原文連結 http://www.cnblogs.com/huangxincheng/archive/2012/12/16/2820519.html