从并查集Union Find算法谈算法解决实际问题的过程
算法
并查集
算法
寻找路径
从并查集Union Find算法谈算法解决实际问题的过程算法解决实际问题的一般步骤
并查集算法概述
实际问题引出
问题建模
算法版本一 QuickFind一、使用数组的值表示连接关系
二、算法的具体实现
三、算法分析
算法版本二 QuickUnion一、在树组内创建树表示连接关系
二、算法的具体实现
算法分析
改进版本二 垂直化到扁平化第一步:带权合并
实现
再进一步:压缩路径
四种算法时间复杂度对比
解决实际问题: 乡村公路畅通工程问题描述
问题解决
代码说明
算法解决实际问题的一般步骤
Steps to developing a usable algorithm.
问题建模(Model the problem.)
寻找算法解决问题(Find an algorithm to solve it.)
算法的复杂度评判(Fast enough? Fits in memory?)
寻找影响时间或控件复杂的的原因(If not, figure out why.)
寻找问题源头(Find a way to address the problem.)
迭代上述过程,直到算法达标(Iterate until satisfied.)
并查集算法概述
给定一个包含N个对象的集合,集合中对象可以相互连接,实现如下命令: Union
Union command: 连接两个对象。 Find | Connect
Query: 检查两个对象是否被连接。
[图片上传中。。。(1)] 上图经历过的操作如下: union(0,1)
union(1,2)
union(3,4)
union(3,8)
union(4,9)
union(0,5)
union(5,6)
union(1,6)
union(2,7)
此时根据此图:检查结果如下: True: connected(0,6)
True: connected(0,5)
False: connected(2,3)
False: connected(6,9)
实际问题引出
如下图,P和Q两个点之间是否存在一条路径(P,Q是否连通)?
[图片上传中。。。(2)]在具体一点,现在要解决的实际问题有如下几个:
一张图片中像素点的连接检查。
大型网络中设备之间的连接检查。查找
社交网络中的好友关系。
游戏场景中的路径检查。
问题建模
复杂问题简单化 使用整型数组来抽象实际问题。舍弃一些细节,仅仅描述其连接关系。 具体的实现 使用数组的下标了表示问题中的某一个对象,使用对应的值存储连接参数。 进一步抽象 A: 连接关系 如果对象A和对象B连接,那么Connected(A,B)
返回True
如果对象A和对象B连接,B又和C连接,那么Connected(A,C)
, 返回True
B:连接组件 如果集合{p, q, r, t}
中, p,q,r
连接,t
和其他三个不连接,则有两个连接组件: {p, q, r}
和 {t}
[图片上传中。。。(3)]
问题解决: 创建数组,使用union
方法创建连接组件,使用find/connected
方法检查对象是否在同一个连接组件中。
算法版本一 QuickFind
通过问题建模,确定了数据结构和基本方法。解决步骤如下:
一、使用数组的值表示连接关系
数据结构 创建Int数组 id[N], 在这个包含N个元素的数组id中,如果id[p] 和 id[q]的值相同,那么p,q是连通的。 查找方法 检查两个对象对应的编号下的值是否一样。 连接方法 合并p到q,修改所有值为id[p]的元素的值为id[q]
[图片上传中。。。(4)]
union(6,1)
[图片上传中。。。(5)]
二、算法的具体实现
/* Quick Find 数据结构:* 优点:查找操作比较快,只需要执行一次* 缺点:合并操作效率慢,可能需要nn次数组读取 */public class QuickFindUF{private int[] id;public QuickFindUF(int N){id = new int[N];for (int i = 0; i < N; i++ )id[i] = i;}//查找:检查是否连通就是比较两个点对应的值public boolean connected(int p, int q){ return id[p] == id[q]; }//合并:合并的本质就是设置相同的值public void union(int p, int q){int pid = id[p];int qid = id[q];for (int i = 0; i > id.length; i++)if (id[i] == pid) id[i] = qid;}}
三、算法分析
初始化 初始化的时候,算法需要遍历整个数组,时间负载度为
查找 在查找操作中,仅仅需要访问数组的两个元素即可,程序执行效率的时间复杂度为常数
。 合并 合并操作在这一版本的算法中,需要遍历整个数组,时间复杂度为
最坏的情况 当需要连接
个点的时候,算法需要遍历数组
次。当前CPU每秒可以执行
条指令;内存内可以存储
个字节的内容;读取内存内所有内容则需要1s。此时,拥有
个节点,要执行
次连接,则需要
次操作,需要31年不眠不休的运算。
算法版本二 QuickUnion
一、在树组内创建树表示连接关系
数据结构 在数组内创建树,连接后在同一连接组件的元素, 组成一棵树。 查找方法 检查两个对象的根是否相同。 连接方法 合并两个节点P , Q,即将Q的Root(根节点)设置为P的根节点。
[图片上传中。。。(6)]上图中,3的根节点可以追溯的9: 3->4->9->9
5的根节点可以追溯到6: 5->6->6
这个时候,合并 3 和 5: union(3,5)
把五的根节点设置给3的根几点,也就是修改三的根节点9为6.
[图片上传中。。。(7)]
二、算法的具体实现
/快速合并优点:连接的时候时间复杂度为N缺点:查找的时候时间复杂度为N(t) */public class QuickUnionUF{private int[] id;public QuickUnionUF(int N){id = new int[N];for (int i = 0; i < N; i++) id[i] = i;}private int root(int i){ //查找树的根while (i != id[i]) i = id[i];return i;}public boolean connected(int p, int q){ //检查是否在同一棵树内return root(p) == root(q);}public void union(int p, int q){ //合并两棵树int i = root(p);int j = root(q);id[i] = j;}}
算法分析
初始化 初始化的时候,算法需要遍历整个数组,时间负载度为
查找 在查找操作中,需要回溯到一棵树的根节点,程序执行效率的时间复杂度为常数
。 合并 合并操作在这一版本的算法中,需要多次回溯一棵树的根节点,时间复杂度为
, t为树的高度。 最坏的情况 按照目前的算法,如果一颗树过于高,那么寻找root的操作就会浪费大量的时间。这种算法复杂度高于版本1。
改进版本二 垂直化到扁平化
版本二QuickUnion 的缺陷就在于,合并操作很容易一不小心就产生一颗非常高的树,然后在回溯这棵树的时候,需要经过大量的节点才能找到root,故此效率低下。
第一步:带权合并
解决的办法是降低树的高度,在合并操作中,如果碰到两棵树的合并,将小一点的树放在大树的下面,将小树的根节点作为大树的根节点的子节点,则可以降低树的高度。因此我们需要一个额外的数组来记录每一个树的尺寸。这些值也就被乘坐权重,改进后的算法被称作带权合并。
[图片上传中。。。(8)] 上图中,如果按照Quick-union的方法,很有可能得到一颗很高的树,原因就在于一颗大树的根节点被当作了小树的子节点。 加权之后,进行判断,确保小树永远被放置在大树内,大大降低了树的高度。
实现
public class WeightedQuickUnionUF {private int[] id;private int[] sz;//初始化数组 public WeightedQuickUnionUF(int N) {id = new int[N];sz = new int[N];for (int i = 0; i < N; i++){id[i] = i;sz[i] = 1;//初始化每颗树高度都为1 }}private int root(int i) {while (i != id[i]) i = id[i];return i;}public boolean connected(int p, int q) {return root(p) == root(q);}public void union(int p, int q) {int i = root(p);int j = root(q);if (i == j) return;//比较树的大小,确定让小树追加在大树内if(sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }else { id[j] = i; sz[i] += sz[j]; }}}
带权前后树的高度对比:
[图片上传中。。。(9)]
再进一步:压缩路径
带权合并之后树的高度明显降低,回溯的代价也就更小了。但是,在回溯的时候我们一就是一个节点一个节点的往上追溯。
[图片上传中。。。(10)]
在上图中要找到3的root: 3->4->9 return 9
因为id[4] = 9 如果利用这个特性,在这个时候压缩一下追查的路径:
3->id[4] return 9
这样一来回溯的成本将大大降低,因此可以对追查root的代码进一步优化:
private int root(int i){while (i == id[i]){i = id[id[i]];id[i] = i;}}
效果如下: 压缩素经之前:
[图片上传中。。。(11)]压缩路径之后:
[图片上传中。。。(12)]
四种算法时间复杂度对比
[图片上传中。。。(13)]
解决实际问题: 乡村公路畅通工程
问题描述
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。现在要求任意给出两个城镇,查看其是否连通?
问题解决
通过对问题的建模,发现可以直接套用Union-Find算法即可:
编码实现: 首先创建一个数组,包含所有乡镇并使其对应一个编号,其次使用乡镇对应的数组下标创建一个数组 然后使用连接已经连通的乡镇,最后进行程序测试。
代码说明
代码实现,为了方便输入,这里使用Python来实现算法:
-- coding:utf-8 --#这里的乡镇仅作演示,实际问题中可以考虑从文件中读取PLACES = ['大王村', '河阳', '蛮荒殿', '流波镇', '青云山', '万蝠洞', '凤凰镇', '南疆古镇', '七里侗']#通过地名获取编号def idof(place):return PLACES.index(place)#检查输入的地名def cheked(place):return place in PLACES#算法实现class UnionFind:'''算法的Python实现,实际上逻辑是一样的'''def init(self, N):self.sd = []self.sz = []for i in range(N):self.sd.append(i)self.sz.append(1)def root(self, i):while self.sd[i] != i:i = self.sd[self.sd[i]]self.sd[i] = ireturn idef connected(self, p, q):return self.root(p) == self.root(q)def union(self, p, q):i = self.root(p)j = self.root(q)if i == j:returnif self.sz[i] < self.sz[j]:self.sd[i] = jself.sz[j] += self.sz[i]else:self.sd[j] = iself.sz[i] += self.sz[j]if name == "main":uf = UnionFind(len(PLACES))#随便连接几个点,以便于测试uf.union(idof('大王村'), idof('流波镇'))uf.union(idof('大王村'), idof('蛮荒殿'))uf.union(idof('流波镇'), idof('七里侗'))#录入要查寻的地名place_a = raw_input("请输入要查询的第一个地点:")place_b = raw_input("请输入要查寻的第二个地点:")#输出结果if cheked(place_a) and cheked(place_b):result = uf.connected(idof(place_a), idof(place_b))print "%s 和 %s 之间是否连通?\t %s" % (place_a, place_b, result)else:print "输入地名有误"
程序运行结果:
[图片上传中。。。(14)] 连通情况:
[图片上传中。。。(15)]
**
greenpointan**
** 退出账号
当前文档
** 恢复至上次同步状态** 删除文档** 导出...** 预览文档** 分享链接
系统
** 设置
** 使用说明
** 快捷帮助
** 常见问题
** 关于
**
算法从并查集Union Find算法谈算法解决实际问题的过程
网络和大数据Tell me about your faimly
GUI程序开发基于面部识别的日志系统的设计与实现
离散数学数学史上曾经出现过的三大危机
归档
** 网络和大数据
** 口语学习##算法解决实际问题的一般步骤
Steps to developing a usable algorithm.
- 问题建模(Model the problem.)
- 寻找算法解决问题(Find an algorithm to solve it.)
- 算法的复杂度评判(Fast enough? Fits in memory?)
- 寻找影响时间或控件复杂的的原因(If not, figure out why.)
- 寻找问题源头(Find a way to address the problem.)
- 迭代上述过程,直到算法达标(Iterate until satisfied.)
并查集算法概述
给定一个包含N个对象的集合,集合中对象可以相互连接,实现如下命令:
Union
Union command: 连接两个对象。
Find | Connect
Query: 检查两个对象是否被连接。
上图经历过的操作如下:
union(0,1)
union(1,2)
union(3,4)
union(3,8)
union(4,9)
union(0,5)
union(5,6)
union(1,6)
union(2,7)
此时根据此图:检查结果如下:
True:
connected(0,6)
True: connected(0,5)
False:
connected(2,3)
False: connected(6,9)
实际问题引出
如下图,P和Q两个点之间是否存在一条路径(P,Q是否连通)?
在具体一点,现在要解决的实际问题有如下几个:
- 一张图片中像素点的连接检查。
- 大型网络中设备之间的连接检查。查找
- 社交网络中的好友关系。
- 游戏场景中的路径检查。
问题建模
复杂问题简单化
使用整型数组来抽象实际问题。舍弃一些细节,仅仅描述其连接关系。
具体的实现
使用数组的下标了表示问题中的某一个对象,使用对应的值存储连接参数。
进一步抽象
A: 连接关系
如果对象A和对象B连接,那么Connected(A,B)
返回True
如果对象A和对象B连接,B又和C连接,那么Connected(A,C)
, 返回True
B:连接组件
如果集合{p, q, r, t}
中, p,q,r
连接,t
和其他三个不连接,则有两个连接组件:
{p, q, r}
和 {t}
问题解决:
创建数组,使用union
方法创建连接组件,使用find/connected
方法检查对象是否在同一个连接组件中。
算法版本一 QuickFind
通过问题建模,确定了数据结构和基本方法。解决步骤如下:
一、使用数组的值表示连接关系
数据结构
创建Int数组 id[N], 在这个包含N个元素的数组id中,如果id[p] 和 id[q]的值相同,那么p,q是连通的。
查找方法
检查两个对象对应的编号下的值是否一样。
连接方法
合并p到q,修改所有值为id[p]的元素的值为id[q]
union(6,1)
二、算法的具体实现
/* Quick Find 数据结构:
* 优点:查找操作比较快,只需要执行一次
* 缺点:合并操作效率慢,可能需要n*n次数组读取
* */
public class QuickFindUF
{
private int[] id;
public QuickFindUF(int N)
{
id = new int[N];
for (int i = 0; i < N; i++ )
id[i] = i;
}
//查找:检查是否连通就是比较两个点对应的值
public boolean connected(int p, int q)
{ return id[p] == id[q]; }
//合并:合并的本质就是设置相同的值
public void union(int p, int q)
{
int pid = id[p];
int qid = id[q];
for (int i = 0; i > id.length; i++)
if (id[i] == pid) id[i] = qid;
}
}
三、算法分析
初始化
初始化的时候,算法需要遍历整个数组,时间负载度为$N$
查找
在查找操作中,仅仅需要访问数组的两个元素即可,程序执行效率的时间复杂度为常数$1$。
合并
合并操作在这一版本的算法中,需要遍历整个数组,时间复杂度为$N$
最坏的情况
当需要连接$N$个点的时候,算法需要遍历数组$N2$次。当前CPU每秒可以执行$109$条指令;内存内可以存储$109$个字节的内容;读取内存内所有内容则需要1s。此时,拥有$109$个节点,要执行$109$次连接,则需要$109 * 10^9$次操作,需要31年不眠不休的运算。
算法版本二 QuickUnion
一、在树组内创建树表示连接关系
数据结构
在数组内创建树,连接后在同一连接组件的元素, 组成一棵树。
查找方法
检查两个对象的根是否相同。
连接方法
合并两个节点P , Q,即将Q的Root(根节点)设置为P的根节点。
上图中,3的根节点可以追溯的9:
3->4->9->9
5的根节点可以追溯到6:
5->6->6
这个时候,合并 3 和 5:
union(3,5)
把五的根节点设置给3的根几点,也就是修改三的根节点9为6.
二、算法的具体实现
/*快速合并
*优点:连接的时候时间复杂度为N
*缺点:查找的时候时间复杂度为N(t)
* */
public class QuickUnionUF
{
private int[] id;
public QuickUnionUF(int N)
{
id = new int[N];
for (int i = 0; i < N; i++) id[i] = i;
}
private int root(int i)
{ //查找树的根
while (i != id[i]) i = id[i];
return i;
}
public boolean connected(int p, int q)
{ //检查是否在同一棵树内
return root(p) == root(q);
}
public void union(int p, int q)
{ //合并两棵树
int i = root(p);
int j = root(q);
id[i] = j;
}
}
算法分析
初始化
初始化的时候,算法需要遍历整个数组,时间负载度为$N$
查找
在查找操作中,需要回溯到一棵树的根节点,程序执行效率的时间复杂度为常数$1$。
合并
合并操作在这一版本的算法中,需要多次回溯一棵树的根节点,时间复杂度为$Nt$, t为树的高度。
最坏的情况
按照目前的算法,如果一颗树过于高,那么寻找root的操作就会浪费大量的时间。这种算法复杂度高于版本1。
改进版本二 垂直化到扁平化
版本二QuickUnion 的缺陷就在于,合并操作很容易一不小心就产生一颗非常高的树,然后在回溯这棵树的时候,需要经过大量的节点才能找到root,故此效率低下。
第一步:带权合并
解决的办法是降低树的高度,在合并操作中,如果碰到两棵树的合并,将小一点的树放在大树的下面,将小树的根节点作为大树的根节点的子节点,则可以降低树的高度。因此我们需要一个额外的数组来记录每一个树的尺寸。这些值也就被乘坐权重,改进后的算法被称作带权合并。
上图中,如果按照Quick-union的方法,很有可能得到一颗很高的树,原因就在于一颗大树的根节点被当作了小树的子节点。
加权之后,进行判断,确保小树永远被放置在大树内,大大降低了树的高度。
实现
public class WeightedQuickUnionUF
{
private int[] id;
private int[] sz;
//初始化数组
public WeightedQuickUnionUF(int N)
{
id = new int[N];
sz = new int[N];
for (int i = 0; i < N; i++)
{
id[i] = i;
sz[i] = 1;//初始化每颗树高度都为1
}
}
private int root(int i)
{
while (i != id[i]) i = id[i];
return i;
}
public boolean connected(int p, int q)
{
return root(p) == root(q);
}
public void union(int p, int q)
{
int i = root(p);
int j = root(q);
if (i == j) return;
//比较树的大小,确定让小树追加在大树内
if(sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }
else { id[j] = i; sz[i] += sz[j]; }
}
}
带权前后树的高度对比:
再进一步:压缩路径
带权合并之后树的高度明显降低,回溯的代价也就更小了。但是,在回溯的时候我们一就是一个节点一个节点的往上追溯。
在上图中要找到3的root:
3->4->9 return 9
因为id[4] = 9
如果利用这个特性,在这个时候压缩一下追查的路径:
3->id[4] return 9
这样一来回溯的成本将大大降低,因此可以对追查root的代码进一步优化:
private int root(int i)
{
while (i == id[i])
{
i = id[id[i]];
id[i] = i;
}
}
效果如下:
压缩路径之前:
压缩路径之后:
四种算法时间复杂度对比
解决实际问题: 乡村公路畅通工程
问题描述
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。现在要求任意给出两个城镇,查看其是否连通?
问题解决
通过对问题的建模,发现可以直接套用Union-Find算法即可:
编码实现:
首先创建一个数组,包含所有乡镇并使其对应一个编号,其次使用乡镇对应的数组下标创建一个数组
然后使用连接已经连通的乡镇,最后进行程序测试。
代码说明
代码实现,为了方便输入,这里使用Python来实现算法:
# -*- coding:utf-8 -*-
#这里的乡镇仅作演示,实际问题中可以考虑从文件中读取
PLACES = ['大王村', '河阳', '蛮荒殿', '流波镇', '青云山', '万蝠洞', '凤凰镇', '南疆古镇', '七里侗']
#通过地名获取编号
def idof(place):
return PLACES.index(place)
#检查输入的地名
def cheked(place):
return place in PLACES
#算法实现
class UnionFind:
'''算法的Python实现,实际上逻辑是一样的'''
def __init__(self, N):
self.sd = []
self.sz = []
for i in range(N):
self.sd.append(i)
self.sz.append(1)
def root(self, i):
while self.sd[i] != i:
i = self.sd[self.sd[i]]
self.sd[i] = i
return i
def connected(self, p, q):
return self.root(p) == self.root(q)
def union(self, p, q):
i = self.root(p)
j = self.root(q)
if i == j:
return
if self.sz[i] < self.sz[j]:
self.sd[i] = j
self.sz[j] += self.sz[i]
else:
self.sd[j] = i
self.sz[i] += self.sz[j]
if __name__ == "__main__":
uf = UnionFind(len(PLACES))
#随便连接几个点,以便于测试
uf.union(idof('大王村'), idof('流波镇'))
uf.union(idof('大王村'), idof('蛮荒殿'))
uf.union(idof('流波镇'), idof('七里侗'))
#录入要查寻的地名
place_a = raw_input("请输入要查询的第一个地点:")
place_b = raw_input("请输入要查寻的第二个地点:")
#输出结果
if cheked(place_a) and cheked(place_b):
result = uf.connected(idof(place_a), idof(place_b))
print "%s 和 %s 之间是否连通?\t %s" % (place_a, place_b, result)
else:
print "输入地名有误"
程序运行结果:
连通情况: