課程內容#
- 並查集：合併集合 [建立連通關係]、查找集合中的連通關係 [判斷某兩個點是否連通]
連通性問題#
-
-
規則：已經具有連通關係的點不能重複連接
-
將所有點分成了 2 個集合：①、②
-
[PS] 點與點的關係 (合併、判斷連通)→也可以是→集合與集合的關係
Quick-Find 算法#
- 核心思想：染色
- 一個顏色，對應一個類別
- 初始化：個體獨立，都寫成自己的索引，屬於一個獨立的集合裡
- ⭐把和自己連通的所有點的顏色改成要染的顏色
- 時間複雜度
- 連通判斷：O (1)—— 查找快，所以叫 Quick-Find
- 合併操作：O (N)—— 需要遍歷所有的點才能確定是否要合併
- 🆒引發思考：為什麼又叫森林呢？
- 關鍵在於合併操作，幾個點與幾個點的合併，集合與集合的合併
- 類似於子樹與子樹之間的合併，或是將一棵樹作為另一棵樹的子樹
- 所有的集合放在一起，類似於所有的樹放在一起，就是森林
- 那麼，除了染色還有其他方式嗎？
- 思考：染成了什麼顏色並不重要，只需要知道和哪些點的顏色相同，即連通
Quick-Union 算法#
- 生活啟發：找大哥，找領導
- 核心思想：找代表元素 [根結點]
- 存的值就是其代表元素
- 初始化：個體獨立，都寫成自己的索引，屬於一個獨立的集合裡
- ⭐找到兩點的代表元素，修改其中一個代表元素裡的值為另一個代表元素裡的值
- 代表元素：裡面的值就是它自己
- 聯想：大哥或他的小弟叛變了，都從大哥開始叛變，叛變到另一個小弟的大哥那
- 與 Quick-Find 的結果一樣，都是把一棵子樹整體合併到另一棵子樹，不過是通過代表元素來實現的
- 只能是根結點指向根結點
- 時間複雜度
- 都得找根結點，與樹高相關
- 連通操作：O (樹高)
- 合併操作：O (樹高)
- ❗ 2 種情況
- 正常狀態→均為 O (logN)
- 退化為一個鏈表→均為 O (N)
- 對於退化情況，如何解決呢？👇
weighted Quick-Union 算法#
【按秩合併】
- 如何避免退化？→保證枝繁葉茂
- 合併依據 1：樹高，矮樹掛在高樹下 [兩兩結合]
- 高度為 h 的樹，至少需要的結點個數 N 為 2 ^ (h - 1)
- 即樹高 h = log [2] N + 1 ≈ log [2] N
- [PS] 只有兩棵一樣樹高的樹合併，才會使高度增加
- 合併依據 2：結點數量，結點少的樹掛在結點多的樹下
- 兩種優化方式都能得到 O (logN)，但是合併依據 2【結點數量】更優秀一些
- 合併依據 1：樹高，矮樹掛在高樹下 [兩兩結合]
- ⭐為什麼合併依據 2 更優秀
- 【示例】什麼是平均查找次數
- 如下圖所示，計算了 A、B 樹的平均查找次數
-
- 結點深度即為結點的查找次數，平均查找次數 = 總查找次數 / 總結點數
- 此示例，B 樹的查找操作更快
- 【推導】合併依據 2 直接決定平均查找次數
- 對於有 SA、SB 個結點的 A、B 樹，它們的總查找次數 LA、LB 分別為：
-
- 其中，li 代表第 i 個結點的深度
-
- 此時進行合併操作，分別計算①A→B 和②B→A 的平均查找次數
- ①當 A 樹作為子樹合併到 B 樹時，為
-
- A 樹中的所有結點需要多查找一次
-
- ②當 B 樹作為子樹合併到 A 樹時，為
-
- B 樹中的所有結點需要多查找一次
-
- ①當 A 樹作為子樹合併到 B 樹時，為
- ❗【比較兩種方式的平均查找次數】
- 和樹高 [LA、LB] 沒有直接關係，而分子的結點數量 [SA、SB]【直接】決定查找次數，次數越小越好
- 👉誰的結點數少，就作為子樹被合併
- ❓思考：上面的推導是否證明高度無法作為合併依據呢？
- ❌否，高度間接影響著結點數量，一般情況高度越低，結點數量越少
- 但是，對於特殊情況，A 樹比 B 樹高，而 A 樹結點數量卻比 B 樹少時，還是按照【結點數量】作為合併依據，將 A 樹作為子樹合併到 B 樹裡
- 對於有 SA、SB 個結點的 A、B 樹，它們的總查找次數 LA、LB 分別為：
- 所以以結點數作為合併依據更優秀！👇合併思路如下
- 【示例】什麼是平均查找次數
- 在合併兩棵子樹時
- 如果結點數一樣，就按照普通 Quick-Union 的思路換
- 如果不一樣，結點數少的子樹的根結點接在👉結點數多的子樹的根結點下面
- [PS] 換句話說
- 在換大哥時
- 如果小弟數量一樣，就按照普通 Quick-Union 的思路換
- 如果不一樣，小弟少的大哥得跟👉小弟多的大哥混
+ 路徑壓縮#
- 參考隨堂練習 2 中 weighted Quick-Union 的可視化結果
-
- 0 的位置有些尷尬
- ❗ 不管 0 的代表元素為 1 還是 3，並沒區別，將 0 直接掛載 3 的下面，還能減小樹高
- 【方法】讓每一個非根結點直接指向根結點，讓結構扁平化
-
上述算法的效率比較
隨堂練習#
Quick-Find vs. Quick-Union#
-
-
【關鍵】理解 Quick-Union
- 0->1->2->4->5、3->4->5；8->9->7->6
- 查找、合併邊界：自己的代表元素就是本身時，停止
Quick-Union vs. weighted Quick-Union#
-
-
【關鍵】理解 weighted 的含義
- 當兩個集合的元素個數不一樣時
- 元素少的集合的代表元素的值👉元素多的集合的代表元素的值
- 小弟少的大哥得跟著小弟多的大哥混
-
結果可視化
-
- 很明顯，weighted 方法得到的樹更矮，合併、查找效率更高
-
代碼演示#
HZOJ-71：朋友圈#
範例輸入
6 5
1 1 2
2 1 3
1 2 4
1 4 3
2 1 3
範例輸出
No
Yes
- 思路
- 使用數據結構 —— 並查集
- 1 即合併操作，2 即查找操作
- 分別測試 Quick-Find、Quick-Union [+weighted、+ 路徑壓縮、-weighted] 的算法效率
- 代碼
Quick-Find#
-
-
-
查找、合併策略：基於染色
Quick-Union#
-
-
基於 Quick-find
- 修改結構定義的 color 為代表元素 father
- 修改查找操作：需要找到底
- 修改合併操作：也要找到兩個元素的底，才合併
-
易出現退化為鏈表的問題，下面進行優化
+ weighted#
-
-
基於 Quick-Union
-
添加 size 屬性，記錄結點所在集合的結點個數，以此作為合併策略
+ 路徑壓縮#
-
-
每次查找就會做一次路徑壓縮，將【查找元素】到【根代表元素】區間的所有元素都指向根代表元素 [根結點]
－weighted#
-
- 抹掉所有與 size 相關的操作
- 有了路徑壓縮後，不按秩合併 [去除 size 屬性] 也能達到很好的效果
HZOJ 平台上題目測試用時
| 方法 | Quick-Find | Quick-Union | +weighted | + 路徑壓縮 | weighted |
|---|---|---|---|---|---|
| 用時 (ms) | 744 | 2020 | 164 | 172 | 188 |
- Quick-Union 出現了退化問題
- 加了路徑壓縮後，不按秩合併也能達到很好的效果
- 🆒后三個方法都有不錯的效果！
思考點#
- 在 weighted Quick-Union 算法部分，結點數更優秀的推導是否證明高度無法作為合併依據呢？
- ❌否，高度間接影響著結點數量，一般情況高度越低，結點數量越少
- 但是，對於特殊情況，A 樹比 B 樹高，而 A 樹結點數量卻比 B 樹少時
- 需按照【結點數】作為合併依據❗ 將 A 樹作為子樹合併到 B 樹裡
Tips#
- 《C++ Primer》建議當工具書使用
-
