動態(tài)聯(lián)通 Union-Find
- 上篇文章解決裂變沒什么問題，因為每次都算一棵樹瘦麸。算法復(fù)雜度不會太高歧胁。
- 解決動態(tài)聯(lián)通問題有以下問題
- 每次都循環(huán)遍歷至少N-1次
- 總體復(fù)雜度N2 (N-3)(N-1)~N2
Union-Find
實現(xiàn)步驟
- merge樹之前，讓其每次找到自己的跟節(jié)點(diǎn)喊巍。
- 根據(jù)while不斷的循環(huán)數(shù)組，這個技巧是解決所有用數(shù)組表示樹的算法呵曹。
- 找到根節(jié)點(diǎn)后，用父親節(jié)點(diǎn)替代子節(jié)點(diǎn)實現(xiàn)新的層次關(guān)系奄喂。
- 用此算法只能作為QF的互補(bǔ)海洼，要想真正解決跨新，還需要加權(quán)坏逢，下一篇會介紹
//動態(tài)聯(lián)通算法
public class QuickUnion {
//數(shù)據(jù)結(jié)構(gòu)
private int count;
private int[] parent;
public int size() {
return parent.length;
}
public int[] getUf() {
return parent;
}
//行為抽象
//初始化N個節(jié)點(diǎn)
public QuickUnion(int N) {
//初始分量數(shù)組，N只是模擬1到N的對象肖揣，如果用現(xiàn)實中的代替浮入，就是【ID】=地址這種模式龙优。
parent = new int[N];
for (int i = 0; i < N; i++) {
parent[i] = i;
}
count = N;
}
//
private int find(int p) {
//找出分量的標(biāo)記
validate(p);
//if不可以 在單線程中他媽的也不一樣
while (p != parent[p]) {
//假如輸入的是4 當(dāng)前序列 0舵盈，1球化，2瓦糟，8筒愚，3菩浙，5，6陆淀，7，8轧苫，9 存在
//第一次循環(huán) parent[4]=3 那么 p=3
//第二次循環(huán) p=3 parent[3]=8 那么 p=8
//第三次循環(huán) p=8 parent[8]=8 bingo! 找到root
//那么算法復(fù)雜度為0（N）
p = parent[p];
}
return p;
}
//
private void validate(int p) {
int n = parent.length;
if (p < 0 || p >= n) {
throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n - 1));
}
}
public void union(int son, int father) {
int sonroot = find(son);
int parentroot = find(father);
if (parentroot == sonroot)
return;
parent[sonroot] = parentroot;
count--;
}
public static void main(String[] args) {
QuickUnion quickUnion = new QuickUnion(10);
quickUnion.union(4, 3);
quickUnion.union(3, 8);
quickUnion.union(9, 4);
quickUnion.union(4, 3);
// quickUnion.union(2, 1);
// quickUnion.union(6, 5);
// //不在改變
// quickUnion.union(8, 9);
// quickUnion.union(5, 0);
// quickUnion.union(7, 2);
// quickUnion.union(6, 1);
// //不在改變
// quickUnion.union(1, 0);
// quickUnion.union(6, 7);
//
System.out.println(quickUnion.count);
}
}
GO版本
package main
import (
"fmt"
)
type QU struct {
Parent []int
Count int
}
func (qu QU) validate(p int) {
if p < 0 || p > len(qu.Parent) {
panic(fmt.Errorf("index %d is not between 0 and %d", p, len(qu.Parent)-1))
}
}
//找到Root節(jié)點(diǎn)
func (qu QU) findRoot(p int) int {
qu.validate(p)
for qu.Parent[p] != p {
p = qu.Parent[p]
}
return p
}
//鏈接不同的樹
func (qu *QU) union(son, father int) {
//找到各自的根節(jié)點(diǎn)
sr := qu.findRoot(son)
fr := qu.findRoot(father)
if sr != fr {
qu.Count--
//son is replaced father
qu.Parent[sr] = fr
}
}
func Init() {
//略
}
//
func main() {
//略
}
加權(quán)UF
上述隨機(jī)的大樹與小樹合并含懊，小樹合并大樹會帶來高度猛增，算法復(fù)雜度最高會到N2
java
//動態(tài)聯(lián)通算法
public class QuickUnion {
//數(shù)據(jù)結(jié)構(gòu)
private int count;
private int[] parent;
//
private int[] sz;
public int size() {
return parent.length;
}
public int[] getUf() {
return parent;
}
//行為抽象
//初始化N個節(jié)點(diǎn)
public QuickUnion(int N) {
//初始分量數(shù)組岔乔，N只是模擬1到N的對象滚躯，如果用現(xiàn)實中的代替，就是【ID】=地址這種模式掸掏。
parent = new int[N];
for (int i = 0; i < N; i++) {
parent[i] = i;
}
//
sz = new int[N];
for (int i = 0; i < N; i++) {
sz[i] = 1;
}
count = N;
}
//
private int find(int p) {
//找出分量的標(biāo)記
validate(p);
//if不可以 在單線程中他媽的也不一樣
while (p != parent[p]) {
//假如輸入的是4那么當(dāng)前序列 0，1阅束，2，8息裸，3，5呼盆，6年扩，7，8访圃，9
//第一次 parent[4]=3 那么 p=3
//第二次 p=3 parent[3]=8 那么 p=8
//第三次 p=8 parent[8]=8 bingo! 找到root
//那么算法復(fù)雜度為0（N）
p = parent[p];
}
return p;
}
//
private void validate(int p) {
int n = parent.length;
if (p < 0 || p >= n) {
throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n - 1));
}
}
public void union(int p, int q) {
int i = find(p);
int j = find(q);
if (i == j)
return;
if (sz[p] < sz[q]) {
parent[p] = j;
//只需要更新大樹的鏈接分量厨幻，因為小樹通過向上爬查詢矛市，也會得到大樹一樣的Root悟衩。
sz[q] += sz[p];
} else {
parent[q] = i;
sz[p] += sz[q];
}
count--;
}
public static void main(String[] args) {
QuickUnion quickUnion = new QuickUnion(10);
quickUnion.union(4, 3);
quickUnion.union(3, 8);
quickUnion.union(9, 4);
quickUnion.union(4, 3);
// quickUnion.union(2, 1);
// quickUnion.union(6, 5);
// //不在改變
// quickUnion.union(8, 9);
// quickUnion.union(5, 0);
// quickUnion.union(7, 2);
// quickUnion.union(6, 1);
// //不在改變
// quickUnion.union(1, 0);
// quickUnion.union(6, 7);
//
System.out.println(quickUnion.count);
}
}
Go
package main
import "fmt"
type WeightedQuickUnion struct {
WU []int
sz []int //聯(lián)通分量
Count int
}
func (w *WeightedQuickUnion) Init(n int) {
w.Count = 0
w.sz = make([]int, n)
//初始化分量都是1
for i, _ := range w.sz {
w.sz[i] = 1
}
w.WU = make([]int, n)
for i, _ := range w.WU {
w.WU[i] = i
}
}
func (qu WeightedQuickUnion) validate(p int) {
if p < 0 || p > len(qu.WU) {
panic(fmt.Errorf("index %d is not between 0 and %d", p, len(qu.WU)-1))
}
}
//找到Root節(jié)點(diǎn)
func (qu WeightedQuickUnion) findRoot(p int) int {
qu.validate(p)
for qu.WU[p] != p {
p = qu.WU[p]
}
return p
}
//鏈接
func (qu *WeightedQuickUnion) Union(p, q int) {
pr := qu.findRoot(p)
qr := qu.findRoot(q)
//大合并小的，這樣樹的高度最小。
if qu.sz[p] >= qu.sz[q] {
//小的的根節(jié)點(diǎn)都替換成大的 pr是大樹
qu.sz[q] = pr
//只需要更新大樹的鏈接分量务嫡，因為小樹通過向上爬查詢赡艰，也會得到大樹一樣的Root挤巡。
qu.sz[p] += qu.sz[q]
} else {
qu.sz[p] = qr
qu.sz[q] += qu.sz[p]
}
}
實際應(yīng)用
- 數(shù)組太大，不利于大規(guī)模數(shù)據(jù)盛末。
- 小規(guī)模百萬級別弹惦，需要把對象ID進(jìn)行排序。
- 很難修改成堆結(jié)構(gòu)（堆可以節(jié)省空間悄但，并行處理棠隐。）
