封面画师:Nengoro(ネんごろぅ)     封面ID:73408895

本文参考视频:小马哥教育(SEEMYGO) 2019年 恋上数据结构与算法(第二季)

源码仓库:mofan212/data-structure-and-algorithm (github.com)

辅助学习网址:数据结构和算法动态可视化     Data Structure Visualizations

0. 需求分析

假设有 n 个村庄,有些村庄之间有连接的路,有些村庄之间并没有连接的路。

并查集需求分析

我们能否设计一种数据结构,能够快速执行 2 个操作:

  • 查询 2 个村庄之间是否有连接的路
  • 连接 2 个村庄

能否使用以前谈及的数据结构,如:数组、链表、平衡二叉树、集合(Set)等来实现呢?

其实是可以的,但是效率可能不是很好。

比如使用数组,我们要判断 2 个村庄之间是否有连接的路时,我们需要对整个村庄集聚区进行遍历,看看判断的两个村庄是否在这个数组中,那么这个时候的时间复杂度是O(n)

链表和数组一样,时间复杂度也是O(n)。因为村庄之间不存在谁大谁小的情况,因此对于平衡二叉树来说,时间复杂度也是O(n)

如果你使用集合(HashSet)来做的时候,将每个村庄聚集区看成一个HashSet,然后查询 2 个村庄之间有没有路时,只需要做 O(1) 级别的查询即可,但是如果每个村庄之间都没有路,相当于一个村庄占据一个HashSet,这个时候就相当于做了 O(n) 级别的查询。

对于以前谈及的数据结构来说,查询的时间复杂度都是 O(n)

连接也是一样,时间复杂度也是 O(n)

使用上面说到的数据结构其实有点大材小用的感觉,因为它们的功能完全不止于此,还有很多强大的功能。对于HashSet来说,其底层实现也很复杂。


那有没有一种数据结构针对这两种需求有较好的效率,也不会出现大材小用的情况呢?

并查集能够办到查询、连接的均摊时间复杂度都是 O(α(n)) ,α(n) < 5 。

并查集非常适合解决这类“连接”相关的问题。

1. 并查集

1.1 基本概念

并查集(Union Find),并查集也叫作不相交集合(Disjoint Set)。

并查集有两个核心操作:

  • 查找(Find):查找元素所在的集合(这里的集合并不是特指Set这种数据结构,是指广义的数据集合)
  • 合并(Union):将两个元素所在的集合合并为一个集合

并查集有两种常见的实现思路:

  • Quick Find

    • 查找(Find)的时间复杂度是O(1)
    • 合并(Union)的时间复杂度是O(n)
  • Quick Union

    • 查找(Find)的时间复杂度是O(logn),可优化至O(α(n)) ,α(n) < 5 。
    • 合并(Union)的时间复杂度是O(logn),可优化至O(α(n)) ,α(n) < 5 。

我们开发中常用 Quick Union。

1.2 数据存储

假设并查集处理的数据类型都是整型,那么可以用整型数组来存储数据。

并查集数据存储方式

在数组中存储的元素就表示一个集合,相同的元素表示位于同一个集合中。

如果使用树形结构来表示,我们将数组中存储的元素作为父节点,每个索引按照对应的元素指向不同的父节点。我们判断数据是否位于同一个集合中,就可以判断它们的根节点是否一样。

不难看出:

  • 0、1、3属于同一个集合
  • 2 单独属于一个集合
  • 4、5、6、7 属于同一个集合

因此,并查集是可以用数组实现的树形结构,以前说过的二叉堆、优先级队列也是可以用数组实现的树形结构。

1.3 接口定义

1
2
3
4
5
6
// 查找v所属的集合(根节点)
int find(int v);
// 合并v1、v2所属的集合
void union(int v1, int v2);
// 检查v1、v2是否属于同一个集合
boolean isSame(int v1, int v2);

根据提供的find()接口,我们可以很容易地编写isSame()的实现:

