算法— union-find
- 记录学习数据结构的总结,希望可以不拘泥于细节和语言,重视应用与推演.
资料来源如下
- 算法第四版
问题描述
白话文: 一堆网点,随机相连,设计一个算法快速检查两个点是否联通.
物理对应: 闲的一堆金属触点,随机用导线连接,快速查找两个点电路通不通.
精确描述:
定义如下API:
1
2
3
4
5UF(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
- 对于搜索类操作,改进算法的一个方面是: 增加一个数据点可以访问的维度.不限于周围元素,通过某种对应关系,拓展维度.
相关文章