該文章為Princeton-Algorithms Part I讀書筆記延届，相關(guān)視頻在此。
1. 算法用于解決的問題: Dynamic Connectivity
1.1 兩個操作：Union & Find
關(guān)鍵：ObjectS + Union + Find
1.2 Connected Component
2. 實現(xiàn)
2.1 Quick-Find
是一種eager approach，why亦歉？
-
思想：利用一個id數(shù)組來對每個object進(jìn)行分類
quick find
Find(p, q): 查看各自的id是否相等
Union(p, q): 將所有與p的id相同的objects的id設(shè)置為與q的id相等
-
Java實現(xiàn)
Java 實現(xiàn) 效率：Union太慢彤恶。一次Union花O(N)本刽，連續(xù)對M個對象Union耗時O(MN)株憾。
2.2 Quick-Union
是一種lazy approach
-
思想：id數(shù)組中存著parent
quick union
Find(p, q): 查看各自的root是否相等
Union(p, q): 將p的root的id設(shè)置為q的root的id
-
Java實現(xiàn)
Java實現(xiàn) -
效率：Union還是太慢址愿，可能花O(N)來find對象的root
效率對比
可以從所維護(hù)的樹的角度來考慮：
quick find: 樹是平的律适，union之后改動很大
quick union: union雖然只需要對樹一次改動，但是可能樹很高上岗，find花很長時間
3.優(yōu)化
3.1 方法1: weighting
-
思想
- 對quick-union進(jìn)行修改使之避免太高的樹
- 記錄每個樹包含的對象數(shù) (size) Note:也可以是depth痴脾，算法complexity上是一樣的韵吨，但是code不同
- union操作時只將小的樹的root連向大的樹的root绢掰，這樣盡量平衡了樹芯砸，避免了樹不斷變高包帚。
unweighted vs weigthed
Java實現(xiàn)
-
效率: 相當(dāng)不錯宅静，每次union和find都是O(lgN)。連續(xù)對N個對象進(jìn)行M次Union-Find操作耗時O(MlgN)绰咽。
效率比較
為什么O(lgN)呢取募？因為一個節(jié)點最大深度只能為lgN
證明：
考慮一個節(jié)點x织阳，什么時候深度才會遞增1？當(dāng)它所在的樹小于要union的那棵樹時岳掐。因此union之后，它所在的樹的節(jié)點數(shù)翻倍吮螺。由于總節(jié)點數(shù)為N饶囚，因此x所在的樹由節(jié)點數(shù)為1開始，最多能翻倍lgN次鸠补，即x的深度最多是lgN萝风。
3.2 方法2：path compression
思想：每次利用root(p)找到某個點的root時，再來一次循環(huán)將路徑上的所有點都指向root紫岩，進(jìn)而又減少了樹的高度规惰！
-
效率：非常好。In theory, 連續(xù)對M個對象進(jìn)行N次Union-Find操作的amortized的時間復(fù)雜度為O(MlgN)被因。In pratical, 其實甚至接近了線性耗時O(N).
union find優(yōu)化效率
4. 應(yīng)用
4.1 Percolation穿透問題
具有NXN的區(qū)域卿拴，每個單元格有一定的概率要么空衫仑，要么填充。問題是求解是否上邊能穿透到下底堕花。
更實際的應(yīng)用有電路問題文狱，流水問題，社交問題等
此外缘挽，還有一個關(guān)于如何得到percolation threshold（穿透閾值）的實驗：
技巧：引入上下兩個virtual site便于check是否上邊與下底相連