1
2
3
public boolean isSame(int v1, int v2){
return find(v1) == find(v2);
}

1.4 初始化

初始化时,每个元素各自属于一个单元素集合。如:

并查集初始化

代码实现:

1
2
3
4
5
6
7
8
9
10
11
private int[] parents;
public UnionFind(int capacity){
if (capacity < 0){
throw new IllegalArgumentException("Capacity must >= 1.");
}
parents = new int[capacity];

for (int i = 0; i < parents.length; i++){
parents[i] = i;
}
}

1.5 Quick Find

对于合并方法union(int v1, int v2),我们合并时是让 v1 所在集合的所有元素都指向 v2 的根节点以达到合并的效果。

QuickFind-Union-1 QuickFind-Union-2

利用这种合并方法,我们可以发现构造出的树形结构“很平”,只有两层,同时数组内存储的值就是对应节点的根节点。

那么查找根节点find()接口可以这么实现:

1
2
3
4
public int find(int v){
rangeCheck(v);
return parents[v];
}

find(0) == 2

find(1) == 2

find(3) == 3

查找时间复杂度: O(1)

代码实现:

1
2
3
4
5
6
7
8
9
10
11
public void union(int v1, int v2){
int p1 = find(v1);
int p2 = find(v2);
if (p1 == p2) return;

for (int i = 0; i < parents.length; i++){
if (parents[i] == p1){
parents[i] = p2;
}
}
}

合并时间复杂度: O(n)

编码实现

编写一个父类UnionFind,并将其定义为抽象类,这样可以让不同实现的并查集继承这个父类。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
package com.yang.union;

/**
* @author 默烦
* @date 2020/8/18
*/
public abstract class UnionFind {
protected int[] parents;

// 初始化
public UnionFind(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("capacity must be >= 1.");
}

parents = new int[capacity];
for (int i = 0; i < parents.length; i++) {
parents[i] = i;
}
}

/**
* 查找 v 所属的集合(根节点)
*
* @param v 查找节点
* @return 所属集合
*/
public abstract int find(int v);

/**
* 合并 v1、v2 所在的集合
* @param v1
* @param v2
*/
public abstract void union(int v1, int v2);

/**
* 检查 v1、v2是否属于同一个集合
*/
public boolean isSame(int v1, int v2) {
return find(v1) == find(v2);
}

protected void rangeCheck(int v) {
if (v < 0 || v >= parents.length) {
throw new IllegalArgumentException("v is out of bounds");
}
}
}

编写 Quick Find 的实现方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package com.yang.union;

/**
* @author 默烦
* @date 2020/8/18
*/
public class UnionFind_QF extends UnionFind {
public UnionFind_QF(int capacity) {
super(capacity);
}

/**
* 父节点就是根节点
*/
@Override
public int find(int v) {
rangeCheck(v);
return parents[v];
}

/**
* 将 v1 所在集合所有元素都嫁接到 v2 的父节点上
*/
@Override
public void union(int v1, int v2) {
int p1 = find(v1);
int p2 = find(v2);
if (p1 == p2) return;

for (int i = 0; i < parents.length; i++){
if (parents[i] == p1){
parents[i] = p2;
}
}
}
}

编写测试代码进行测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void main(String[] args) {
UnionFind uf = new UnionFind_QF(12);
uf.union(0, 1);
uf.union(0, 3);
uf.union(0, 4);
uf.union(2, 3);
uf.union(2, 5);

uf.union(6, 7);

uf.union(8, 10);
uf.union(9, 10);
uf.union(9, 11);


System.out.println(uf.isSame(0, 6));
System.out.println(uf.isSame(0, 5));
System.out.println(uf.isSame(2, 7));
uf.union(4, 6);
System.out.println(uf.isSame(2, 7));
}

测试结果为:

QuickFind测试结果

1.6 Quick Union

Union

