【文章內容簡介】 輸出包含這個對象的等價類 。 } 給定集合 S = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }, 及如下等價對 : 0 ? 4, 3 ? 1, 6 ? 10, 8 ? 9, 7 ? 4, 6 ? 8, 3 ? 5, 2 ? 11, 11 ? 0 。 初始 {0},{1},{2},{3},{4},{5},{6},{7},{8},{9}, {10},{11} 0 ? 4 {0,4},{1},{2},{3},{5},{6},{7},{8},{9},{10},{11} 3 ? 1 {0,4}, {1,3},{2},{5},{6},{7},{8},{9},{10},{11} 6 ? 10{0,4},{1,3},{2},{5},{6,10},{7},{8},{9},{11} 8 ? 9 {0,4},{1,3},{2},{5},{6,10},{7},{8,9},{11} 7 ? 4 {0,4,7},{1,3},{2},{5},{6,10},{8,9},{11} 6 ? 8 {0,4,7},{1,3},{2},{5},{6,8,9,10},{11} 3 ? 5 {0,4,7},{1,3,5},{2},{6,8,9,10},{11} 2 ? 11{0,4,7},{1,3,5},{2,11},{6,8,9,10} 11 ? 0{0,2,4,7,11},{1,3,5},{6,8,9,10} 并查集 (UnionFind Sets) ? 并查集支持以下三種操作： ? Union (Root1, Root2) //并操作 ? Find (x) //搜索操作 ? UFSets (s) //構造函數(shù) ? 對于并查集來說，每個集合用一棵樹表示。 ? 為此，采用 樹的雙親表示 作為集合存儲表示。集合元素的編號從 0到 n1。其中 n 是最大元素個數(shù)。 ? 在 雙親表示 中， 第 i 個數(shù)組元素代表包含集合元素 i 的樹結點 。根結點的雙親為 1，表示集合中的元素個數(shù)。 ? 在同一棵樹上所有結點所代表的集合元素在同一個子集合中。 ? 為此，需要有兩個映射： ? 集合元素到存放該元素名的樹結點間的對應； ? 集合名到表示該集合的樹的根結點間的對應。 ? 設 S1= {0, 6, 7, 8 }, S2= { 1, 4, 9 }, S3= { 2, 3, 5 } 集合名 指針 0 S1 1 S2 2 S3 0 4 2 7 6 8 1 9 3 5 ? 為簡化討論 ， 忽略實際的集合名 ， 僅用表示集合的樹的根來標識集合 。 ? 初始時 , 用構造函數(shù) UFSets(s) 構造一個森林 , 每棵樹只有一個結點 , 表示集合中各元素自成一個子集合 。 ? 用 Find(i) 尋找集合元素 i 的根 。 如果有兩個集合元素 i 和 j, Find(i) == Find(j), 表明這兩個元素在同一個集合中 ， ? 如果兩個集合元素 i 和 j 不在同一個集合中 ,可用 Union(i, j) 將它們合并到一個集合中 。 下標 parent 1 1 1 1 1 1 1 1 1 1 0 1 2 3 4 5 6 7 8 9 S1 下標 parent 集合 S1, S2 和 S3 的雙親表示 4 4 3 2 3 2 0 0 0 4 0 1 2 3 4 5 6 7 8 9 0 7 6 8 4 1 9 2 3 5 S2 S3 S1 ? S2的可能的表示方法 下標 parent 集合 S1 ? S2 和 S3 的雙親表示 7 4 3 2 0 2 0 0 0 4 0 1 2 3 4 5 6 7 8 9 0 7 6 8 4 1 9 4 1 9 0 8 7 6 const int DefaultSize = 10。 class UFSets { //并查集類定義 private: int *parent。 //集合元素數(shù)組 int size。 //集合元素的數(shù)目 public: UFSets ( int s = DefaultSize )。 //構造函數(shù) ~UFSets ( ) { delete [ ] parent。 } //析構函數(shù) const UFSetsamp。 operator = (UFSetsamp。 right)。 //重載函數(shù) ： 集合賦值 void Union ( int Root1, int Root2 )。 //基本例程 : 兩個子集合合并 int Find ( int x )。 //基本例程 : 搜尋集合 x的根 void UnionByHeight ( int Root1, int Root2 )。 //改進例程 : 壓縮高度的合并算法 }。 UFSets :: UFSets ( int s ) { //構造函數(shù) size = s。 //集合元素個數(shù) parent = new int [size]。 //雙親指針數(shù)組 for ( int i = 0。 i size。 i++ ) parent[i] = 1。 //每一個自成一個單元素集合 } ? 并查集操作的算法 ? 查找 5 0 1 2 3 0 1 2 3 4 Find (4) Find (3) = 3 Find (2) =2 Find (1) = 1 Find (0) = 0 = 5 0 結束 int UFSets :: Find ( int x ) { if ( parent [x] 0 ) return x。 else return Find ( parent [x] )。 } 5 0 1 2 3 parent Parent[4] =3 Parent[3] =2 Parent[2] =1 Parent[1] =0 Parent[0] =5 0 1 2 3 4 void UFSets :: Union ( int Root1, int Root2 ) { //求兩個不相交集合 Root1與 Root2的并 parent[Root1] += parent[Root2]。 parent[Root2] = Root1。 //將 Root2連接到 Root1下面 } ? Find和 Union操作性能不好。假設最初 n 個元素構成 n 棵樹組成的森林， parent[i] = 1。做處理 Union(n2, n1), …, Union(1, 2), Union(0, 1)后，將產生退化的樹。 ? 合并 1 1 1 1 1 0 2 3 4 3 5 0 3 2 1 3 3 4 1 3 3 2 2 0 2 3 1 4 Union(0,1) 2 3 4 1 4 2 1 2 3 4 Union(1,2) Union(2,3) Union(3,4) ? 執(zhí)行一次 Union操作所需時間是 O(1)， n1次 Union操作所需時間是 O(n)。 ? 若再執(zhí)行 Find(0), Find(1), …, Find(n1), 若被搜索的元素為 i，完成 Find(i) 操作需要時間為 O(i)，完成 n 次搜索需要的總時間將達到 ? 改進的方法 ? 按樹的結點個數(shù)合并； ? 按樹的高度合并； ? 壓縮元素的路徑長度。 ???nini12OO )()(? 按樹結點個數(shù)合并 ?結點個數(shù)多的樹的根結點作根。 1 1 1 1 1 0 1 2 3 4 1 1 0 7 2 5 6 5 2 2 2 3 3 2 0 1 3 4 5 6 2 3 3 0 2 0 5 6 2 3 1 4 Union(2, 0) void UFSets :: WeightedUnion ( int Root1, int Root2 ) { //按 Union的加權規(guī)則改進的算法 int temp = parent[Root1] + parent[Root2]。 if ( parent[Root2] parent[Root1] ) { parent[Root1] = Root2。 //Root2中結點數(shù)多 parent[Root2] = temp。 //Root1指向 Root2 } else { parent[Root2] = Root1。 //Root1中結點數(shù)多 parent[Root1] = temp。 //Root2指向 Root1 } } ? 按樹高度合并 ? 高度高的樹的根結點作根。 0 0 0 0 0 0 1 2 3 4 0 0 0 2 2 5 6 2 1 2 2 3 3 2 0 1 3 4 5 6 2 3 3 0 2 0 5 6 2 3 1 4 Union(2, 0) Union操作的折疊規(guī)則 ? 為進一步改進樹的性能 ， 可以使用如下折疊規(guī)則來 “ 壓縮路徑 ” 。 即： 如果 j 是從 i 到根的路徑上的一個結點 ， 且 parent[j] ? root[j]， 則把 parent[j] 置為 root[i]。 0 0 6 7 8 6 7 8 1 9 1 9 3 5 3 5 從 i = 5 壓縮路徑 int UFSets :: CollapsingFind ( int i ) { //使用折疊規(guī)則的搜索算法 for ( int j = i。 parent[j] = 0。 j = parent[j] )。 //讓 j 循雙親指針走到根 while ( parent[i] != j ) { //換 parent[i] 到 j int temp = parent[i]。 parent[i] = j。 i = temp。 } return j。 } 搜索 (Search)的概念 靜態(tài)搜索表 ? 所謂 搜索 ，就是 在數(shù)據(jù)集合中尋找滿足某 種條件的數(shù)據(jù)對象 。 ? 搜索的結果通常有兩種可能： ? 搜索成功 ，即找到滿足條件的數(shù)據(jù)對象 這時 ,作為結果 , 可報告該對象在結構中 的位置 , 還可給出該對象中的具體信息。 ? 搜索不成功 ，或搜索失敗。作為結果 , 應報告一些信息 , 如失敗標志、位置等。 ? 通常稱用于搜索的數(shù)據(jù)集合為 搜索結構 ，它是由 同一數(shù)據(jù)類型的對象 (或記錄 )組成。 ? 在每個對象中有若干屬性，其中有一個屬性，其值可惟一地標識這個對象。稱為關鍵碼。 使用基于關鍵碼的搜索，搜索結果應是惟一的。 但在實際應用時，搜索條件是多方面的，可以使用 基于屬性的搜索方法，但搜索結果可能不惟一。 ? 實施搜索時有兩種不同的環(huán)境。 ?靜態(tài)環(huán)境 ，搜索結構在插入和刪除等操作的前后不發(fā)生改變。 ? 靜態(tài)搜索表 ?動態(tài)環(huán)境 ，為保持較高的搜索效率 , 搜索結構在執(zhí)行插入和刪除等操作的前后將自動進行調整，結構可能發(fā)生變化。 ? 動態(tài)搜索表 靜態(tài)搜索表 template class Type class dataList。 template class Type class Node { friend class dataListType。 pri