工會找到分離集加權快速聯合與路徑壓縮算法

Question

關於有關聯合這個問題找到分離集，與路徑壓縮算法加權快速聯合

Weighted Quick-Union with Path Compression algorithm

不路徑壓縮影響IZ []數組（包含以i爲根的樹的長度的數組）？

Answer 1

就我所瞭解的代碼而言，數組iz []表示給定不相交集合中元素的數量。壓縮路徑時，不會爲每組修改該數字。因此，路徑壓縮不會影響iz []數組。

Answer 2

我會開始引用一些基本觀點。首先，這是用於實現不相交集合的最優算法，並且稱爲Union by Rank with path compression heuristic。該算法需要2個數組，第一個（id [] there）用作到父級的鏈接，第二個（iz []）給出該set中的節點數。

我們有2個操作 - 聯盟和連接。

聯盟是通過'等級'來完成的，通過使更小的樹子成爲更大的子樹，從而導致更低分攤成本，因此長度趨於最小。

當連接方法被調用後，在我們瞭解了該樹的根後，我們使用了一種路徑壓縮技術，該技術基本上將該特定節點指向該樹的根，因此在將來我們不必遍歷整個分支。由於iz []只包含該集合的節點數量，因此不會受到路徑壓縮的影響。