• 并查集总结


    1、简介

    1)有若干个样本 a、b、c、d… 类型假设是 V

    2)在并查集中一开始认为每个样本都在单独的集合里

    3)用户可以在任何时候调用如下两个方法:

    • boolean isSameSet(V x, V y):查询样本 x 和 样本 y 是否属于一个集合

    • void union(V x,V y):把 xy 各自所在集合的所有样本合并成一个集合

    4)isSameSetunion 方法的代价越低越好

    2、并查集结构

    1)每个节点都有一条往上指的指针

    2)节点 a 往上找到的头节点,叫做 a 所在集合的代表节点

    3)查询 xy 是否属于同一个结合,就是看看找到的代表节点是不是一个

    4)把 xy 各自所在集合的所有点合并成一个集合,只需要小集合的代表点挂在大集合的代表点的下方即可

    (可以用哈希表或者数组实现,虽然二者的时间复杂度一致,但是哈希表实现方式的常数比数组实现的常数大2倍左右,所以在数据量很大的时候,数组的实现方式用时更少)

    3、并查集的优化

    1)节点往上找代表节点的过程,把沿途的链变成扁平的 【路径压缩

    说明:比如 a->b->c->f,即代表节点是 f,那么则将 abc分别直接连到 f,变成了a->fb->fc->f

    2)小集合挂在大集合的下面 【按秩合并

    说明:小集合挂在大集合下,链的长度增长得比较慢。所谓大小集合就是集合的元素个数,元素个数多的叫做大集合,小的叫做小集合。

    3)如果方法调用很频繁,那么单次调用的代价为 O ( 1 ) O(1) O(1),两个方法都如此

    4、并查集的应用

    • 解决两大块区域的合并问题
    • 常用在图等领域中(连通性问题)
  • 相关阅读:
    【无标题】
    Python 中 key 参数的含义及用法
    99. 激光炸弹(二维前缀和)
    【python】设置里的BASE_DIR
    QQ小程序——无法正常创建项目与uniapp联动问题
    Shell基础
    C语言字符转数字函数
    【设计模式】Java设计模式 - 解释器模式
    LeetCode —— 回溯
    我心目中的分布式操作系统
  • 原文地址:https://blog.csdn.net/u011386173/article/details/126109979