quick-find乖订、quick-union均函、加權(quán)quick-union(附帶路徑壓縮優(yōu)化)
本算法主要解決動(dòng)態(tài)連通性一類(lèi)問(wèn)題衡创，這里盡量用精煉簡(jiǎn)潔的話來(lái)闡述运悲。
數(shù)據(jù)結(jié)構(gòu)描述:
- 有N個(gè)節(jié)點(diǎn)（索引0~N-1），可以查詢(xún)節(jié)點(diǎn)數(shù)量
- 可以連接兩個(gè)節(jié)點(diǎn)
- 可以查詢(xún)兩個(gè)節(jié)點(diǎn)是否連通
算法大致設(shè)計(jì)思路：
- 每個(gè)節(jié)點(diǎn)初始化為不同的整數(shù)標(biāo)記
- 通過(guò)一個(gè)輔助函數(shù)查詢(xún)某個(gè)節(jié)點(diǎn)的標(biāo)記值
- 如果兩節(jié)點(diǎn)標(biāo)記相同似忧，說(shuō)明兩節(jié)點(diǎn)是連通的
抽象基類(lèi)：
package com.roc.algorithms.unionfind;
/**
* Union-Find算法的基類(lèi)
* @author roc
*/
public abstract class UnionFind {
protected int[] id;
protected int count;
public UnionFind(int n){
this.count = n;
this.id = new int[n];
for (int i=0;i<n;i++){
this.id[i] = i;
}
}
public int getCount(){
return this.count;
}
public abstract boolean isConnected(int p,int q);
public abstract void union(int p,int q);
}
QuickFind
- a和b進(jìn)行union的時(shí)候渣叛，將b及與b連通節(jié)點(diǎn)的標(biāo)記都置為和a的標(biāo)記一樣
- 標(biāo)記相同的節(jié)點(diǎn)是連通的
package com.roc.algorithms.unionfind;
/**
* union-find算法的quick-find實(shí)現(xiàn)版本
*
* @author roc
*/
public class QuickFind extends UnionFind {
public QuickFind(int n) {
super(n);
}
@Override
public boolean isConnected(int p, int q) {
return id[p] == id[q];
}
@Override
public void union(int p, int q) {
int i = id[p];
int j = id[q];
if (i == j) {
return;
}
for (int k = 0; k < id.length; k++) {
if (id[k] == j) {
id[k] = i;
}
}
count--;
}
}
QuickUnion
- 連通的節(jié)點(diǎn)形成一棵樹(shù)，根節(jié)點(diǎn)相同
package com.roc.algorithms.unionfind;
/**
* union-find算法的quick-union實(shí)現(xiàn)版本
* @author roc
*/
public class QuickUnion extends UnionFind {
public QuickUnion(int n) {
super(n);
}
private int findRoot(int p) {
while (p != id[p]) {
p = id[p];
}
return p;
}
@Override
public boolean isConnected(int p, int q) {
return findRoot(p) == findRoot(q);
}
@Override
public void union(int p, int q) {
int i = findRoot(p);
int j = findRoot(q);
if (i == j) {
return;
}
id[j] = id[i];
count--;
}
}
加權(quán)QuickUnion(附帶路徑壓縮優(yōu)化)
- union的時(shí)候小樹(shù)掛在大樹(shù)下
- 查詢(xún)根節(jié)點(diǎn)的時(shí)候順便將該節(jié)點(diǎn)的父節(jié)點(diǎn)直接指向根節(jié)點(diǎn)盯捌，壓縮路徑
package com.roc.algorithms.unionfind;
/**
* union-find算法的加權(quán)quick-union實(shí)現(xiàn)版本淳衙，
* 附帶路徑壓縮優(yōu)化
*
* @author roc
*/
public class WeightedQuickUnion extends QuickUnion {
private int[] sz;
public WeightedQuickUnion(int n) {
super(n);
this.sz = new int[n];
for (int i = 0; i < n; i++) {
this.sz[i] = 1;
}
}
////查詢(xún)根節(jié)點(diǎn)，順便壓縮路徑
@Override
protected int findRoot(int p) {
while (p != id[p]) {
id[p] = id[id[p]];
p = id[p];
}
return p;
}
@Override
public void union(int p, int q) {
int i = findRoot(p);
int j = findRoot(q);
if (i == j) {
return;
}
if (sz[i] < sz[j]) {
id[i] = j;
sz[j] += sz[i];
} else {
id[j] = i;
sz[i] += sz[j];
}
count--;
}
}
