算法— union-find


  • 记录学习数据结构的总结,希望可以不拘泥于细节和语言,重视应用与推演.

资料来源如下

  • 算法第四版

问题描述

  • 白话文: 一堆网点,随机相连,设计一个算法快速检查两个点是否联通.

  • 物理对应: 闲的一堆金属触点,随机用导线连接,快速查找两个点电路通不通.

  • 精确描述:

    • 定义如下API:

      1
      2
      3
      4
      5
      UF(int N) ;//初始化 N 个点
      void union(int p,int q)//连接p q
      int find(int p)//N个点的分量标识符
      boolean conneted(int p ,int q)//p q联通返回true
      int count()//连通分量数量
    • 设计算法的任务分解为

      • 定义数据结构高效表示连通.
      • 高效实现API方法.

实现算法

  • 叙述原理,不拘泥于代码

quick-find

  • 第一印象,所谓连通两个点,类似物理上的通路,表示两个点的id的值 相同即可.

  • p q 连通,则标识量置为相同值.

  • 分析

    • 非常直观
    • find conneted 非常快.
    • union随着需要连接的节点数量而增大,每次执行 union 都需要遍历整个网格.时间复杂度平方.
    • 大型网格union成本不可接收.
  • 改进

    • 从标识量入手,降低 union 复杂度,即使意味着 find conneted 等成本上升.
    • 平衡各个方法成本.

quick-union

  • 肯定要对标识量下手了,极端一点,将标识量 改为类似树木生长的实现,每个连通拥有一个根元素.
    conneted 判断两个节点的根元素是否相同.
    union 连通 即将两个连通的根元素 链接.
    find 直接返回根节点.

  • 这样 union 的复杂度降低,找到根节点,新建一个链接即可完成.

  • 分析

    • 逻辑上也比较好理解,类似 连通节点,用绳子串起来了.
    • union 的时间复杂度 降低到了线性级别.
    • 但 find 的成本在最糟糕情况下到了 平方 级别.
    • 最糟糕生长情况,从上到下,一个深度只有一个节点.
  • 改进

    • 由导致 find 最糟糕情况入手,避免这种情况.关注点在 树生长的过程.

加权quick-union

  • 我们的目标 控制树的生长,即控制树生长的深度,尽力减少平均深度.

  • 主要做法: union 时,区分大小树,(节点多的树为大),小树只能链接到大树.代码上 要增加一个 数组来标识 一个连通的节点数.

  • 分析

    • 可以很好控制 树生长的高度.
    • 各个方法的时间复杂度,平衡很好.
    • 但是还不是最完美.
  • 改进

    • 继续改进 union 时操作,控制树生长的高度.

路径压缩的加权quick-union

  • 对 union 操作似乎无法继续改进.

  • 但是从直觉上考虑,要控制树的深度,最直接的情况就是所有节点直接连接到根节点.

  • so,在 find 操作中 加入这个转换,将所有节点 直接 连接到根节点.

  • 分析

    • 这是我们目前可以找到的最优解.
    • 但不是所有操作都可以在场数级别.

总结

  • 完整详细定义问题,找到解决问题所必须的抽象操作并定义 API
  • 对于搜索类操作,改进算法的一个方面是: 增加一个数据点可以访问的维度.不限于周围元素,通过某种对应关系,拓展维度.