Union-Find

用于解决动态连通图的连接性问题

问题描述

给定由N个对象构成的集合,并告知哪些对象之间是连通的,由此判断某两个对象之间是否连通。

注:连通代表有路可达,而不一定直接相连

连通性示例

抽象建模

  • 将所有对象用序号标识,如0,1,2,3...
  • Union 将告知的连通对象之间连通
  • Find 判断某两个对象之间是否连通
连通性抽象

算法描述

基本思想是,将连通图分割成N个最大连通子集,即每个子集内部的对象相互连通,而子集之间的对象互不连通,这样只需判断某两个对象是否在同一个子集中,便可判断其是否连通。

最大连通子集

具体而言,根据不同的实现方式,可衍生出以下几种算法。

1. Quick-Find

顾名思义,这是一个注重快速判断的算法。它将属于同一个子集的对象用同一个标号标识,而不同子集用不同标号标识,这时判断对象是否连通就等价于判断对象标号是否相等。

实现思路

  • 整形N维数组id[],存储N个对象所属的子集标号,下标为对象标识
  • Union 合并分别包含p和q的子集,需将所有标号等于id[p]的都置为id[q]
  • Find 判断p和q是否连通,即判断是否满足id[p]==id[q]
QF 实现图例

伪代码

// 初始化 function(int N)
id = new int[N];
for (int i = 0; i < N; i++) 
  id[i] = i; // 每个对象在初始时各不连通,各成一个子集,用其下标标识 

// Union function(int p, int q)
int pid = id[p];
int qid = id[q];
for (int i = 0; i < N; i++)
{ 
  if (id[i] == pid) 
    id[i] = qid; // 将所有子集标识等于id[p]的改为id[q]
}

// Find function(int p, int q)
return id[p] == id[q]; // 判断子集标识是否相同

这种算法虽然Find很快,但Union却非常慢,每次需要判断和改动的位置很多。一般来说,Union的次数要比Find的次数多很多,所以注重Union效率的提高会更实际一些。

2. Quick-Union

这即是一个注重快速合并的算法, 不同于Quick-Find将子集内所有对象都用同一个标识表示,它将子集中的对象看成是树状结构,每个子集形成一棵树,子集中的对象都有父对象,根对象的父对象是其自身。

此时,在N维数组中存储各对象的父对象标识,则对象i所在子集树的根为id[id[id[...id[i]...]]],同一个根对应的所有对象是连通的。这样,Find时需判断对象的根是否相同,而Union时只需将一个子集树的根变为另一个子集树的孩子。可见,Union时只需要变更一个位置,而Find则取决于树的高度。

QU 实现图例

伪代码

// Root function(int i)
while (i != id[i]) i = id[i]; // 寻找根节点
return i;

// Union function(int p, int q)
int i = root(p);
int j = root(q);
id[i] = j; // 将一颗子集树挂在另一颗子集树根上

// Find function(int p, int q)
return root(p) == root(q); // 判断对象根节点是否相同

虽然这种算法的Union速度加快,但其速度仍取决于root的速度,即树的高度,因此可优化的地方还有很多。

3. Weighted Quick-Union

这是一个基于QU的加权算法,它可有效降低树的高度,使root速度变快。

其思想是,在每次Union合并子集树时,总是将小树的根挂在大树的根上,而不像QU中总是将前一个树的根挂在后一个树的根上。

W-QU 思想

这就需要另外设置一个N维整形数组,用于存储以每个对象为根的树大小,这样在Union时便可比对子集树的大小。

伪代码

// 初始化 function(int N)
sz = new int[N]; // 树大小数组
for (int i = 0; i < N; i++)
  sz[i] = 1; // 初始时各对象自成一树,每棵树的大小为1

// Union function(int p, int q)
int i = root(p);
int j = root(q);
if (sz[i] < sz[j]) 
{
  id[i] = j;
  sz[j] += sz[i];
}
else 
{
  id[j] = i;
  sz[i] += sz[j];
}

这种算法带来的压缩树高度的效果是非常显著的,尤其是在对象个数较多时。

W-QU优化效果.png

4. Quick-Union with Path Compression

这是一种基于QU的路径压缩优化算法,目的也是压缩树的高度。

一种思想是,在每次寻找对象的根节点时,都将通往根节点的沿途各个节点直接挂在根节点下。代码实现可设置两个循环,先找根节点,再挂各节点。

