美文网首页
并查集--Union Find

并查集--Union Find

作者: 叫我胖虎大人 | 来源:发表于2019-10-05 22:49 被阅读0次

并查集的概念

一种可以用来判断相互关联(同属一个集合)的元素属于几个集合,也可以用来判断图结构中的两点是否是联通的算法(动态连接,时候属于同一个集合)。

假设存在数组
0 1 2 3 4 5 6 7 8 9
他们分别属于集合
0 1 0 1 0 1 0 1 0 1

那么元素0,2,4,6,8及时关联的,同样的1,3,5,7,9也是

上述的0~9并不代表实际的元素,相当于元素的索引

对于一组数据,主要支持两个操作

  • union(p,q)
  • isConnected(p,q) -> find(p) == find(q)

并查集的应用

  • 用来合并集合元素,并确定集合数量,查询元素属于哪一个集合。

Quick Union

  • 这里将每一个元素都看做成是一个节点

拿一个数组做比喻


初始化

上面一排的数字是数字的索引,下面一排是所指向的集合

在初始化时,所有的节点都指向自己,此时便是一棵森林


初始化
  • 合并4,3


    union 4,3
    union 4,3
  • 合并3,8


    Union 3,8
    Union 3,8
  • 合并9,4


    Union 9,4

注意:这里是9是直接指向的8(需要进行一步遍历操作),是为了防止出现线性结构[但是在某些操作中还是会出现线性结构]

例如 0,1,2,3,4,5,6进行
unioin(0,1),unioin(0,2),unioin(0,3),unioin(0,4),unioin(0,5),unioin(0,6)这样就会形成一个链表
解决方案:让节点少的那棵树指向节点多的那棵树的根节点(基于size的优化 )


假设当前的节点结构如下


当前节点情况
  • 执行union(6,2)操作


    union(6,2)

直接使用6的根节点指向2的根节点


基于rank(深度)的优化

上面提到了可能会出现链表的问题,并提出了基于size的解决方法.源码传送门

其实,基于size的优化是不够合理的,在进行元素合并的时候,决定方法复杂度的是树的深度而不是树的元素个数.


例如这个Unoin(4,2)操作,应当通过比较深度来判断谁作为根节点

源码传送门


路径压缩

面所示森林的任意两个元素之间都是鼠疫同一个元素的(根据根节点是否一致进行判定)

相同的效果,明显最左边的树形结构效率最低,中间效率最高,那么如何才能使得树形结构效率靠近中间的树呢?
这里就要涉及到路径压缩.

  • 方案一
    find()方法中执行parent[p] = parent[parent[p]]操作
    也就是节点上移

    遍历结束后的结果
再次遍历4

最终也会成为中间的那棵树
源码传送门
但是上述的核心代码并不能使得二叉树完全成为上述三棵二叉树的中间那棵

  • 方案二 通过递归实现
    核心代码
if(p != parent[p]) {
            parent[p] = find(parent[p]);
        }

源码传送门


这里我们计算并查集的时间复杂度是和深度相关O(h)
严格上并查集的时间复杂度:


log*n
几乎是O(1)级别的.

相关文章

  • 从并查集Union Find算法谈算法解决实际问题的过程

    从并查集Union Find算法谈算法解决实际问题的过程算法并查集算法寻找路径 从并查集Union Find算法谈...

  • 神奇的数据结构---并查集

    并查集(Union Find)何为集,集合,用树表示;何为并,集合的合并(union);何为查,查询元素所属集合(...

  • [并查集]并查集的升级路线(四)

    路径压缩并查集 并查集在经过了quick-find、quick-union、加权quick-union的演化之后,...

  • 深入理解并查集

    并查集是一种树形结构,它是由并查集算法进行维护的。而并查集算法(Union-find-algorithm),顾名思...

  • union find 并查集

    一、数据的预处理 要找一个数是不是在数组中,不可能用遍历的方法实现,这样时间复杂度就超过O(n)了。而要降低时间复...

  • 并查集 | find & union

    并查集 Disjoint Setb站大佬的讲解视频以下截屏来自⬆️讲解视频 应用 检查无向图中是否有环 Krusk...

  • 并查集(Union Find)

    并查集也叫做不相交集合(Disjoint Set),这种数据结构主要用来快速的判断两个集合是否有交集的问题,或者说...

  • 并查集 Union Find

    什么是并查集 一种很不一样得到树形结构 连接问题image.png

  • 并查集--Union Find

    并查集的概念 一种可以用来判断相互关联(同属一个集合)的元素属于几个集合,也可以用来判断图结构中的两点是否是联通的...

  • 并查集Union Find

    对于并查集的理解? a.并查集用于处理连接问题,可以非常快地判断出网络中节点的连接状态.能够快速实现数学中的集合类...

网友评论

      本文标题:并查集--Union Find

      本文链接:https://www.haomeiwen.com/subject/devrpctx.html