数据结构与算法之并查集
需求分析
假设有n个村庄，有些村庄之间有连接的路，有些村庄之间并没有连接的路
image.png
如上图：我们很容易发现1，2，3，4，5，0之间有连接路，而1和6，7之间没有连接的路.
需求：
现在要求设计一个数据结构，能够执行两个操作:
- 1、查询两个村庄之间有没有连接的路
- 2、连接两个村庄
这里我们用并查集去解决这类“连接"的相关问题
并查集
定义
并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题.
并查集有两个核心操作
- 查找(Find)：查找元素所在的集合
- 合并(Union)：将两个元素所在的集合合并成一个集合
有两种常见的实现思路
- Quick Find
查找的时间复杂度是O(1)
合并的时间复杂度O(n) - Quick Union(推荐)
查找的时间复杂度：O(logn)，可以优化至 O(𝛼(𝑛)) ，α(𝑛) < 5
合并的时间复杂度：O(logn)，可以优化至 O(𝛼(𝑛)) ，α(𝑛) < 5
分析
存储数据
如下图：有三个不相交的村庄（集合）
- 0,1,2是一个集合.并且0是1和2的根节点
- 3是一个集合，3的根节点是自己
- 4，5，6，7是一个集合
图1.png
我们可以用数组来存储这些数据，那用数组怎么存储呢？
- 1、首先定义一个数组的集合(该集合是用来存储他们的根节点)，数组的索引便是我们的值，并让他们初始化让他们各自指向自己
private int[] parents;
public UnionFind(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("capcaity must be >=1");
}
parents = new int[capacity];
for (int i = 0; i < parents.length; i++) {
parents[i] = i;
}
}
结果如下图
图2.png
-
2、初始化完之后，我们在find和union中将相应的索引的值(根节点)换成对应的值，比如上面图1，存储之后的数据对应的是如下图(现在只是一个举例,以quick find为例，不同情况代码不一样，结果不一样，后面会分析)
图3.png
-
3、根据上面第2步，其实我们可以知道，两个数据在不在一个集合可以判断他们的根节点是不是一样,如果一样则表示是同一个集合
/**
* 检查v1、v2是否属于同一个集合
*/
public boolean isSame(int v1, int v2) {
return find(v1) == find(v2);
}
- 4、方法定义： find便是找根节点，union便是合并两个数组，因此，我们定义出一个基本的抽象类
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所属的集合（根节点）
*/
public abstract int find(int v);
/**
* 合并v1、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
刚才在上面我们分析了，我们在初始化之后会生成图一的结果(因为太多，所以只截取一部分)。
image.png
接下来，我们分析Quick Find的union
union(v1,v2)
让v1所在集合的所有元素都指向v2的根节点
-
union(1,0)：将1所在集合所有元素全部指向0的根节点，结果如下
image.png
-
union(1,2):将1所在集合的所有元素全部指向2的根节点。所以我们需要将刚刚变化的集合0也指向2。结果如下
image.png
-
依次轮推：union(3,4)
image.png
-
union(0,3) 0所在集合的所有元素指向3的根节点4
image.png
/**
* 将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;
}
}
}
上面我们可以分析出它的时间复杂度是O(n)
find
我们之前设计方法的时候便知道，这个find的作用是找到该元素的根节点，那么很容易知道，因为我们的索引是我们的值，那么数组中索引对应的值便是我们的跟节点
@Override
public int find(int v) {
rangeCheck(v);
return parents[v];
}
很容易发现，时间复杂度是O(1)
实现的思路二：Quick Union
union(v1, v2)
让 v1 的根节点指向 v2 的根节点
-
union(1,0)
image.png
-
union(1,2)
image.png
-
union(3,4)
image.png
-
union(3,1)
image.png
@Override
public void union(int v1, int v2) {
int p1 = find(v1);
int p2 = find(v2);
if (p1 == p2) return;
parents[p1]=p2;
}
时间复杂度：O(logn)
find
因为我们find是找到根节点
image.png
那我们可以很清楚知道，find(0)=find(1)=find(3)=find(4)=2
@Override
public int find(int v) {
rangeCheck(v);
while (v != parents[v]) {
v = parents[v];
}
return v;
}
基于Quick Union的优化
在上面union的过程中极可能出现以下情况:退化成链表
image.png
常见的优化有两种方案：
1、基于size的优化：元素少的树 嫁接到元素多的树
2、基于rank的优化：矮的树嫁接到高的树
-
基于Size的优化
基于size.png
如上图：union(1,4)我们将元素少的4指向(嫁接)元素多的树1的根节点
image.png
初始化每个元素的大小为1
sizes = new int[capacity];
for (int i = 0; i < sizes.length; i++) {
sizes[i] = 1;
}
在原本Quick Union的代码中 修改union代码
@Override
public void union(int v1, int v2) {
int p1 = find(v1);//1
int p2 = find(v2);//4
if (p1 == p2) return;
if (sizes[p1] < sizes[p2]) {
parents[p1] = p2;
sizes[p2] += sizes[p1];
}else{
parents[p2] = p1;
sizes[p1] += sizes[p2];
}
}
分析:当前4所在集合的大小是小于1元素所在集合的个数，所以4指向了1的根节点2，当前元素1所在集合的大小要加上你新嫁接结合的个数
我们会发现，基于size的优化也可能出现树极度不平衡，比如下图
image.png
union(2,6)结果如下
image.png
基于rank的优化
矮的树嫁接到高的树
image.png
基于rank优化之后union(2,6)结果如图
image.png
初始化每个高度为1
ranks = new int[capacity];
for (int i = 0; i < ranks.length; i++) {
ranks[i] = 1;
}
修改Quick Union中的union代码
@Override
public void union(int v1, int v2) {
int p1 = find(v1);
int p2 = find(v2);
if (p1 == p2) return;
if (ranks[p1] < ranks[p2]) {
parents[p1] = p2;
}else if (ranks[p1] > ranks[p2]) {
parents[p2] = p1;
}else{
parents[p1] = p2;
ranks[p2]++;
}
}
image.png
union(7,3):因为两个树的高度一样，所以谁嫁接给谁都可以
image.png
我们会发现树的高度右3变成了4
路径压缩
虽然基于rank进行了优化，树的高度会相对平衡一些，但是当树的高度越来越高，我们会发现find操作会变慢，尤其是底层节点，所以我们需要在刚才rank优化之后再对find进行优化
- 定义
在find的时候使路径的所有节点都指向根节点，从而降低树的高度
image.png
find(3)：将3所有节点指向根节点
image.png
find(7)的结果
image.png
@Override
public int find(int v) {
rangeCheck(v);
if (parents[v] != v) {
parents[v] = find(parents[v]);
}
return parents[v];
}
路径分裂和路径减半
我们会发现路径分裂的成本比较高，因为所有的节点都指向了根节点
优化的方案有两种： 路径分裂和路径减半。它们不仅能降低树高，实现成本也比路径压缩低.两者效率差不多
-
路径分裂
使每个节点都指向其祖父节点
image.png
如上图，1指向的祖父3，2指向它的祖父4，3指向祖父5，4指向祖父也就是5的父5
@Override
public int find(int v) {
rangeCheck(v);
while (parents[v] != v) {
int p = parents[v];
parents[v] = parents[parents[v]];
v = p;
}
return v;
}
-
路径减半
使路径上每隔一个节点就指向其祖父节点
image.png
@Override
public int find(int v) {
rangeCheck(v);
while (parents[v] != v) {
parents[v] = parents[parents[v]];
v = parents[v];
}
return v;
}
自定义对象的并查集
public class UnionFind<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;
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;
Node(V value) {
this.value = value;
}
}
}