对于合并方法union(int v1, int v2),我们合并时是将v1的根节点指向 v2的根节点以达到合并的效果。

QuickUnion-Union-1 QuickUnion-Union-2

Find

find(int v)的作用是查找v所属的集合(根节点),那么对于下图所示的并查集有:

QuickUnion-Find

find(1) == 2

find(2) == 2

find(4) == 2

时间复杂度: O(logn)

我们发现,一个节点的父节点等于它自身时,那么这个节点就是根节点。

1
2
3
4
5
6
7
public int find(int v) {
rangeCheck(v);
while (v != parents[v]) {
v = parents[v];
}
return v;
}

实现了find()接口后,可以很容易实现union()接口:

1
2
3
4
5
6
7
public void union(int v1, int v2) {
int p1 = find(v1);
int p2 = find(v2);
if (p1 == p2) return;

parents[p1] = p2;
}

时间复杂度为: O(logn)

编码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class UnionFind_QU extends UnionFind {
public UnionFind_QU(int capacity) {
super(capacity);
}

/**
* 通过 parents 链条不断向上找,直到找到根节点
*/
@Override
public int find(int v) {
rangeCheck(v);
while (v != parents[v]) {
v = parents[v];
}
return v;
}

/**
* 将 v1 的根节点嫁接到 v2 的根节点上
*/
@Override
public void union(int v1, int v2) {
int p1 = find(v1);
int p2 = find(v2);
if (p1 == p2) return;

parents[p1] = p2;
}
}

测试代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Main {
public static void main(String[] args) {
UnionFind uf = new UnionFind_QU(12);
uf.union(0, 1);
uf.union(0, 3);
uf.union(0, 4);
uf.union(2, 3);
uf.union(2, 5);

uf.union(6, 7);

uf.union(8, 10);
uf.union(9, 10);
uf.union(9, 11);


System.out.println(uf.isSame(0, 6));
System.out.println(uf.isSame(0, 5));
System.out.println(uf.isSame(2, 7));
uf.union(4, 6);
System.out.println(uf.isSame(2, 7));
}
}

运行测试一下:

QuickUnion测试结果

得到的测试结果与QuickFind一样,也证明了我们的编码没有问题! 🎉🎊

在实际应用中,我们常用 Quick Union,因为 Quick Find 合并的时间复杂度为 O(n) 实在太大,因此选用 Quick Union 作为我们的主要实现,而且 Quick Union 还可以进一步地优化。👇

2. Quick Union优化

2.1 优化方案

在Union的过程中,可能会出现树不平衡的情况,甚至退化成链表,导致效率降低。

如:

QuickUnion树不平衡

针对这个弊端,我们有两种常见的优化方案:

  • 基于size的优化:元素少的树 嫁接到 元素多的树
  • 基于rank的优化: 矮的树 嫁接到 高的树

需要注意一点,元素多少与树的高矮没有直接联系,因此上述两种方式是不同的优化方式。

2.2 基于size的优化

基于size的优化图解:

QuickUnion基于size的优化图解

基于size的优化的方式是: 将元素少的树 嫁接到 元素多的树,就如同上图一样,因此我们需要知道进行合并的两棵树的元素数量,这样才方便比较并嫁接。

在构造函数中令每个集合的数量都为 1 :

1
2
3
4
sizes = new int[capacity];
for (int i = 0; i < sizes.length; i++){
sizes[i] = 1;
}

然后在进行合并时利用树元素的数量进行比较,查看是哪个树嫁接到哪棵树:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@Override
public void union(int v1, int v2) {
int p1 = find(v1);
int p2 = find(v2);
if (p1 == p2) return;

// 以 p1 为根节点的树的元素数量小于 p2 的
if (sizes[p1] < sizes[p2]) {
parents[p1] = p2;
sizes[p2] += sizes[p1];
} else {
parents[p2] = p1;
sizes[p1] += sizes[p2];
}
}

