有鑑於今天有提到Equivalence class的關係，不過之前coding已經是一年半前的事了，完全忘光
觀念剛剛複習了一下，大致上應該理解的差不多...orz，但怕以後忘記還是紀錄一下。
觀念剛剛複習了一下，大致上應該理解的差不多...orz，但怕以後忘記還是紀錄一下。
能問題，而在這邊先舉一例子為0 ≡ 4, 3 ≡ 1, 6 ≡ 10, 8≡9, 7 ≡ 4, 6 ≡ 8, 3 ≡ 5, 2 ≡ 11, 11 ≡ 0
這樣透過 ≡ 可以知道
{0,2,11,4,7}
{3,1,5}
{6,8,9,10}
為三種類別的集合體
就是要將≡關係的資料集合在一起
在這邊將0 ～ 11 都視為一個根節點(-1)，如果我們不定義weight來組織一個tree(你可以將
{0,2,11,4,7})視為一棵tree，那麼他可能會變成degeneration tree，即一個節點一個節點個別
串接在一起
最差的例子為 0≡1 , 1≡2, 2≡3 .... n-1≡n
{0,2,11,4,7})視為一棵tree，那麼他可能會變成degeneration tree，即一個節點一個節點個別
串接在一起
最差的例子為 0≡1 , 1≡2, 2≡3 .... n-1≡n
n
|
n-1
|
n-2
...
|
1
|
此時會有個問題，假設我想要知道最下面的節點n的根節點為多少，此時我可能需要往上找n次
才會找到root，那麼總和所有的節點找到根節點的步驟可能會花
n+n-1+n-2+..+1 = n(n+1)/2 = O(n^2)
n+n-1+n-2+..+1 = n(n+1)/2 = O(n^2)
因此，在這邊透過weightedUnion，即0 ≡ 4, 3 ≡ 1, 6 ≡ 10, 8≡9，各自組成一顆tree時
[-2] [-2] [-2] [-2]
0 3 6 8
| | | |
4 1 10 9 (weightedUnion的演算法我就不打了囧)
這邊可以解釋成4根節點value為0，0根節點value為-2，表示成array為parent[0] = -2,
parent[4] = 0
parent[4] = 0
那麼再經由第二輪 7 ≡ 4, 6 ≡ 8, 3 ≡ 5, 2 ≡ 11
此時7 ≡ 4， 7根節點value為-1， 此時需透過collapsingFind找到4的根節點為多少(由於滿足4's
root value>=0，知道4不是這棵tree實際的根節點)
再根據weightedUnion規則，節點數少的tree會依附在節點數多的tree下面
結果將變成
[-3]
0
| |
4 7
此時parent[0] = -3 , parent[4] = 0
之後不斷反覆檢查是否需要collapsingFind及WeightedUnion就可以長成三棵tree
{0,2,11,4,7}
{3,1,5}
{6,8,9,10}
大致情況是如此，若有講錯的地方請多多指教囉...orz
(迷之音...之前我PO在FB的文章，在此blogger做分享並做個紀錄(毆))
留言
張貼留言