文档章节

算法——union-find算法

高乐钏
 高乐钏
发布于 2018/03/01 13:05
字数 1800
阅读 175
收藏 0

问题:问题的输入是一列整数对,其中每个整数都表示一个某种类型的对象,一对整数p q可以被理解为“p和q是相连的”。

当程序从输入中读取了整数对p q时,如果已知的所有整数对都不能说明p和q是相连的,那么则将这一对整数写入到输出中;如果已知数据可以说明p和q是相连的,那么程序应该忽略p q这对整数并继续处理输入中的下一对整数。我们将这个问题通俗地叫做动态连通性问题。

应用如下:输入的整数表示的可能是一个大型计算机网络中的计算机,而整数对则表示网络中的连接。这个程序能够判断我们是够需要在p和q之间架设一条新的连接才能进行通信,或是我们可以通过已有的连接在两者之间建立通信线路。

union-find算法的API

public class UF  
UF (int N) 以整数标志(0到N-1)初始化N个触点
void union (int p,int q) 在p和q之间建立一条连接
int find (int p) p(0到N-1)所在分量的标识符
boolean connected (int p,int q) 如果p和q存在于同一个分量中则返回true
int count()     连通分量的数量

 

我们将讨论三种不同的实现,他们均根据以触点为索引的id[]数组来确定两个触点是否存在于相同的连通分量中。

1. quick-find算法

保证当且仅当id[p]等于id[q]时p和q是连通的,换句话说,在同一个连通分量中的所有触点在id[]中的值必须全部相同。算法如下:

public int find(int p){
   return id[p];
}
public void union(int p,int q) {
	//将p和q归并到相同分量中
	int pID=find(p);
	int qID=find(q);
	
	//如果p和q已经在相同的分量之中则不需要采取任何行动
	if(pID==qID) return;
	
	//将p和分量重命名为q的名称
	for(int i=0;i<id.length;i++)
		if(id[i]==pID)id[i]=qID;
	count--;
}

分析:find()操作的速度显然是很快的,以为他只需要访问id[]数组一次。。但是quick-find算法一般无法处理大型问题,因为每一对输入union()都需要扫描整个id[]数组。

每次find()调用都只需要访问一次数组,而归并两个分量的union()操作访问数组的次数在(N+3)到(2N+1)之间。

假设我们使用quick-find算法解决动态连通性问题,并且最后只得到了一个连通分量,那么至少需要调用N-1次union(),即至少(N+3)*(N-1)~N²次数访问,因而可以得出结论,quick-find算法的运行时间对于最终只能得到少数连通分量的一般应用是平方级别的。

2. quick-union算法

此算法重点是提高union()方法的速度,它和quick-find算法是互补的。

定义数据结构时,我们需要每个触点所对应的id[]元素都是同一个分量中的另一个触点的名称(也可能是它自己)——我们将这种联系称为链接

在实现find()方法时,我们从给定的触点开始,由他的链接得到另一个触点,再由这个触点链接到第三个触点,如此继续跟随链接直到到达一个根触点。不同触点,经过一系列的链接,如果可以到达同一个根触点,则说明这两个触点存在于同一个连通分量中。

使用森林的概念,根触点作为根节点,quick-union算法更容易让人理解。算法如下:

public int find(int p){
   //找出分量的名称,即根触点的名称
	
	while(p!=id[p])p=id[p];//存储的链接不等于本身,则继续追溯下一个触点
	return p;
}
public void union(int p,int q) {
	//将p和q归并到相同分量中,即将p和q的根触点统一
	int pRoot=find(p);
	int qRoot=find(q);
	
	//如果p和q已经在相同的分量之中则不需要采取任何行动
	if(pRoot==qRoot) return;
	
	//将p的根触点,指向q的根触点
	id[pRoot]=qRoot;
	
	count--;
}

分析:quick-union算法看起来比quick-find算法更快,但是分析它的算法成本难度很大,因为这依赖于输入的特点。在最好情况下,find()只需要访问一次数组就能得到一个触点所在的分量标识符;而在最坏情况下,这需要2N+1次数组访问。不难得出,quick-union算法在构造有一个最佳情况输入使得解决动态连通性的问题的用例的运行时间是线性级别(1*N)的;而最坏情况下,他的运行时间是平方级别(N*(2N+1))的。

3.加权quick-union算法

quick-union算法可以看做quick-find算法的一种改良,因为它解决了quick-find算法中最主要的问题(union()操作总是线性级别的,因为每次都需要遍历整个数组来改掉某个连通分量内的值)。

但是quick-union算法仍存在问题,我们不能保证任何情况下它都能比quick-find算法快的多。因为之前提到quick-union算法利用到森林,树的概念,每次find()都需要层层遍历到根节点,因此运行时间和节点在书中的深度息息相关。因此我们需要一个改进的方法减小节点的深度。

加权quick-union算法就能实现这样的改进,因为他总是能让较小的树连接到较大的树上。当然,这需要我们对数据结构进行相应的改进,即添加实例变量来记录每一棵树的大小,即分量大小。算法如下:

