code前端网并查并查算法：什么是动态连接？平衡优化、路径压缩
并查算法又称并查算法，主要解决图论中的“动态连通性”问题。名词很高级，其实也很容易理解。我稍后会解释它们。另外，这个算法的应用也很有趣。
说起并查，应该算是我的“启蒙算法”，因为这个算法是在《算法4》一开始就介绍过的，但是给我留下了深刻的印象，感觉好精妙啊！后来更新了LeetCode，查了相关算法题。他们都很有趣。而且，《算法4》给出的解还可以进一步优化。只要添加一点小小的修改，时间复杂度就可以降低到O(1)。
废话不多说，让我们直接进入实际的内容。首先，我们来解释一下什么是动态连接。
1。问题简介
简单地说，动态连接实际上可以抽象为连接图像。例如下图中，一共有10个节点。它们之间没有联系，分别用0~9来标记：
现在我们的并查算法主要需要实现这两个API：
class UF {
/* 将 p 和 q 连接 */
public void union(int p, int q);
/* 判断 p 和 q 是否连通 */
public boolean connected(int p, int q);
/* 返回图中有多少个连通分量 */
public int count();
}
这里所说的“连通”是一个等价关系，表示它具有以下三个属性：
1. 自反性 ：节点 p 和 p❀ 也已连接。 r 已连接，则p 和 r 也已连接。♿例如任何其他❝图像❝分数从 0 到 9 均不连接。调用 已连接将会返回 false，有 10 个连通分量。
然后调用 union(1, 2)。此时 0、1、2 都连通了。调用 connected(0) ， 2）也会返回true，连通分量也会是8个。
判断这种“等价关系”是非常方便的。比如编译器判断对同一个变量的不同引用，比如社交网络中朋友圈的计算等
这样你应该大概明白什么是动态连接了。并查算法的关键在于函数union和connected的效率。那么用什么模型来表示这个图像的连接状态呢？使用什么数据结构来实现代码？
2. 基本思想
请注意，我只是将“模型”与具体的“数据结构”分开。有一个原因。因为我们用一个森林（多棵树）来表示图的动态连通性，所以我们用一个矩阵来具体实现这个森林。
如何用森林来表示连通性？我们将树中的每个节点设置为有一个指向其父节点的指针。如果是根节点，则该指针指向其自身。
例如，现在的10节点图一开始并没有相互连接，所以它是这样的：
class UF {
// 记录连通分量
private int count;
// 节点 x 的节点是 parent[x]
private int[] parent;
/* 构造函数，n 为图的节点总数 */
public UF(int n) {
// 一开始互不连通
this.count = n;
// 父节点指针初始指向自己
parent = new int[n];
for (int i = 0; i < n; i++)
parent[i] = i;
}
/* 其他函数 */
}
如果两个节点连接，则设（任意）节点的根节点为连接到另一个节点的根节点上的 ：
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ)
return;
// 将两棵树合并为一棵
parent[rootP] = rootQ;
// parent[rootQ] = rootP 也一样
count--; // 两个分量合二为一
}
/* 返回某个节点 x 的根节点 */
private int find(int x) {
// 根节点的 parent[x] == x
while (parent[x] != x)
x = parent[x];
return x;
}
/* 返回当前的连通分量个数 */
public int count() {
return count;
}
。这样，如果节点p和q相连的话，它们一定有相同的根节点：--原则上此时基本上F就完成了。那不是很棒吗？其实可以用数组来模拟一片森林，如此巧妙地解决了这个相对复杂的问题！
那么这个算法的复杂度是多少呢？我们发现主要API 因此，对于上述解决方案， 问题的关键是如何找到避免树不平衡的方法？只需一点点计划就可以了。 我们需要知道什么情况下会出现不平衡。关键在于 我们从简单粗暴的 如果长此以往，树可能会生长得非常不平衡。 我们其实希望小树挂在大树下面，避免头重脚轻，更平衡。解决方案是使用额外的 例如， 这样，通过比较树的权重，就可以保证树的生长是相对均衡的。树的高度大约为 此时 这个优化步骤非常简单，所以非常聪明。我们能否进一步压缩每棵树的高度，使树高保持不变？ 这样， 做到这一点非常简单。只需要为 这个操作有点奇怪。看GIF就可以明白它的功能（为了清晰起见，这些树比较极端）： 可以看到，当你调用 PS：读者可能会问，这个GIF的 我们先看一下完整的代码： 并查算法的复杂度可以分析如下：构造函数初始化数据结构，需要O(N)的时间和空间复杂度；连接 两个节点connected和union的复杂性是由find造成的，它们的功能是 一样。 find的主要功能是从某个节点向上到树的根，时间复杂度就是树的高度。我们可能习惯于认为树的高度是logN，但事实并非一定如此。 logN的高度仅存在于平衡二叉树中。对于一般的树来说，会出现极端的不平衡，导致“树”几乎退化为“链表”。在最坏的情况下，树的高度可能会变成N。 
find、union和连接所有(N)的时间复杂度。这种复杂性并不理想。你想要图论解决的是像社交网络这样的大数据规模问题。拨打union和connected的电话非常频繁。每次调用所需的线性时间是完全无法忍受的。 3。平衡优化
union过程：public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ)
return;
// 将两棵树合并为一棵
parent[rootP] = rootQ;
// parent[rootQ] = rootP 也可以
count--;
p开始连接到树的根节点q所在的树，然后一个“顶这里可能会出现“重”的不平衡，比如下面的情况： 
size 数组来记录每棵树中的节点数量。我们不妨称之为“权重”：class UF {
private int count;
private int[] parent;
// 新增一个数组记录树的“重量”
private int[] size;
public UF(int n) {
this.count = n;
parent = new int[n];
// 最初每棵树只有一个节点
// 重量应该初始化 1
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
/* 其他函数 */
}
表示大小[3] = 5，以节点3为根的树总共有5❀。这样，我们就可以修改union方法：public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ)
return;
// 小树接到大树下面，较平衡
if (size[rootP] > size[rootQ]) {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
} else {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
count--;
}
logN的量级，这极大地提高了执行效率。 find、union、log的时间复杂度连接到♼(N)。虽然数据规模有亿级，但所需的时间也很少。 4。路径压缩
find可以在O(1)时间内找到特定节点的根节点。相应地，connected和union的复杂度也降低了。是 O(1)。 find添加一行代码即可：private int find(int x) {
while (parent[x] != x) {
// 进行路径压缩
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
find函数时，每次都会去到根树，树的高度缩短了。最后所有树的高度都不会超过3（union时树高可以达到3）。 find过程完成后，树的高度正好等于3，但是如果有更高的树，压缩后的高度仍然会更大比 3 ?不能这么想。这个GIF的场景是我为了方便大家理解路径压缩而制作的。但实际上，每次find都会进行路径压缩，所以树不可能长到这么高。您不必担心这一点。是多余的。 5。最后总结
class UF {
// 连通分量个数
private int count;
// 存储一棵树
private int[] parent;
// 记录树的“重量”
private int[] size;
public UF(int n) {
this.count = n;
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ)
return;
// 小树接到大树下面，较平衡
if (size[rootP] > size[rootQ]) {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
} else {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
}
count--;
}
public boolean connected(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
return rootP == rootQ;
}
private int find(int x) {
while (parent[x] != x) {
// 进行路径压缩
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
}
union所需的时间复杂度，通过判断两个节点connected的连接，并计算连接分量number(Onumber)。
版权声明
本文仅代表作者观点，不代表Code前端网立场。
本文系作者Code前端网发表，如需转载，请注明页面地址。
