搜索 - 腾讯云开发者社区-腾讯云

文章/答案/技术大牛

发布

来自专栏小浩算法
图解：什么是并查集？
Quick-Union 回忆 Quick-Find 中 union 函数，就像是暴力法，遍历所有对象的 id[] ，然后把有着相同 id 的数全部改掉， Quick-Union 算法则是引入 “树” 但 Quick-Union 算法依然是用来求解动态连通性问题的一个快速而优雅的设计。 ? Quick-Union 算法的缺点在于树可能太高了。这意味着查找操作的代价太大了。我们可以看一下 Weighted Quick-Union 操作的例子： ? 可以看到 Weighted Quick-Union 所生成的树很 “胖”，刚好满足我们的需求。 Weighted Quick-Union 算法通过对 Union 操作进行加权保证 Quick-Union 算法可能出现的 “瘦高” 情况发生。路径压缩的加权 Quick-Union （Weigthed Quick-Union with Path Compression）算法虽是最优算法，但是并非所有操作都能在常数时间内完成。
2.8K30发布于 2021-04-26
来自专栏Vegout
算法——union-find
quick-union成为了下一步的探索 public int find(int i){ while (i! qRoot = find(q); if (pRoot==qRoot) return; id[pRoot] = qRoot; count--; } 在quick-union 如下图所示，当运行main函数时，随着A处循环的进行，过程如下(公众号回复quick-union可查看动画演示) ? 此时我们就需要再次改进算法，于是出现了加权quick-union算法。 private int find(int p){ while (p ! 但没有最好，只有更好，更优秀的算法实现送给大家----使用路径压缩的加权quick-union算法： private int find(int p){ while (p !
49730发布于 2019-07-03
来自专栏mathor
并查集（Union Find）
算法加权Quick-Union算法 class UF { private int[] id; private int[] sz; private int count; 这是十分有意义的，因为在Quick-Union算法中的任何操作，都不可避免的需要调用find方法，而该方法的执行效率依赖于树的高度。树的高度减小了，find方法的效率就增加了，从而也就增加了整个Quick-Union算法的效率。上图其实还可以给我们一些启示，即对于Quick-Union算法而言，节点组织的理想情况应该是一颗十分扁平的树，所有的孩子节点应该都在height为1的地方，即所有的孩子都直接连接到根节点。，然后到对Quick-Union的几项改进，让我们的算法的效率不断的提高。
1.3K10发布于 2018-07-24
来自专栏h-t-m
算法——union-find
quick-union 算法概述，图源自《算法：第4版》这个思路貌似让 find() 方法变得非常复杂，事实上实现并不复杂。也就是为什么算法名为 quick-union 算法了。由于 quick-union 算法树与树之间实际上就是根整数与根整数之间的操作，因此我们只需为每棵树的根整数加权并在每次连接前进行比较即可。算法即使加权 quick-union 算法，依然不是现存的最优算法，即使树的高度得到了很大的控制，但我们依然希望每个节点能直接连接到根整数。路径压缩的加权 quick-union 算法是最优的算法，但并非所有操作都能在常数时间内完成。摘自：《算法：第4版》。
49710编辑于 2022-11-24
来自专栏云霄雨霁
动态联通性问题----union-find算法
2、quick-union算法 quick-union算法中每个触点所对应的id[]元素都是另一个触点的名称（也可能是自己，如果是自己的画说明是根触点），触点之间循环这种关系直到到达根触点。算法改进（加权quick-union算法）：保证小的树链接在大树上，即给每一个分量添加权重。在类中新建一个数组保存各根节点的权重，注意该数组只有只有根结点对象的下标中的数据有效。
78200发布于 2018-05-30
来自专栏小樱的经验随笔
零基础学并查集算法
Quick-Union 算法：考虑一下，为什么以上的解法会造成“牵一发而动全身”？和 Weighted Quick-Union 的比较： ? 树的高度减小了，find方法的效率就增加了，从而也就增加了整个Quick-Union算法的效率。，然后到对Quick-Union的几项改进，让我们的算法的效率不断的提高。 Weighted Quick-Union N lgN lgN Weighted Quick-Union With Path Compression N Very near to 1 (amortized
1.5K80发布于 2018-04-08
来自专栏机器学习入门
算法原理系列：并查集
实现二（quick-union）在union操作中，为了维护这种扁平结构，需要循环遍历一次数组，这种操作相当费时。（通过find手段找到同根）所以quick-union的合并思路和树的合并一个道理，union(p,q)，p和q可以分别表示在存在于某棵树的两个中间结点，找到它们的根结点后，把一棵根结点树并到另一个根结点的孩子上实现三（加权quick-union）在最坏情况下，quick-union的深度即为结点数。这是因为在合并操作时，总是把大树依附在小树的结点上。
62430发布于 2019-05-26
来自专栏决胜机器学习
有趣的算法（六） ——Find-Union算法
2、方法二：quick-union 为了加快union，现换一种思路。id[i]的值表示的是节点i的父节点。初始状态下，每个节点id[i]=i，表示自己指向自己的节点是根节点。 3、方法三：加权的quick-union 为了解决上述问题，进行了一个改进，即在连接的时候，将树节点较少的那颗，连接到节点较多的那颗。这样可以保证大多数的节点的深度不要增加。 4、方法四：压缩路径的加权quick-union 方法三的速度已经很快，还有一个地方可以进行微调。即每次find的时候，由于其都在追溯父节点，则可以把每次追溯到的父节点，都指向要连接的那个根节点。
1K40发布于 2018-03-07
来自专栏博客迁移同步
哥尼斯堡的“七桥问题“(并查集)
= parent[root]) // 加权quick-union算法，找到根节点，父节点是自己的就是根节点 { root = parent[root]; } while (p !
26310编辑于 2023-05-06
来自专栏博客迁移同步
食物链(并查集)
= parent[root]) {// 到这里为加权quick-union算法，往下继续优化 root = parent[root]; } while
46910编辑于 2023-05-06
来自专栏拭心的安卓进阶之路
使用并查集UnionFind和优先队列PriorityQueue实现Kruskal算法
[p]){ //找到它的根节点 //将p节点的父节点设置为它的爷爷节点 id[p] = id[id[p]]; p = id[p]; } return p; } //组合Weighted Quick-Union
43730编辑于 2022-11-30
来自专栏技术一点点成长
有一种算法叫做“Union-Find”？
结合本算法对quick-find()的优化，我们把它称为“quick-union”算法。 -------- 3.Union-Find再进阶　　等等，还没完！ 2-3 1-0 0-4 5-7 6-2 总连通分量数：3 4.算法性能比较：读入数据 find() union() 总时间复杂度 quick-find O(M) O(l) O(N) O(M*N) quick-union
41330编辑于 2022-08-09
来自专栏爱撸猫的杰
ACM算法基础
加权 Quick Union 为了解决 quick-union 的树通常会很高的问题，加权 quick-union 在 union 操作时会让较小的树连接较大的树上面。理论研究证明，加权 quick-union 算法构造的树深度最多不超过 logN。
2.2K30发布于 2019-03-29

图解：什么是并查集？

算法——union-find

并查集（Union Find）

算法——union-find

动态联通性问题----union-find算法

零基础学并查集算法

算法原理系列：并查集

有趣的算法（六） ——Find-Union算法

哥尼斯堡的“七桥问题“(并查集)

食物链(并查集)

使用并查集UnionFind和优先队列PriorityQueue实现Kruskal算法

有一种算法叫做“Union-Find”？

ACM算法基础

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