public class WeightedQuickUnionUF {
	private int[] id;		//父链接数组(由触点索引)
	private int[] sz;		//各根节点所对应的分量大小
	private int count;		//连通分量的数量
	public WeightedQuickUnionUF(int N) {
		count=N;
		id=new int[N];
		for(int i=0;i<N;i++)id[i]=i;
		sz=new int[N];
		for(int i=0;i<N;i++)id[i]=1;
	}
	public int count() {
		return count;
	}
	public boolean connected(int p,int q) {
		return find(p)==find(q);
	}
	public int find(int p) {
		while(p!=id[p])p=id[p];
		return p;
	}
	public void union(int p,int q) {
		int i=find(p);
		int j=find(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];
		}
		count--;
	}
}

对于动态连通性问题,加权quick-union算法是三种算法中唯一能够用于解决大型实际问题的算法。

最优算法

先说结论,路径压缩的加权quick-union算法是最优算法。

路径压缩即在检查每个节点的同时将他们直接链接到根节点,也就是实现了树的几乎完全的扁平化,这和quick-find算法理想情况下所得到的树非常接近。

© 著作权归作者所有

高乐钏
粉丝 11
博文 90
码字总数 73518
作品 0
南京
程序员
私信 提问
加载中

评论(1)

o
oolijpe
请教一下,构造方法的最后一行代码是啥意思啊?
《算法》笔记 2 - 动态连通性问题

动态连通性问题 实现 通用代码 Quick-Find算法 Quick-Union算法 加权Quick-Union算法 动态连通性问题 在基础部分的最后一节,作者用一个现实中应用非常广泛的案例,说明以下几点: 优秀的算法...

zhixin9001
2019/08/19
0
0
MySQL集锦---explain讲解

本文我们主要介绍了MySQL性能分析以及explain的使用,包括:组合索引、慢查询分析、MYISAM和INNODB的锁定、MYSQL的事务配置项等,希望能够对您有所帮助。 1.使用explain语句去查看分析结果 ...

宿小帅
2017/03/16
15
0
斯坦福ML公开课笔记9—偏差/方差、经验风险最小化、联合界、一致收敛

本篇与前面不同,主要内容不是算法,而是机器学习的另一部分内容——学习理论。主要包括偏差/方差(Bias/variance)、经验风险最小化(Empirical Risk Minization,ERM)、联合界(Union bou...

xinzhangyanxiang
2013/09/27
0
0
算法导论——最小生成树:Kruskal算法(利用了并查集)

package org.loda.graph; import org.loda.structure.MinQ;import org.loda.structure.Queue;import org.loda.util.In; /*** @ClassName: KruskalMST @Description:Kruskal最小生成树算法 @a......

loda0128
2015/05/26
621
0
计算机科学中最重要的32个算法

转载:http://www.infoq.com/cn/news/2012/08/32-most-important-algorithms 奥地利符号计算研究所(Research Institute for Symbolic Computation,简称RISC)的Christoph Koutschan博士在自......

Nov_Eleven
2013/06/23
532
0

没有更多内容

加载失败,请刷新页面

加载更多

为容器设置启动时要执行的命令及其入参

本页将展示如何为 Pod 中的容器设置启动时要执行的命令及其入参。 准备开始 创建 Pod 时设置命令及入参 使用环境变量来设置入参 通过 shell 来执行命令 注意 接下来 准备开始 你必须拥有一个...

xiaomin0322
16分钟前
24
0
自动化部署工具syncd

一.部署安装 (一)常用安装方式 1. curl https://syncd.cc/install.sh | bash 2. dockerfile安装方式正在测试中 (二)安装参考文档 1.https://syncd.cc/docs/#/install 2.https://github....

浮世清欢-千帆
21分钟前
30
0
如何学习嵌入式?(网上汇总)

如何学习嵌入式?汇总了网上的一些帖子,最后部分给出了一些资源的下载链接 嵌入式菜鸟学习路线,2019, https://zhuanlan.zhihu.com/p/68227075 嵌入式小白到大神学习全攻略(学习路线+课程...

sentuate
22分钟前
23
0
工欲善其事,必先利其器——DevOps中如何管理工具包

一、背景 作为DevOps交付流水线的开发者,为支持CI/CD中各项任务的自动化,都需要依赖多种包管理工具来下载各种相关的工具,比如针对产生最终交付件的构建过程,就需要在构建流程的第一步,自...

JFrog杰蛙
22分钟前
22
0
深度探索JFR - JFR详细介绍与生产问题定位落地 - 2. 通过一个线上调优例子了解JMC 与 Event 结构与详细配置

查看 JFR 事件的工具 - JMC (Java Mission Control) 官网地址:https://adoptopenjdk.net/jmc.html 国内下载起来比较慢,建议在aws上面建一个欧洲法兰克福的实例,在这个实例上先下载好,然...

zhxhash
24分钟前
26
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部