编码实现

编写一个基于 size 的优化的 Quick Union 类,同时这个类可以继承UnionFind_QU,因为只有union()方法发生改变:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* Quick Union - 基于 size 的优化
*
* @author 默烦
* @date 2020/8/19
*/
public class UnionFind_QU_S extends UnionFind_QU {
private int[] sizes;

public UnionFind_QU_S(int capacity) {
super(capacity);
sizes = new int[capacity];
for (int i = 0; i < sizes.length; i++) {
sizes[i] = 1;
}
}

/**
* 将 v1 的根节点嫁接到 v2 的根节点上
*/
@Override
public void union(int v1, int v2) {
int p1 = find(v1);
int p2 = find(v2);
if (p1 == p2) return;

// 以 p1 为根节点的树的元素数量小于 p2 的
if (sizes[p1] < sizes[p2]) {
parents[p1] = p2;
sizes[p2] += sizes[p1];
} else {
parents[p2] = p1;
sizes[p1] += sizes[p2];
}
}
}

统计耗时的测试工具类:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Times {
private static final SimpleDateFormat fmt = new SimpleDateFormat("HH:mm:ss.SSS");

public interface Task {
void execute();
}

public static void test(String title, Task task) {
if (task == null) return;
title = (title == null) ? "" : ("【" + title + "】");
System.out.println(title);
System.out.println("开始:" + fmt.format(new Date()));
long begin = System.currentTimeMillis();
task.execute();
long end = System.currentTimeMillis();
System.out.println("结束:" + fmt.format(new Date()));
double delta = (end - begin) / 1000.0;
System.out.println("耗时:" + delta + "秒");
System.out.println("-------------------------------------");
}
}

断言工具类:

1
2
3
4
5
6
7
8
9
public class Asserts {
public static void test(boolean value) {
try {
if (!value) throw new Exception("测试未通过");
} catch (Exception e) {
e.printStackTrace();
}
}
}

测试使用并查集不同的实现时, 8w 个随机数进行union()isSame()所消耗的时间:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public class Main {
static final int count = 80000;

public static void main(String[] args) {
test(new UnionFind_QF(12));
test(new UnionFind_QU(12));
test(new UnionFind_QU_S(12));
testTime(new UnionFind_QF(count));
testTime(new UnionFind_QU(count));
testTime(new UnionFind_QU_S(count));
}

static void test(UnionFind uf) {
uf.union(0, 1);
uf.union(0, 3);
uf.union(0, 4);
uf.union(2, 3);
uf.union(2, 5);

uf.union(6, 7);

uf.union(8, 10);
uf.union(9, 10);
uf.union(9, 11);


Asserts.test(!uf.isSame(0, 6));
Asserts.test(uf.isSame(0, 5));
Asserts.test(!uf.isSame(2, 7));
uf.union(4, 6);
Asserts.test(uf.isSame(2, 7));
}

static void testTime(UnionFind uf) {
Times.test(uf.getClass().getSimpleName(), () -> {
for (int i = 0; i < count; i++) {
uf.union((int) (Math.random() * count),
(int) (Math.random() * count));
}
for (int i = 0; i < count; i++) {
uf.isSame((int) (Math.random() * count),
(int) (Math.random() * count));
}
});
}
}

测试结果截图:

QuickUnion基于size优化测试结果

我们发现控制台没有打印出异常信息,证明我们的优化没有错误。

同时还能发现,就合并而言,Quick Union的耗时 > Quick Find 的耗时 > 优化后Quick Union的耗时,这也证明了我们的优化是有作用的。

补充拓展

虽然进行基于size的优化后,性能得到了明显的提升,但是依然可能会出现树不平衡的问题。

比如原本两棵树是这样的:

QuickUnion基于size优化不足-1

然后经过union(1, 3)就可能会出现:

QuickUnion基于size优化不足-2

这样的树依旧是不平衡的。

