5
18
2016
0

【新姿势】再谈并查集 (启发式策略优化)

并查集是用树结构实现的。

①数组模拟指针

②根节点代表集合,初始时根节点指向自身

设树高为H。

查找操作:O(H)

 

注意上图(好大>_<),实现就很好理解:

  int find(int x) 
  {
      while (father[x] != x) x = father[x];
      return x;
  }
  int find(int x) 
  {
      if (father[x] != x) return find(father[x]);
      else return x;
  } 

合并操作:由②知树的合并操作对象为根节点,由①知合并就是改变根节点的指针指向。O(H)

void unionn(int x,int y)
{
  x = find(x);y = find(y);
  father[y] = x;
}

均摊:H=log2n

极端:H=n ==>相当于一个一个节点暴力合并!!递归写法有爆栈可能!!

 


我们受到了启发!

——于是接下来的优化操作被统称为“启发式策略”0.0!

优化的目的是减小树高.树越扁平,查找find(x)效率越高.

1、按秩合并
2、路径压缩
find(x)时进行.
  int find (int x)
  {
      if (father[x] != x) father[x] = find (father[x]);
      return father[x];
  }

只要在回溯时增加一个赋值操作即可!

看看效果:

n个元素的m次不相交集合操作

◆按秩合并:时间:O(m*lg(n))
◆路径压缩:最坏:O(n+lg(n))
◆按秩合并和路径压缩: O(mα(n))
 
每次查找近似常数时间的复杂度!
 
终于明白为什么说并查集"实现简单,效果拔群"了,之前一直不太明白路径压缩的代码是什么玩意..你们一定以为我是普及组选手...(TuT)

 

Category: 并查集 | Tags: 技巧 并查集 学习笔记 | Read Count: 200

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com