概念及其介绍
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。
并查集的思想是用一个数组表示了整片森林（parent）
- 树的根节点唯一标识了一个集合
- 我们只要找到了某个元素的的树根
- 就能确定它在哪个集合里。
并查集构造方法
public class Union {
int n;
int[] parent;
// size[i] 表示以 i 为根，集合中元素的个数
int[] size;
// rank[i] 表示以 i 为根为集合，所表示的输的层数
int[] rank;
public Union(int n, int[] parent) {
// 表示集合的元素个数
this.n = n;
// 初始化数组
parent = new int[n];
// 填充数组
for (int i = 0; i - 有三个重要概念，分别是 归属集合、集合中元素个数和树的层数
- 归属集合
- 用
parent数组进行表示
- 元素个数
- 用
size数组进行表示
- 树的层数
- 用
rank数组进行表示
- 图例1
- 图例2
- 编号 0 的集合现在只有一个元素就是其本身，层数为 1
- 编号 1 的集合现在有两个元素
{0, 1}，层数为 2
并查集快速查找
- 问题提出：如何查找元素所在的集合编号？
public int find(int val) {
assert val >= 0 && val - 但是这样存在一个问题，如下图
- 如上图示：
-
find(0) = 1: 表示 0 属于 编号为 1 的集合 -
find(1) = 2: 表示 1 属于 编号为 2 的集合 - 然后所有的元素都属于编号为 4 的集合，元素个数为 5，层数为 5
- 所以该种方法无法找到元素最终归属的集合
优化一
查找目标元素所对应的根集合编号
public int find(int val) {
assert val >= 0 && val - 以下图为例
-
val = 0 , parent[val] = 1，不相等-令val = 1 -
val = 1 , parent[val] = 2->val = 2 -
val = 2 , parent[val] = 3->val = 3 -
val = 3 , parent[val] = 4->val = 4 -
val = 4 , parent[val] = 4最终返回4：元素 0 所属的集合编号是 4
优化二
优化一中的例子，需要计算 4 次之后才能够找到元素最终归属的集合编号
- 但是实际上，
{0, 1, 2, 3, 4}都同属于 4号集合
- 如下图，
find(0) = 4可以直接得出结果 - 并且对应 层数 发生了变化 从
5 -> 2
- 期望实现达到的效果是 如下图—> 从左到右 的转换
- 代码实现如下
public int find(int val) {
assert val >= 0 && val 并查集判断两个元素是否相连
public boolean isConnected(int a, int b) {
return find(a) == find(b);
}- 判断两个元素是否相连的方法较为简单
- 直接利用find方法即可
并查集合并
并查集合并的相关代码和find方法的相关代码相关
路径优化
package new_start.classic;
/**
* desc : 并查集--rank优化
*
* create time : 2023/10/14 21:26
*/
public class UnionRankBest {
int n;
int[] parent;
// 记录每一个集合的层数
int[] rank;
public UnionRankBest(int n) {
this.n = n;
parent = new int[n];
rank = new int[n];
for (int i = 0; i = 0 && val rank[rB]) {
// 层数低 的 指向层数 高的，rank 不变
parent[rB] = rA;
} else {
// rank[rA] == rank[rB]
parent[rA] = rB;
rank[rB] += 1;
}
}
}
size优化
package new_start.classic;
/**
* desc : 并查集 size 优化
*
* create time : 2023/10/14 21:39
*/
public class UnionSizeBest {
int n;
int[] parent;
int[] size;
public UnionSizeBest(int n) {
this.n = n;
parent = new int[n];
size = new int[n];
for (int i = 0; i = 0 && v
路径压缩
package new_start.classic;
/**
* desc : 并查集--路径压缩
*
* create time : 2023/10/14 21:26
*/
public class UnionRankCompress {
int n;
int[] parent;
public UnionRankCompress(int n) {
this.n = n;
parent = new int[n];
for (int i = 0; i = 0 && val
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.fwq服务器托管网tg.net
原文链接： Go 语言 context 都能做什么？ 很多 Go 项目的源码，在读的过程中会发现一个很常见的参数 ctx，而且基本都是作为函数的第一个参数。 为什么要这么写呢？这个参数到底有什么用呢？带着这样的疑问，我研究了这个参数背后的故事。 开局一张图： …