针对这种情况,我们可以选择用另外一种优化方式—— 基于rank的优化 。 😉

2.3 基于rank的优化

这里的rank指的是树的高度,因此基于rank的优化就是将矮的树嫁接到高的树上。

比如:

QuickUnion基于rank的优化图解

为了比较两棵树的高度,我们需要一个变量来存储树的高度,我们可以使用一个数组来进行存储。

树的高度初始化如下:

1
2
3
4
ranks = new int[capacity];
for (int i = 0; i < ranks.length; i++) {
ranks[i] = 1;
}

编码实现

编写一个基于 rank 的优化的 Quick Union 类,同时这个类可以继承UnionFind_QU,因为只有union()方法发生改变:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
* Quick Union - 基于 rank 的优化
* @author 默烦
* @date 2020/8/19
*/
public class UnionFind_QU_R extends UnionFind_QU {
private int[] ranks;

public UnionFind_QU_R(int capacity) {
super(capacity);

ranks = new int[capacity];
for (int i = 0; i < ranks.length; i++) {
ranks[i] = 1;
}
}

public void union(int v1, int v2) {
int p1 = find(v1);
int p2 = find(v2);
if (p1 == p2) return;

// 以 p1 为根节点的树的高度小于 p2 的
if (ranks[p1] < ranks[p2]) {
parents[p1] = p2;
} else if (ranks[p1] > ranks[p2]){
parents[p2] = p1;
} else {
parents[p1] = p2;
ranks[p2] += 1;
}
}
}

编写完之后,我们可以测试一手,测试代码基本不变,只在main()方法中添加测试方法即可:

1
2
3
4
5
6
7
8
9
static final int count = 500000;
public static void main(String[] args) {
test(new UnionFind_QF(12));
test(new UnionFind_QU(12));
test(new UnionFind_QU_S(12));
test(new UnionFind_QU_R(12));
testTime(new UnionFind_QU_S(count));
testTime(new UnionFind_QU_R(count));
}

测试的数据规模增大,测试 50w 个随机数进行union()isSame()所消耗的时间,测试截图如下:

QuickUnion基于rank优化测试结果

控制台没有打印出异常信息,证明我们的优化没有错误。

还发现基于rank的优化耗时与基于size的优化耗时差不多,甚至前者的耗时要少一些,这证明了我们的优化是有作用的。

相比于基于size的优化,基于rank的优化会让树的高度相对平衡,因此我们选择优化时, 常选用基于rank的优化进行优化。

2.4 路径压缩

Quick Union基于rank的优化演示:

QuickUnion基于rank的优化演示

虽然有了基于rank的优化,树会相对平衡一点,但是随着 Union 次数的增多 ,树的高度依然会越来越高, 导致 find 操作变慢 ,尤其是底层节点(因为 find 是不断向上寻找根节点的)。

路径压缩(Path Compression):在 find 时使路径上的所有节点都指向根节点,从而降低树的高度。比如:

路径压缩结果

编码实现

编写一个基于 size 的优化且使用了路径压缩的 Quick Union 类,同时这个类可以继承UnionFind_QU_R,代码中只有find()方法发生改变:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* Quick Union - 基于 rank 的优化 - 路径压缩 (Path Compression)
* @author 默烦
* @date 2020/8/19
*/
public class UnionFind_QU_R_PC extends UnionFind_QU_R{
public UnionFind_QU_R_PC(int capacity) {
super(capacity);
}

@Override
public int find(int v) {
rangeCheck(v);

if (parents[v] != v) {
// 从 v 到根节点路径上所有节点的父节点都指向根节点
parents[v] = find(parents[v]);
}
return parents[v];
}
}

测试的数据规模增大,测试 100w 个随机数进行union()isSame()所消耗的时间,测试截图如下:

路径压缩测试对比

从测试结果中可以看出进行路径压缩后耗时得到了减少,但是减少的耗时不是很明显。这是因为我们在进行路径压缩时使用了递归调用,使路径上的所有节点都指向了根节点,所以实现成本较高。

