动态联通 Union-Find
- 上篇文章解决裂变没什么问题，因为每次都算一棵树。算法复杂度不会太高。
- 解决动态联通问题有以下问题
- 每次都循环遍历至少N-1次
- 总体复杂度N2 (N-3)(N-1)~N2
Union-Find
实现步骤
- merge树之前，让其每次找到自己的跟节点。
- 根据while不断的循环数组，这个技巧是解决所有用数组表示树的算法。
- 找到根节点后，用父亲节点替代子节点实现新的层次关系。
- 用此算法只能作为QF的互补，要想真正解决，还需要加权，下一篇会介绍
//动态联通算法
public class QuickUnion {
//数据结构
private int count;
private int[] parent;
public int size() {
return parent.length;
}
public int[] getUf() {
return parent;
}
//行为抽象
//初始化N个节点
public QuickUnion(int N) {
//初始分量数组，N只是模拟1到N的对象，如果用现实中的代替，就是【ID】=地址这种模式。
parent = new int[N];
for (int i = 0; i < N; i++) {
parent[i] = i;
}
count = N;
}
//
private int find(int p) {
//找出分量的标记
validate(p);
//if不可以 在单线程中他妈的也不一样
while (p != parent[p]) {
//假如输入的是4 当前序列 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
//那么算法复杂度为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节点
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) {
//找到各自的根节点
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() {
//略
}
加权UF
上述随机的大树与小树合并，小树合并大树会带来高度猛增，算法复杂度最高会到N2
java
//动态联通算法
public class QuickUnion {
//数据结构
private int count;
private int[] parent;
//
private int[] sz;
public int size() {
return parent.length;
}
public int[] getUf() {
return parent;
}
//行为抽象
//初始化N个节点
public QuickUnion(int N) {
//初始分量数组，N只是模拟1到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) {
//找出分量的标记
validate(p);
//if不可以 在单线程中他妈的也不一样
while (p != parent[p]) {
//假如输入的是4那么当前序列 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
//那么算法复杂度为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 //联通分量
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节点
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] {
//小的的根节点都替换成大的 pr是大树
qu.sz[q] = pr
//只需要更新大树的链接分量，因为小树通过向上爬查询，也会得到大树一样的Root。
qu.sz[p] += qu.sz[q]
} else {
qu.sz[p] = qr
qu.sz[q] += qu.sz[p]
}
}
实际应用
- 数组太大，不利于大规模数据。
- 小规模百万级别，需要把对象ID进行排序。
- 很难修改成堆结构（堆可以节省空间，并行处理。）
