动态联通性问题----union-find算法

定义union-find算法API:

public class UF{               UF(int N)                          初始化N个触点       void union(int p,int q)            在p和q之间建立连接          int find(int p)                        p所在的分量的标识符 boolean connected(int p,int q)     p和q同在一个分量中则为true          int count()                             连通分量的数量 }

初始状态,每个触点都是一个分量。两点之间建立连接后,union()方法会将两个分量合并,一个分量中各触点都相互连接。find()方法返回给定触点所在连通分量的标识符。

此份API中,构造函数和count()方法很好写,connected方法只含有一条语句,即return find(p)==find(q);

数据结构:采用数组来实现。初始时数组各个元素保存自己的下标。

所以关键是实现find()方法和union方法。

1、quick-find算法

quick-find算法保证在同一连通分量中所有触点id[]中的值必须相同,这样connected()方法只需判断id[p]==id[q]即可。

find方法只需return id[p]; 而将两个连通分量合并,union()必须遍历数组,将一个连通分量中的id[]值变为另一个连通分量的id[]值。

public int qk_find(int p) {
	return id[p];
}
	
public void qf_union(int p,int q) {
	int pID = qk_find(p);
	int qID = qk_find(q);
	if(pID == qID) return;
	for(int i = 0;i<id.length;i++)
		if(id[i] == pID) id[i] = qID;
	count--;
}

算法分析:

在quick-find算法中,每次find()调用访问一次数组,归并两个分量的union()操作访问数组次数在(N+3)到(2N+1)之间。

假设最后只得到一个连通分量,至少需要N-1次union操作,(N+3)*(N-1)~N^2, 算法是平方级别的。

2、quick-union算法

quick-union算法中每个触点所对应的id[]元素都是另一个触点的名称(也可能是自己,如果是自己的画说明是根触点),触点之间循环这种关系直到到达根触点。当且仅当两个触点开始这个过程打到同一个根触点说明它们存在于一个连通分量中。

find()方法就是沿着这条路径找到根节点。union()方法只需将一个根节点链接到另一个上面就可实现合并分量。每个分量其实都是一个多叉树。

public int qu_find(int p) {
	while(p!=id[p]) p=id[p];
	return p;
}
	
public void qu_union(int p,int q) {
	int pRoot = qu_find(p);
	int qRoot = qu_find(q);
	if(pRoot == qRoot) return;
	id[pRoot] = qRoot;
	count--;
}

算法分析:

find()方法访问数组次数是1+触点所在树的高度*2;union()和connected()为两次。

算法改进(加权quick-union算法):

保证小的树链接在大树上,即给每一个分量添加权重。

在类中新建一个数组保存各根节点的权重,注意该数组只有只有根结点对象的下标中的数据有效。然后修改union方法如下:

public void wei_union(int p,int q) {
	int i = qu_find(p);
	int j = qu_find(q);
	if(i == j) return;
	if(sz[i]<sz[j]) {id[i]=j;sz[j]+=sz[i]}
	else {id[j]UF = i; sz[i]+=sz[j];}
	count--;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏DOTNET

.Net多线程编程—Parallel LINQ、线程池

Parallel LINQ 1 System.Linq.ParallelEnumerable 重要方法概览: 1)public static ParallelQ...

2997
来自专栏文武兼修ing——机器学习与IC设计

开放地址法散列开放地址法代码实现

开放地址法 开放地址法是另一种(相对于分离链接法)解决散列冲突的方法。适用于装填因子(散列表中元素个数和散列表长度比)较小(小于0.5)的散列表。 开放地址法中...

46312
来自专栏互联网开发者交流社区

使用Java实现面向对象编程

1252
来自专栏Jack-Cui

第三天、计算某日是该年的第几天

       编写一个计算天数的程序,用户从键盘中输入年、月、日,在屏幕中输出此日期是该年的第几天。 C代码: /*第三天、计算某日是该年的第几天*/ #i...

2120
来自专栏文武兼修ing——机器学习与IC设计

Python解决大规模二进制数据错位问题描述解决方法实验代码最终代码

问题描述 有一些二进制数据,每八位按顺序存为一个十进制数保存成CSV文件,每行为一个二进数数据,每个单元格均为一个十进制数。若数据为0000 0001 1000...

34910
来自专栏阿尔法go

Pandas速查手册中文版

本文翻译自文章: Pandas Cheat Sheet - Python for Data Science,同时添加了部分注解。 对于数据科学家,无论是数据分析...

8087
来自专栏对角另一面

lodash源码分析之数组的差集

外部世界那些破旧与贫困的样子,可以使我内心世界得到平衡。 ——卡尔维诺《烟云》 本文为读 lodash 源码的第十七篇,后续文章会更新到这个仓库中,欢迎 s...

42114
来自专栏Petrichor的专栏

tensorflow: variable初始化

tf.global_variables_initializer() 将在其创建时查看全局图并自动将依赖关系添加到图中的每个 tf.initializer。

2282
来自专栏数据结构与算法

P3388 【模板】割点(割顶)

题目背景 割点 题目描述 给出一个n个点,m条边的无向图,求图的割点。 输入输出格式 输入格式: 第一行输入n,m 下面m行每行输入x,y表示x到y有一条边 输...

3707
来自专栏前端迷

数据结构与前端(二)-队列

因为单链队列在出队操作的时候需要 O(n) 的时间复杂度,所以引入了循环队列。循环队列的出队操作平均是 O(1) 的时间复杂度。

1302

扫码关注云+社区

领取腾讯云代金券