QU-PC思想1

另一种思想是,在每次寻找对象的根节点时,都将对象挂在其祖父对象上,再从祖父对象依次重复上述过程。则每次root会大致将路径长度压缩一半。

伪代码

// Root function(int i)
while (i != id[i])
{
  id[i] = id[id[i]];
  i = id[i];
}
return i;

当然也可以将Weighted与Path Compression结合使用。

5. Weighted Quick-Union with Path Compression

Weighted是在Union阶段,而Path Compression是在Root阶段,两者互不干扰,可结合使用,效果更好。

伪代码(完整)

/* Weighted Quick-Union with Path Compression */

// 初始化 function(int N)
id = new int[N]; // 父对象数组
sz = new int[N]; // 树大小数组
for (int i = 0; i < N; i++)
{
  id[i] = i; 
  sz[i] = 1;
}

// Root function(int i)
while (i != id[i])
{ 
  id[i] = id[id[i]]; // 采用Path Compression第二种思想
  i = id[i];
}
return i;

// Union function(int p, int q)
int i = root(p);
int j = root(q);
if (sz[i] < sz[j]) // 采用Weighted思想
{
  id[i] = j;
  sz[j] += sz[i];
}
else 
{
  id[j] = i;
  sz[i] += sz[j];
}

// Find function(int p, int q)
return root(p) == root(q);

算法分析

现分析各算法的时间性能。

  1. Quick-Find
    UnionO(N),FindO(1)

  2. Quick-Union
    UnionO(N),FindO(N)
    主要耗时在root上

  3. Weighted-QU
    UnionO(logN),FindO(logN)
    树的高度不会超过logN(以2为底),考虑一个对象,其最开始树大小为1,每次其高度+1发生在其作为小树成员挂到大树根上,此时合并树的大小>=2倍小树大小,而小树最多不会翻倍logN次,所以高度最高不会超过logN

  4. QU + Path Compression
    UnionO(logN),FindO(logN)
    猜想:采用第二种思想时,每次可将路径压缩一半,则最终树的高度<=logN?

  5. Weighted-QU + Path Compression
    <= c(N+MlogN) 接近于线性
    N表示对象个数,M表示Union次数
    log
    N表示N经过多少次log能到达1,如log16=3, log65536=4

Algorithm Initialize Union Find Worst-Case Time
Quick-Find N N 1 MN
Quick-Union N N N MN
Weighted-QU N logN logN N + MlogN
QU + Path Compression N logN logN N + MlogN
Weighted-QU + Path Compression N log*N log*N N + Mlog*N

注:Union和 Find列均指一次操作的最坏时间复杂度, Worst-Case Time表示 M次Union操作的最坏时间复杂度。

应用举例

Union-Find 的一个典型应用是解决“渗透问题(Percolation)”

N*N的网格,网格中每一块都以概率p开启(白色)或关闭(黑色),判断从顶层能否渗透到底层(可假想从顶层注水,只能流经白色区域,水能否到达底层,或者导体通电问题等)

渗透问题示例

将每个网格看成是一个对象,这类问题明显可转化为动态连通图连接性问题,但要注意几个问题。

  1. 为避免循环,可将所有顶层节点与一个虚拟顶层节点相连,而将所有底层节点都与一个虚拟底层节点相连,这样只需判断两个虚拟节点是否连通。
  2. 开启一个网格时,应连通它与周围四个节点中所有开启的节点。
  3. Backwash问题,在将所有底层节点与虚拟底层节点相连后,如果要判断一个节点(不一定是底层节点)是否与顶层节点相连时,它可能会通过虚拟底层节点向上寻找到路径,这显然不符合常理。
    可有两种解决方式,一是取消使用底层虚拟节点,牺牲时间;二是带虚拟底层几点与不带虚拟底层节点两种模型结合使用,牺牲空间。
渗透问题建模

结束语

动态连通图问题可以是很多问题的抽象建模,如网络中计算机连接、社交中的朋友关系、数学集合中的元素等等,掌握Union-Find的各算法是非常有用的。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 202,607评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,047评论 2 379
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 149,496评论 0 335
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,405评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,400评论 5 364
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,479评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,883评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,535评论 0 256
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,743评论 1 295
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,544评论 2 319
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,612评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,309评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,881评论 3 306
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,891评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,136评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,783评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,316评论 2 342

推荐阅读更多精彩内容