英文版科技网站,怎样开网店流程视频,社交平台推广,做网站平台的工作嘿#xff0c;朋友们#xff01;喜欢这个并查集的讲解吗 记得点个关注哦#xff0c;让我们一起探索算法的奥秘#xff0c;别忘了一键三连#xff0c;你的支持是我最大的动力#xff01; 欢迎拜访#xff1a;羑悻的小杀马特.-CSDN博客 本篇主题#xff1a;深度剖析并查…嘿朋友们喜欢这个并查集的讲解吗 记得点个关注哦让我们一起探索算法的奥秘别忘了一键三连你的支持是我最大的动力 欢迎拜访羑悻的小杀马特.-CSDN博客 本篇主题深度剖析并查集算法及一系列优化 制作日期2025.01.13 隶属专栏美妙的算法世界 下面我们就介绍一下并查集是啥吧 目录 一·概念
二·数据结构表示 三·基本操作及实现
3.1初始化
3.2查找操作root
3.3 合并操作merge
朴素版 四.优化策略:
4.1路径压缩
4.2按秩合并
4.3按大小合并启发合并
五·优化前后对比
5.1 优化前
5.2优化后 六·例题测试
七.应用场景 7.1网络连通性问题
7.2社交网络中的朋友圈问题:
7.3:图论中的最小生成树算法如 Kruskal 算法:
八·个人小结 一·概念 并查集是一种树型的数据结构用于处理不相交集合的合并及查询问题。它主要支持两种操作“并”Union操作即将两个不相交的集合合并为一个集合“查”Find操作即查找元素所在的集合大概它的外形也可以理解为多插树的形式。 并查集在解决元素分组和动态连通性问题上展现出强大的能力能够高效地处理元素之间的关系判断元素是否属于同一集合以及将不同集合进行合并操作。 这里我们就记住同根就连通合并总发生在根上。
二·数据结构表示 数组存储
最常见的实现方式是使用一个数组 pre[] 来存储每个元素的父节点信息。初始时每个元素自成一个集合所以 pre[i] i表示元素 i 是它自己集合的代表元素即根节点.
当然了还会有其他表示方法
也可以使用链表、树等数据结构表示并查集但数组是最常用的因为其实现简单操作相对便捷并且在经过优化后可以达到理想的性能。 三·基本操作及实现
3.1初始化
void init() {for (int i 1; i n; i) {pre[i] i;//无连接把自身初始化成前驱节点}return;
}
这里就不用多解释了把一开始还没给关系它们每个节点自己就是一个集合自己是自己的根节点。
3.2查找操作root
功能查找元素所在集合的代表元素根节点。
通过不断查找元素的父节点直到找到父节点为自身的元素该元素即为集合的代表元素。
这里我们可以用循环来实现也可以用递归但是如果它深度太高还是循环比较友好但是一般数据又不会太大。
比如我们举个例子 例如对于集合 {0, 1, 2}其中 pre[0] 0, pre[1] 0, pre[2] 1查找元素 2 的根节点时先找到 pre[2] 1继续查找 pre[1] 0最终找到根节点为 0。 下面就用普通的递归实现我们的查找操作
int root(int x) {return pre[x]x?x:root(pre[x]);//递归找到根节点
}
3.3 合并操作merge
功能将两个元素所在的集合合并为一个集合。
首先找到两个元素的根节点如果根节点不同则将其中一个根节点作为另一个根节点的子节点完成集合的合并。 注意合并操作不是就是找根节点嘛这里我们可以规定方向但是也可以不规定前提是我们保证所合并的集合的每个节点的通过父亲节点找到的根节点一定是同一个即可。但是对于朴素法也就是我们上面所写的还没有做优化可以认为后者的根节点点是前者的根节点的根节点 下面就是简单版本的合并
void merge(int i, int j) {int x root(i), y root(j);pre[x]y;return;
}
这样就是实现好了。其实上面实现的就是我们的朴素版本。
朴素版
const int N 5005;/// summary
/// 多插树
/// /summary
int pre[N];//类似前驱节点pre[i]是i指向的前一个节点ji-j
int rk[N];//每个节点的秩高度
int sz[N];//以i号节点作为根节点的集合的节点个数
int n, m, p;void init() {for (int i 1; i n; i) {pre[i] i;//无连接把自身初始化成前驱节点}return;
}
//找根节点
int root(int x) {return pre[x]x?x:root(pre[x]);//递归找到根节点
}
//合并总发生在根节点
void merge(int i, int j) {int x root(i), y root(j);pre[x]y;return;
}
但是这样肯定是时间复杂度肯定比较高的可以认为为O(N)那么下面我们来介绍一下它的优化策略。 四.优化策略:
下面我们分三种情况来把朴素版给优化一下
4.1路径压缩 介绍在查找操作时将查找路径上的元素的父节点都直接指向根节点以减少后续查找的时间复杂度。
那么我们只需要在查找元素的根节点时将路径上的元素的父节点直接更新为根节点。
也就是我们最后的目的就是让每个点的父亲节点都是他们的根节点即可。 当然了它的实现可以是循环解决也可以是递归但是对于数据不是特别大我们就选递归因为它比较好写
4.1.1递归版本
//找根节点
int root(int x) {return pre[x]pre[x] x ? x : root(pre[x]);//递归找到根节点,归的时候完成对当前节点的最终指向根节点}
4.1.2迭代版本
int root(int x){int rx;while(pre[r]0){rpre[r];}//拿到根while(pre[r]0){int respre[x];pre[x]r;xres;} return r;}
这个优化只需要我们更改找根操作即可其他和朴素法一样。 但是这样就一定好嘛我们之前说的是它是一个多插树这样就破坏了树的结构当然也是可以用的只限于单个数据结构也就是只有它自己但是如果还要和其他数据结构的功能配合使用那么就麻烦了因此我们就要建议使用后面的优化方法了。 时间复杂度就降到O(1)了。
总代码
const int N 5005;/// summary
/// 多插树
/// /summary
int pre[N];//类似前驱节点pre[i]是i指向的前一个节点ji-j
int rk[N];//每个节点的秩高度
int sz[N];//以i号节点作为根节点的集合的节点个数
int n, m, p;路径压缩破坏树结构void init() {for (int i 1; i n; i) {pre[i] i;//无连接把自身初始化成前驱节点}return;
}
//找根节点
int root(int x) {return pre[x]pre[x] x ? x : root(pre[x]);//递归找到根节点,归的时候完成对当前节点的最终指向根节点}
//合并总发生在根节点
void merge(int i, int j) {int x root(i), y root(j);pre[x] y;return;
}4.2按秩合并 目的避免合并操作使树变得过于不平衡影响查找性能。 为每个节点维护一个秩rank可以是树的高度或集合的大小即叶子节点秩为0合并时将秩小的集合合并到秩大的集合秩相等时任意合并并更新秩。 说白了也就是让我们的这颗树变的矮一点胖一点而不是高高瘦瘦的那这样为什么能起到优化作用呢
我们的秩就是树高如果我们让秩小的和并时候指向高的也就是让高树的根节点成为矮树根节点的父亲节点这样我们在查询高树的N多个底层节点的时候就可以少走一次了 矮树多走一步但是它相对走的少啊。
那么这就得出结论了 让秩小的根节点指向秩大的根节点如果相同呢那么随便指向但是此时我们就要更新最终根节点的秩也就是加一了这里其实就不完全考虑我们上面朴素法定义的关系指向了只需要保证同集合共根即可。 时间复杂度就近似O(logN)了。
定义rk数组存放每个节点的秩
void merge(int i, int j) {int x root(i), y root(j);if (rk[x] rk[y]) swap(x, y);//保证x的秩大。秩大的指向秩小的根节点pre[y] x;if (rk[x] rk[y])rk[x];//如果相等则根节点可以互相指向但是被指向的节点秩要更新return;
}然而这里我们只需要更改合并操作对于查找的操作我们也可以修改成循环形式
总代码
const int N 5005;/// summary
/// 多插树
/// /summary
int pre[N];//类似前驱节点pre[i]是i指向的前一个节点ji-j
int rk[N];//每个节点的秩高度
int sz[N];//以i号节点作为根节点的集合的节点个数
int n, m, p;/// /按秩合并根据高度关系让root函数查找的时候找的更快每个节点都少走一个提高效率
void init() {
for (int i 1; i n; i) {pre[i] i;//无连接把自身初始化成前驱节点
}
return;
}
//找根节点
int root(int x) {//return pre[x] x ? x : root(pre[x]);//递归找到根节点while (pre[x] ! x) x pre[x];return x;
}
//合并总发生在根节点
void merge(int i, int j) {int x root(i), y root(j);if (rk[x] rk[y]) swap(x, y);//保证x的秩大。秩大的指向秩小的根节点pre[y] x;if (rk[x] rk[y])rk[x];//如果相等则根节点可以互相指向但是被指向的节点秩要更新return;
}
4.3按大小合并启发合并 这里其实和按秩排序优化效果上一样只不过不是根据秩划分而是根据集合的大小来划分罢了。
就是我们合并的时候肯定会有多个集合那么我们要想集合里的元素越多那么它向上找根次数肯定越多那么如果一个大集合和一个小集合合并是不是让大集合的根指向小集合的根就可以少走很多次了类似按秩合并思想只是写法不同罢了
时间复杂度就近似O(logN)了。
因此得到总结 小集合根节点指向大集合根节点如果相同两个根节点可以随机指向其次注意合并后要更新集合大小。 因此我们搞一个数组为sz[]记录每个集合大小
也就是int sz[N];以i号节点作为根节点的集合的节点个数 。
但是这里还有个细节很容易忽略:我们这个操作不仅要改变指向集合大小还要注意初始化每个节点一开始的集合大小就是1不像按秩合并一样因为叶子节点本身秩就是0
void init() {for (int i 1; i n; i) {pre[i] i;//无连接把自身初始化成前驱节点sz[i] 1;//注意数组含义集合节点数/细节/}return;
}
合并
void merge(int i, int j) {int x root(i), y root(j);if (sz[x] sz[y]) swap(x, y);//保证x是大集合pre[y] x;sz[x] sz[y];//有y集合的纳入x变大的sz也增大return;
}
总代码
const int N 5005;/// summary
/// 多插树
/// /summary
int pre[N];//类似前驱节点pre[i]是i指向的前一个节点ji-j
int rk[N];//每个节点的秩高度
int sz[N];//以i号节点作为根节点的集合的节点个数
int n, m, p;/// /按大小合并启发合并
void init() {for (int i 1; i n; i) {pre[i] i;//无连接把自身初始化成前驱节点sz[i] 1;//注意数组含义集合节点数/细节/}return;
}
//找根节点
int root(int x) {// return pre[x] x ? x : root(pre[x]);//递归找到根节点while (pre[x] ! x) x pre[x];return x;
}
//合并总发生在根节点
void merge(int i, int j) {int x root(i), y root(j);if (sz[x] sz[y]) swap(x, y);//保证x是大集合pre[y] x;sz[x] sz[y];//有y集合的纳入x变大的sz也增大return;
}五·优化前后对比
5.1 优化前 单次查找或合并操作的最坏情况时间复杂度为 o(N)因为树可能退化成链查找元素时可能需要遍历整个链。 5.2优化后 经过路径压缩和按秩合并优化单次查找或合并操作的平均时间复杂度接近oN 其中 N 是阿克曼函数的反函数其增长速度非常慢在实际应用中可近似认为是常数时间复杂度因此优化后的并查集在效率上有显著提升。 六·例题测试
下面我们就以一道洛谷的并查集模版题测试一下吧 输入 6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6 输出 Yes
Yes
No 数据范围还是比较小的
链接 亲戚 - 洛谷
首先我们每个写法无论优化还是不优化都是可以通过的 这里数据范围比较小所以优化肯定是成立的但是我们一般看不太出来 这里按大小合并确实有点离谱了但是数据还是比较少的因此理论应该是和按秩合并一样的。
main函数实现:
int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);//取消同步cin n m p;init();//初始化自己指向自己while (m--) {int i, j;cin i j;merge(i, j);//合并完成节点的指向i-j。}while (p--) {int a, b;cin a b;if (root(a) root(b)) cout Yes endl;//根节点相同属于同一个节点else cout No endl;}}
七.应用场景 7.1网络连通性问题 在计算机网络中判断两台计算机是否处于同一子网将计算机视为元素当新的连接建立时可以使用并查集合并集合。 例如在网络拓扑中每台计算机开始是独立的集合当连接两台计算机时通过并查集的合并操作将它们所在集合合并表示它们处于同一连通区域。
7.2社交网络中的朋友圈问题: 判断两个人是否属于同一朋友圈添加好友时可以合并两个朋友圈集合。 比如在社交软件中每个人开始是一个独立的朋友圈当添加好友时使用并查集将两人所在的朋友圈集合合并。
7.3:图论中的最小生成树算法如 Kruskal 算法: 用于判断边的两个端点是否在同一连通分量若不在则合并它们所在的连通分量。 在 Kruskal 算法中对边进行排序依次取出边若边的两端不在同一集合使用并查集的合并操作最终形成最小生成树。 因此 并查集作为一种高效的数据结构通过简单的数组存储和优化的查找、合并操作在元素分组、动态连通性判断等方面具有广泛的应用。它在解决网络、社交和图算法等领域的问题时能够提供简洁有效的解决方案优化后的并查集在性能上表现出色是处理集合操作和图论问题的重要工具之一。 八·个人小结 个人认为我们在进行实现时候要注意两点同根即连通合并总发生在根上指向无所谓只要保证同一个集合元素一定都同根即可其次就是使用判断是否有关系组别划分等根据题目分析即可。