还有两种更优的做法,不但可以降低树高,实现成本也比路径压缩低:

  • 路径分裂(Path Splitting)
  • 路径减半(Path Halving)

路径分裂、路径减半的效果差不多,但都比路径压缩要好。😏

2.5 路径分裂

路径分裂(Path Splitting):使路径上的每个节点都指向其祖父节点(parent的parent)。

路径分裂演示

我们发现进行路径分裂后的树的高度确实降低了,但是没有路径压缩那么“离谱”,并不是将所有元素都平铺开来,因此路径分裂的成本没有路径压缩的成本高。

编码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* Quick Union - 基于 rank 的优化 - 路径分裂 (Path Splitting)
* @author 默烦
* @date 2020/8/19
*/
public class UnionFind_QU_R_PS extends UnionFind_QU_R{
public UnionFind_QU_R_PS(int capacity) {
super(capacity);
}

@Override
public int find(int v) {
rangeCheck(v);
while (v != parents[v]) {
int p = parents[v];
parents[v] = parents[parents[v]];
v = p;
}
return v;
}
}

测试的数据规模增大,测试 200w 个随机数进行union()isSame()所消耗的时间,测试截图如下:

路径分裂测试对比

根据测试结果可以发现,相比于路径压缩,路径分裂的耗时又进一步减少了,这也证明了路径分裂的成本没有路径压缩的成本高。

2.6 路径减半

路径减半(Path Halving):使路径上每隔一个节点就指向其祖父节点(parent的parent)。

路径减半演示

从上图可以看出,路径减半和路径分裂类似,进行这两种优化后得到的树的高度是一样的。

编码测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* Quick Union - 基于 rank 的优化 - 路径减半 (Path Halving)
* @author 默烦
* @date 2020/8/19
*/
public class UnionFind_QU_R_PH extends UnionFind_QU_R {
public UnionFind_QU_R_PH(int capacity) {
super(capacity);
}

@Override
public int find(int v) {
rangeCheck(v);
while (v != parents[v]) {
parents[v] = parents[parents[v]];
v = parents[v];
}
return v;
}
}

测试的数据规模减小,测试 100w 个随机数进行union()isSame()所消耗的时间,测试截图如下:

路径减半测试对比

从测试结果可以看出路径分裂和路径减半的耗时差不多,但相比于路径压缩是更优的。

因此我们在进行优化时,可以选择路径分裂和路径减半进行优化,而不是路径压缩。

2.7 总结

摘自《维基百科》: Disjoint-set data structure

并查集wiki

大概就是说:

使用路径压缩、分裂或减半 + 基于 rank 或者 size 的优化

可以确保每个操作的均摊时间复杂度为 O(α(n)) ,α(n) < 5

建议的搭配

  • Quick Union
  • 基于 rank 的优化
  • Path Halving 或 Path Splitting

3. 自定义类型

之前的使用都是基于整型数据的,如果其他自定义类型也想使用并查集应该怎么做呢?

3.1 方案一

通过一些方法将自定义类型转为整型后使用并查集(比如生成哈希值),但是需要注意的是,转为整型的过程的效率要高,时间复杂度最好是O(1),如果过程的时间复杂度达到了O(n),那就没必要了。

对于方案一,我们要保证不同的自定义对象生成的整型数据必须是不一样的。因此,方案一就显得比较麻烦。

3.2 方案二

使用链表 + 映射(Map)。

首先需要编写一个节点对象Node,这样数据就可以是任何类型的:

1
2
3
4
5
6
7
8
9
10
// 节点对象
private static class Node<V> {
V value;
Node<V> parent = this; // 指向自己
int rank = 1; // 默认初始高度 1

public Node(V value) {
this.value = value;
}
}

在这里,一个对象和一个节点对象是一一对应的,因此我们可以使用Map来存储节点:

1
private Map<V, Node<V>> nodes = new HashMap<>();

在以前使用基于整型的并查集时,如果想使用union(int v1, int v2)方法是有一个前提的,就是 v1 和 v2 都是被初始化的,如:

1
2
3
4
5
6
7
8
9
10
11
12
13
protected int[] parents;

// 初始化
public UnionFind(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("capacity must be >= 1.");
}

parents = new int[capacity];
for (int i = 0; i < parents.length; i++) {
parents[i] = i;
}
}

因此自定义类型使用并查集时也需要进行初始化,我们可以编写一个方法对数据进行初始化:

1
2
3
4
5
// 自定义对象初始化成集合
public void makeSet(V v) {
if (nodes.containsKey(v)) return;
nodes.put(v, new Node<>(v));
}

初始化完毕后,就可以实现并查集的接口了,比如:find()union()isSame(),完成的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
* @author 默烦
* @date 2020/8/20
*/
public class GenericUnionFind<V> {
private Map<V, Node<V>> nodes = new HashMap<>();

// 自定义对象初始化成集合
public void makeSet(V v) {
if (nodes.containsKey(v)) return;
nodes.put(v, new Node<>(v));
}

/**
* 找到 v 的根节点
*/
private Node<V> findNode(V v) {
Node<V> node = nodes.get(v);
if (node == null) return null;

while (!Objects.equals(node.value, node.parent.value)) {
node.parent = node.parent.parent;
node = node.parent;
}
return node;
}

public V find(V v) {
Node<V> node = findNode(v);
return node == null ? null : node.value;
}

public void union(V v1, V v2) {
Node<V> p1 = findNode(v1);
Node<V> p2 = findNode(v2);
if (p1 == null || p2 == null) return;
if (Objects.equals(p1.value, p2.value)) return;

// 以 p1 为根节点的树的高度小于 p2 的
if (p1.rank < p2.rank) {
p1.parent = p2;
} else if (p1.rank > p2.rank){
p2.parent = p1;
} else {
p1.parent = p2;
p2.rank += 1;
}
}

public boolean isSame(V v1, V v2) {
return Objects.equals(find(v1), find(v2));
}

private static class Node<V> {
V value;
Node<V> parent = this; // 指向自己
int rank = 1; // 默认初始高度 1

public Node(V value) {
this.value = value;
}
}
}

测试

编写一个自定义类型Student

1
2
3
4
5
6
7
8
9
public class Student {
private String name;
private int age;

public Student(String name, int age) {
this.name = name;
this.age = age;
}
}

测试代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static void main(String[] args) {
GenericUnionFind<Student> uf = new GenericUnionFind<>();
Student stu1 = new Student("jack", 1);
Student stu2 = new Student("rose", 2);
Student stu3 = new Student("jack", 3);
Student stu4 = new Student("rose", 4);
uf.makeSet(stu1);
uf.makeSet(stu2);
uf.makeSet(stu3);
uf.makeSet(stu4);

uf.union(stu1, stu2);
uf.union(stu3, stu4);
uf.union(stu1, stu4);

Asserts.test(uf.isSame(stu2, stu3));
Asserts.test(uf.isSame(stu3, stu4));
Asserts.test(!uf.isSame(stu1, stu3));
}

运行后,控制台没有打印出任何异常消息,证明我们编写的代码是正确的。

既然可以使用任何类型的数据,那么使用整型的耗时是多少呢?

测试 100w 个随机数进行union()isSame()所消耗的时间,测试截图如下:

GenericUnionFind测试对比

我们可以发现,GenericUnionFind的耗时是最多的,主要原因是它可以兼容所有类型,而且底层还涉及了HashMap 的使用,基于这两个原因导致GenericUnionFind的耗时最多。

毕竟鱼与熊掌不可兼得,又想支持任何类型,又要效率好过单一的支持,想必是很难做到的。😞