直覺描述
依舊是動態(tài)聯(lián)通性問題简逮。換一種方法來處理。
Quick Union
與Quick Find一樣蒜胖，我們需要用到index今缚。
針對節(jié)點(diǎn)算柳，有[0, 1, ...9]作為index。
看看有哪些連接荚斯。
union(0, 1), union(1, 2), union(0, 5), union(1, 6),
union(2, 7), union(3, 4), union(3, 8), union(4, 9)
Quick Find使用的方式是埠居，將聯(lián)通的節(jié)點(diǎn)index改為一樣的，所以更新后的index可以分為若干組事期，每個(gè)組內(nèi)的index是相同的，每個(gè)組表示相互聯(lián)通的節(jié)點(diǎn)組合纸颜。組員間的關(guān)系可以看作是平級的兽泣。
Quick Union使用的方式是，將聯(lián)通的節(jié)點(diǎn)之間用父子關(guān)系串聯(lián)起來胁孙，所以組員間的關(guān)系可以看作是樹狀的唠倦。
為了方便起見，我們將每次union(m, n)定義為涮较，m為子稠鼻，n為父。每次union狂票，都是用m所代表的組的頂部候齿，即父節(jié)點(diǎn)，連接到n節(jié)點(diǎn)所代表的組的父節(jié)點(diǎn)之下闺属，這樣慌盯，m所代表的這一組有了新的頂部節(jié)點(diǎn)，也就是n那一組的父節(jié)點(diǎn)掂器。整個(gè)過程如下面的示例分步進(jìn)行：
-
union(0, 1)
圖2: union(0, 1)
index更新為：
[1亚皂，1，2国瓮，3灭必，4，5乃摹，6禁漓，7，8峡懈，9]
-
union(1, 2)
圖3: union(1, 2)
index更新為：
[1璃饱，2，2肪康，3荚恶，4撩穿，5，6谒撼，7食寡，8，9]
-
union(0, 5)
圖4: union(0, 5)
index更新為：
[1廓潜，2抵皱，5，3辩蛋，4呻畸，5，6悼院，7伤为，8，9]
-
union(1, 6)
圖5: union(1, 6)
index更新為：
[1据途，2绞愚，5，3颖医，4位衩，6，6熔萧，7糖驴，8，9]
-
union(2, 7)
圖6: union(2, 7)
index更新為：
[1哪痰，2遂赠，5，3晌杰，4跷睦，6，7肋演，7抑诸，8，9]
-
union(3, 4)
圖7: union(3, 4)
index更新為：
[1爹殊，2蜕乡，5，4梗夸，4层玲，6，7，7辛块，8畔派，9]
-
union(3, 8)
圖8: union(3, 8)
index更新為：
[1，2润绵，5线椰，4，8尘盼，6憨愉，7，7卿捎，8配紫，9]
-
union(4, 9)
圖9: union(4, 9)
index更新為：
[1，2娇澎，5笨蚁，4，8趟庄，6，7伪很，7戚啥，9，9]
接下來就很好辦锉试，如果我們想知道兩個(gè)節(jié)點(diǎn)是否聯(lián)通猫十，只需要查詢它們所屬的頂端父節(jié)點(diǎn)是否相同就可以了。比如:
connected(2, 3) = false
2的頂端父節(jié)點(diǎn)是7呆盖，3的頂端父節(jié)點(diǎn)是9拖云，因此它們不聯(lián)通；
復(fù)雜度
接下來我們看一下Quick Union的復(fù)雜度应又。這種方法做了如下的事情宙项，和Quick Find一樣：
- 給每一個(gè)節(jié)點(diǎn)初始index；
- 記錄union株扛；
- 查詢聯(lián)通性尤筐；
代碼如下：
public class QuickUnionUF
{
private int[] id;
public QuickUnionUF(int N)
{
id = new int[N];
for (int i = 0; i < N; i++) id[i] = i;
}
private int root(int i)
{
while (i != id[i]) i = id[i];
return i;
}
public boolean connected(int p, int q)
{
return root(p) == root(q);
}
public void union(int p, int q)
{
int i = root(p);
int j = root(q);
id[i] = j;
}
}
給每一個(gè)節(jié)點(diǎn)初始index；
用到的是constructor中的for循環(huán)洞就，即：
for (int i = 0; i < N; i++)
id[i] = i;
很明顯盆繁，這里訪問了index對象N次。
記錄union
如下旬蟋，可以發(fā)現(xiàn)每一次union操作油昂，都涉及到一個(gè)root方法
private int root(int i)
{
while (i != id[i]) i = id[i];
return i;
}
public void union(int p, int q)
{
int i = root(p);
int j = root(q);
id[i] = j;
}
首先看看root這個(gè)方法，它用來查詢一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)。那么這個(gè)查詢需要的計(jì)算量冕碟，取決于節(jié)點(diǎn)所在組的樹的深度拦惋。比如0節(jié)點(diǎn)所在的組，深度為6鸣哀，那么前面的計(jì)算步驟union(0, 5)架忌，需要的計(jì)算量如下：
// root(0)
// i = 0
while (0 != id[0] = 1) i = 1;
while (1 != id[1] = 2) i = 2;
while (2 = id[2] = 2)
return 2
// root(5)
// i = 5
while (5 = id[5] = 5)
return 5
// id[0] = 5
可以發(fā)現(xiàn)，計(jì)算量 = 3(當(dāng)前tree深度) + 1(當(dāng)前tree深度) + 1 = 5
考慮到樹的深度有可能為N我衬，比較Quick Find和Quick Union叹放，那么出現(xiàn)了如下的復(fù)雜度局面。
那也就是說挠羔，考慮到N次的union操作井仰，Quick Union也需要N2的計(jì)算復(fù)雜度，依舊是個(gè)不好的方法破加，Quick Find無法規(guī)木愣瘢化的問題依舊存在。
