並查集 (Union-Find) 知識點整理與講解 什麼是並查集？ (Page 2) 並查集是一種樹狀的資料結構，用於處理一些不交集 (Disjoint Sets) 的合併及查詢問題。它的主要目的是： 將 n 個不同的元素分成若干個不相交的集合。 支援兩種核心操作： Find (查詢)：確定某個元素屬於哪個集合。通常是返回該集合的代表元素 (Representative)。 Union (合併)：將兩個元素所在的集合合併成一個新的集合。 常應用於解決連通性問題，例如判斷圖中的節點是否連通。一個連通分量 (Connected Component) 內的元素彼此都是連通的，這符合等價關係的特性：自反性 (reflexive)、對稱性 (symmetric)、傳遞性 (transitive)。 不交集資料結構 (Disjoint-Set Data Structure) (Page 3) 並查集維護一個包含 S = {S1, S2, ..., Sk} 的動態集合的集合，其中每個 Si 都是一個不交集。 代表元素 (Representative)：每個集合都由其內部的一個成員作為代表來標識。 核心操作定義： Make-Set(x)：創建一個新的集合，該集合只包含元素 x，x 同時也是這個集合的代表。 Union(x, y)：將包含元素 x 的集合 Sx 和包含元素 y 的集合 Sy 合併。合併後，Sx 和 Sy 會被銷毀 (從 S 中移除)，新的代表元素是 Sx U Sy 中的某個成員。 Find-Set(x)：返回包含元素 x 的集合的代表元素的指標。 應用：判斷無向圖的連通分量 (Page 4) 給定一個無向圖 G=(V, E)： 對圖中每個頂點 v in V[G]，執行 Make-Set(v)，將每個頂點初始化為一個獨立的集合。 對圖中每條邊 (u, v) in E[G]，如果 Find-Set(u) != Find-Set(v) (即 u 和 v 不在同一個集合中)，則執行 Union(u, v)，將它們所在的集合合併。 經過這些操作後，所有在同一個集合中的頂點都屬於同一個連通分量。這個過程涉及 n 次 Make-Set 操作，最多 m 次 Find-Set 操作 (實際上是 2m 次，因為每條邊檢查兩個端點)，以及最多 n-1 次 Union 操作。 並查集的實現方式與效能 4.1. 鏈表表示法 (Linked-List Representation) (Page 5, 7-9) 每個集合用一個鏈表表示。 鏈表的頭部 (Head) 作為該集合的代表元素。 每個節點都有一個指向其所在集合代表元素的指標。 操作複雜度： Make-Set(x)：Theta(1) 時間。 Find-Set(x)：Theta(1) 時間 (直接返回指向代表的指標)。 Union(x, y)：較為複雜。樸素的實現是將一個鏈表附加到另一個鏈表的末尾，然後更新被附加鏈表中所有節點指向代表元素的指標。如果每次都將短鏈表附加到長鏈表，並更新短鏈表中所有節點的代表指標，在最壞情況下 (例如，一系列 n-1 次合併操作，每次都合併一個單元素集合到一個大集合)，總時間複雜度可能達到 Theta(n^2)。 加權合併啟發式 (Weighted-Union Heuristic) (Page 8-9): 在執行 Union 操作時，總是將元素數量較少的集合（短鏈表）合併到元素數量較多的集合（長鏈表）上，如果長度相同則任意選擇。 定理：使用鏈表表示法和加權合併啟發式，一個包含 m 次 Make-Set、Union 和 Find-Set 操作的序列 (其中有 n 次 Make-Set 操作)，總時間複雜度為 O(m + n lg n)。 證明思路：計算一個元素的代表指標被修改的次數。考慮元素 x，第一次其指標被修改時，合併後的新集合至少有 2 個成員。第二次更新時，新集合至少有 4 個成員。更新 lg k 次後，新集合至少有 k 個成員。因此，一個元素的代表指標最多被更新 lg n 次。由於有 n 個元素，所有 Union 操作的總成本最多為 O(n log n)。Make-Set 和 Find-Set 各需要 O(1)，共 m 次操作，所以總成本是 O(m + n lg n)。 4.2. 不交集森林表示法 (Disjoint-Set Forest) (Page 10, 12) 每個集合用一棵有根樹表示，樹中的每個節點代表集合中的一個成員。 每個節點只儲存指向其父節點的指標。 樹的根節點是該集合的代表元素，其父指標指向自己 (或一個特殊標記)。 操作： Make-Set(x)：創建一個只有根節點 x 的樹，O(1) 時間。 Union(x, y)：找到 x 和 y 所在樹的根節點，然後讓其中一個根節點指向另一個根節點，O(1) 時間 (不包括查找根的時間)。 Find-Set(x)：從節點 x 開始，沿著父指標向上追溯直到找到根節點。時間複雜度取決於節點到根的距離（樹的高度）。 樸素實現的複雜度： Make-Set: O(1) Union (僅合併操作): O(1) Find-Set: 最壞情況下，樹可能退化成一條鏈，高度為 O(n)。因此，一系列 n 次 Union/Find-Set 操作可能需要 O(n^2) 時間。 不交集森林的優化啟發式 (Heuristics) (Page 13-16) 為了改善不交集森林的執行時間，引入了兩種重要的啟發式方法： 5.1. 按秩合併 (Union by Rank) 類似於加權合併啟發式。為每個節點維護一個 "秩 (rank)"，它代表該節點高度的一個上界 (注意，rank 不完全等於高度，尤其在路徑壓縮後)。 在執行 Union 操作時，總是將秩較小的樹的根指向秩較大的樹的根。如果兩個根的秩相同，則任意選擇一個作為父節點，並將其秩加 1。 5.2. 路徑壓縮 (Path Compression) 在執行 Find-Set(x) 操作時，當從 x 向上走到根節點的過程中，將路徑上的每個節點都直接指向根節點。 這樣可以顯著地 "扁平化" 樹的結構，使得後續對這些節點及其子孫節點的 Find-Set 操作更快。 5.3. 帶有優化的偽代碼 (Page 14-15) MAKE-SET(x) p[x] = x (父指標指向自己) rank[x] = 0 UNION(x, y) LINK(FIND-SET(x), FIND-SET(y)) FIND-SET(x) (實現路徑壓縮) if x != p[x] p[x] = FIND-SET(p[x]) (遞歸調用，並將父指標直接指向根) return p[x] LINK(x, y) (實現按秩合併，假設 x 和 y 都是根) if rank[x] > rank[y] p[y] = x else p[x] = y if rank[x] == rank[y] rank[y] = rank[y] + 1 5.4. 啟發式對執行時間的影響 (Page 16) 僅路徑壓縮：如果只有路徑壓縮，對於 f 次 FIND-SET 操作，最壞情況運行時間為： Theta(f log_(1+f/n)n) 如果 f >= n Theta(n+f lg n) 如果 f < n 同時使用按秩合併和路徑壓縮：最壞情況運行時間為 O(m alpha(n))，其中 m 是操作總數，n 是 MAKE-SET 操作的次數，alpha(n) 是反阿克曼函數 (Inverse Ackermann Function)，它是一個增長極其緩慢的函數。 在所有實際應用中，alpha(n) <= 4，因此可以認為運行時間在實務上接近線性於 m。 反阿克曼函數 alpha(n) 的數學背景 (Page 17-25) 這部分內容是為了嚴謹地分析並查集在同時使用兩種啟發式後的複雜度。 6.1. 函數迭代 (Functional Iteration) (Page 17) f^(i)(n) 表示函數 f(n) 對初始值 n 迭代應用 i 次。 f^(0)(n) = n f^(i)(n) = f(f^(i-1)(n)) for i > 0 例如，如果 f(n) = 2n，則 f^(i)(n) = 2^i * n。 6.2. 迭代對數函數 (Iterated Logarithm Function) lg*n (Page 18-19) lg^(i)n 定義為對 lg n 進行 i 次迭代。 lg*n = min{i >= 0 | lg^(i)n <= 1}。 lg*n 是一個增長非常非常緩慢的函數。 lg*2 = 1 lg*4 = 2 lg*16 = 3 lg*65536 = 4 lg*(2^65536) = 5 由於宇宙中可觀測的原子數量估計約為 10^80，而 10^80 << 2^65536，因此我們很少遇到輸入大小 n 使得 lg*n > 5。 6.3. 阿克曼函數的變體 Ak(j) (Page 20-24) 對於 k >= 0 和 j >= 1，定義函數 Ak(j)： Ak(j) = j+1 如果 k=0 Ak(j) = A_k-1^(j+1)(j) 如果 k >= 1 (這裡 A_k-1^(j+1)(j) 表示將函數 A_k-1 迭代應用 j+1 次到 j 上) k 代表函數 A 的層級 (level)。 重要性質： A0^(i)(j) = j+i A1(j) = A0^(j+1)(j) = j + (j+1) = 2j+1 A2(j) = A1^(j+1)(j) = 2^(j+1)(j+1)-1 Ak(j) 函數增長極其迅速。例如： A0(1) = 2 A1(1) = 3 A2(1) = 7 A3(1) = A2^(2)(1) = A2(A2(1)) = A2(7) = 2^8 * 8 - 1 = 2047 A4(1) = A3^(2)(1) = A3(A3(1)) = A3(2047) = A2^(2048)(2047) >> 10^80 6.4. 反阿克曼函數 alpha(n) (Page 25) alpha(n) = min{k | Ak(1) >= n}。 alpha(n) 是 Ak(1) 函數的反函數，表示 Ak(1) 至少達到 n 所需的最小層級 k。 alpha(n) 增長極其緩慢： alpha(n) = 0 for 0 <= n <= 2 alpha(n) = 1 for n = 3 alpha(n) = 2 for 4 <= n <= 7 alpha(n) = 3 for 8 <= n <= 2047 alpha(n) = 4 for 2048 <= n <= A4(1) 對於所有實際用途，alpha(n) <= 4。 O(m alpha(n)) 時間界限的攤還分析 (Amortized Analysis) (Page 26-39) 這部分是證明並查集在同時使用按秩合併和路徑壓縮啟發式後，其 m 次操作的總時間複雜度為 O(m alpha(n)) 的核心。它使用了勢能法 (Potential Method)。 基本引理 (Page 26-27): Lemma 4: 對於節點 x，有 rank[x] <= rank[p[x]]，如果 x != p[x] 則嚴格小於；rank[x] 不會改變，而 rank[p[x]] 隨時間單調遞增。 Corollary 5: 從任何節點沿路徑走向根，節點的秩嚴格增加。 Lemma 6: 每個節點的秩最多為 n-1 (一個較弱的界限，更緊的界限是 floor(lg n))。 將 UNION 轉換 (Page 29): Lemma 7: 可以將一個包含 MAKE-SET, UNION, FIND-SET 的操作序列 S' 轉換為一個包含 MAKE-SET, LINK, FIND-SET 的序列 S，其中每個 UNION 變成兩次 FIND-SET 和一次 LINK。如果 S 的運行時間是 O(m alpha(n))，則 S' 的運行時間也是 O(m' alpha(n))，因為 m 約等於 m'。 勢函數 (Potential Function) (Page 30-34): 為每個節點 x 在第 q 次操作後定義一個勢能 phi_q(x)。 整個森林的總勢能 Phi_q = sum_x phi_q(x)。初始時 Phi_0 = 0。 phi_q(x) 的定義比較複雜，依賴於 x 是否為根、rank[x]，以及兩個輔助函數： level(x) = max{k | rank[p[x]] >= Ak(rank[x])} 表示 Ak 應用於 x 的秩不大於其父節點秩的最大層級 k。 性質：0 <= level(x) < alpha(n)。 iter(x) = max{i | rank[p[x]] >= A_level(x)^(i)(rank[x])} 表示在 level(x) 層級上，可以迭代應用 A_level(x) 於 x 的秩多少次而不超過其父節點的秩。 性質：1 <= iter(x) <= rank[x] (如果 rank[x] >= 1)。 phi_q(x) 的具體定義 (Page 34): 如果 x 是樹根或 rank[x]=0：phi_q(x) = alpha(n) * rank[x] 如果 x 不是樹根且 rank[x] >= 1：phi_q(x) = (alpha(n) - level(x)) * rank[x] - iter(x) 勢能的性質 (Page 35-36): Lemma 8: 對於每個節點 x 和所有操作計數 q，0 <= phi_q(x) <= alpha(n) * rank[x]。 Lemma 9: 如果 x 不是根節點，在 LINK 或 FIND-SET 操作後，phi_q(x) <= phi_(q-1)(x) (勢能不增加)。此外，如果 rank[x] >= 1 且 level(x) 或 iter(x) 因操作而改變，則 phi_q(x) <= phi_(q-1)(x) - 1 (勢能至少減少1)。 各操作的攤還成本 (Amortized Cost) (Page 37-39): 攤還成本 c_hat_i = c_i + Phi_i - Phi_(i-1) (其中 c_i 是實際成本)。 Lemma 10 (MAKE-SET): 攤還成本 O(1)。實際成本 O(1)，勢能變化為0。 Lemma 11 (LINK): 攤還成本 O(alpha(n))。實際成本 O(1)。分析顯示，只有被作為父節點的根的勢能可能增加，且增加量最多為 alpha(n)。其他相關節點的勢能或者不變，或者減少。 Lemma 12 (FIND-SET): 攤還成本 O(alpha(n))。實際成本 O(s) (其中 s 是查找路徑上的節點數)。分析的關鍵在於證明，路徑上至少有 max(0, s - (alpha(n)+2)) 個節點的勢能會因路徑壓縮而減少至少1。這些勢能的減少可以 "支付" 實際成本中超出 O(alpha(n)) 的部分。 最終定理 (Page 40): Theorem 13: 一個包含 m 次 MAKE-SET, UNION, 和 FIND-SET 操作的序列 (其中 n 次是 MAKE-SET)，在使用按秩合併和路徑壓縮的並查集森林上，最壞情況運行時間為 O(m alpha(n))。 總結 並查集是一種高效的資料結構，用於處理不相交集合的合併與查詢。通過鏈表或森林結構實現，並結合按秩合併和路徑壓縮這兩種啟發式優化，其操作的攤還時間複雜度可以達到近乎線性的 O(alpha(n))，其中 alpha(n) 是增長極其緩慢的反阿克曼函數。這使得並查集在解決如圖的連通性等問題時非常高效。文件的後半部分詳細介紹了用於證明這一複雜度界限的數學工具和攤還分析過程。