请选择 进入手机版 | 继续访问电脑版

夜深人静写算法(五)- 并查集

[复制链接]
云韵 发表于 2021-1-2 12:16:05 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
文章目次



一、前言

    亲爱的读者,你三十岁了吗?
  以前总是讨厌父母的平庸,长大了才发现他们曾经也是怀揣着空想的少年,只是被生活磨平了棱角。现在的我们走着父母曾经走过的路,却发现也许我们还不如父母,当初他们拿着微薄的工资却养活了我,而我却照旧靠着父母几十年的积贮付了首付。
  小时候总是盼着长大,如果长大后父母依旧辛苦,那我们长大尚有什么意义。

二、并查集的原理

1、“并"和"查”



  • 有了深度优先搜索的底子以后,相信你对递归已经有一定的认识,那么本日让我们来认识一下并查集。
  • 并查集是一种处置惩罚不相交聚集的数据结构。
  它支持两种使用:
  1)归并使用                                    m                         e                         r                         g                         e                         (                         x                         ,                         y                         )                              merge(x, y)                  merge(x,y)。即归并两个原本不相交的聚集,此所谓 “并”。
  2)查找使用                                    f                         i                         n                         d                         (                         x                         )                              find(x)                  find(x)。即检索某一个元素属于哪个聚集,此所谓 “查”。


  • 讲个简单的故事来加深对并查集的明白,这个故事要追溯到北宋年间。话说北宋时期,朝纲败坏,奸臣当道,民不聊生。又有外侮辽军放肆南下,于是众多能人异士群起而反,各大武林门派同仇敌忾,共抗辽贼,为首的自然是中原武林第一大帮-丐帮,其帮主乃万军丛中取上将首级犹如探囊取物、泰山崩于前而面不改色的北乔峰;与其齐名的空有一腔抱负、壮志未酬的南慕容领导的慕容世家;固然也少不了天下武功的鼻祖-少林,以及一些小帮派,如逍遥派、灵鹫宫、无量剑、神农帮等等。我们将每个门派(帮派)作为一个聚集,从中选出一个代表作为这个聚集的标识,姑且认为门派(帮派)的掌门(帮主)就是这个代表。

  • 作者有幸成了“抗辽同盟”的统计员,统计员只有一个工作,就是吸收一条条同门数据,然后统计共有多少个门派,好举行分派摆设。同门数据的格式为                                    (                         x                         ,                         y                         )                              (x, y)                  (x,y),体现                                    x                              x                  x 和                                    y                              y                  y 属于同一个门派,吸收到一条数据,需要对                                    x                              x                  x 所在的群体和                                    y                              y                  y 的群体举行归并,当统计完所有数据后有多少个聚集就代表多少个门派。
  • 这个问题实在隐含了两个使用:
  • 1)查找                                    a                              a                  a 和                                    b                              b                  b 是否已经在同一个门派;
  • 2)如果两个人的门派不一致,则归并这两个人所在聚集的两堆人。分别对应了并查集的查找和归并使用。
  • 如图二-1-1所示,分别体现丐帮、少林、逍遥、大理段氏四个聚集。
         图二-1-1
2、质朴算法



  • 接下来来讨论下并查集的质朴素现,既然是质朴素现,固然是越质朴越好啦。
  • 质朴的只需要一个数组就能体现聚集,我们用                                    f                         s                         e                         t                         [                         i                         ]                              fset                  fset 体现                                    i                              i                  i 所在的聚集编号。
  质朴算法实现如下:
  1)初始化每个元素一个聚集:                                   f                         s                         e                         t                         [                         i                         ]                         =                         i                              fset = i                  fset=i;
  2)查找                                    x                              x                  x 属于哪个聚集,直接通过下标索引;
  3)归并                                    x                              x                  x 和                                    y                              y                  y 的使用,需要判定                                    f                         s                         e                         t                         [                         x                         ]                              fset[x]                  fset[x] 和                                    f                         s                         e                         t                         [                         y                         ]                              fset[y]                  fset[y] 是否相等:
   3.a)如果相等,则不作任何使用;
   3.b)如果不相等,遍历所有满足条件                                    f                         s                         e                         t                         [                         i                         ]                              fset                  fset 即是                                    f                         s                         e                         t                         [                         x                         ]                              fset[x]                  fset[x] 的                                    i                              i                  i,设置                                    f                         s                         e                         t                         [                         i                         ]                         =                         f                         s                         e                         t                         [                         y                         ]                              fset = fset[y]                  fset=fset[y];


  • 可以把                                    f                         s                         e                         t                              fset                  fset 数组明白成哈希表,查找过程的时间复杂度为                                    O                         (                         1                         )                              O(1)                  O(1);
  • 然后,归并的时候,由于需要遍历                                    f                         s                         e                         t                         [                         i                         ]                              fset                  fset,所以时间复杂度为                                    O                         (                         n                         )                              O(n)                  O(n) 。图二-2-1展示了质朴算法的一个例子,该数组一共记载了四个聚集,而且用每个聚集的最小数字作为该聚集的标识。

  图二-2-1

  • 初始化的 c++ 代码实现如下:
[code]const int MAXN = 300010;int fset[MAXN];void init(int n) {    for (int i = 1; i
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )