算法（第四版）學習筆記1--第一章--union-find算法

算法第一章-基礎-1.5案例研究：union-find算法

問題陳述：動态連通性。給出一個整數集合，然後輸入一列整數對，<p,q>代表p和q是連通的，即在一個連通分量重，最後得到這個整數集合的所有連通分量。

三種算法（第四種屬理論）：

1）quick-find：用一個數組，數組下标代表所有整數，内容是下标整數所在的連通分量标志，選該連通分量裡的某一個整數作為标志。這樣，每兩個不同的分量做連接配接操作時，要将其中一個原屬的分量周遊修改一遍；做查找操作，隻需比較兩個分量的數組内容即可得知。

2）quick-union：用一個數組，數組下标代表所有整數，但内容不再是連通分量标志，而是其父節點。父節點就是通過做連接配接操作得到的，連接配接就是将一個節點作另一個節點的孩子，那麼結果就是一棵樹代表一個連通分量；做查找操作時，則要周遊一棵樹。

3）權重quick-union：與2）的差別在于，連接配接操作時，加上一個條件判斷，必須将高度較低的樹向高度較高的樹合并，這樣随着樹的擴大，整體深度會降低，周遊時就會更快。

4）最優算法（路徑壓縮）：将quick-find算法的思想加入到quick-union中，就是在find操作時，加一個循環将路徑上遇到的所有節點都連結到根節點，這樣當一棵樹的所有非根節點都被連結到根節點後，find操作就可以直接通過判斷是否有公共根節點判斷是否連通。這種方法不保證每個操作都在常數級别完成，其對權重quick-union也很難改進，這種算法理論研究很複雜。

是以，最優算法仍是權重quick-union。

各種union-find算法性能比較：

算法	存在N個觸點時成本的增長數量級（最壞情況）
構造函數	union()	find()
quick-find算法	N	N	1
quick-union算法	N	樹的高度	樹的高度
權重quick-union算法	N	lgN	lgN
使用路徑壓縮的權重quick-union算法	N	很接近但仍沒有達到1（均攤成本）
理想情況	N	1	1

注：也可以用繪制均攤成本圖像的方法觀察性能。方法：i表示處理的第i次連接配接。cost表示通路數組的次數。灰點（i,cost）表示第i次操作成本，紅點（i,total/i）表示均攤成本。