文档章节

dynamic-connectivity 动态连通性问题之 quick-union 算法

P
 Phpythoner_Alei
发布于 01/18 01:57
字数 668
阅读 102
收藏 0

quick-union 的思想是:若对象 p 的 root_id 和对象 q 的 root_id 相等,则认为 p 和 q 连通。

若要将对象 p 和对象 q 连通(已知两对象未连通),则将 p 的 root_id 的值设为 q 的 root_id 的值,这样 p 和 q 各自所在的两个树状结构将会合并

算法类源码:

public class QuickUnionUF {
	private int[] id;
	
	//访问id[] N 次
	public QuickUnionUF(int size) {
		id = new int[size];
		for (int i = 0; i < size; i++) { //初始化id[]
			id[i] = i;
		}
	}
	
	//最多访问id[] N 次最少访问 1 次
	private int root(int i) { //追寻父节点
		while (i != id[i]) {
			i = id[i];
		}
		return i;
	}
	
	//最多访问id[] N + N - 1 = 2N - 1 次,最少访问 1 + 1 = 2 次
	//在最少的情况下,若只访问id[] 2 次,两个对象一定不是连通的
	public boolean connected(int p, int q) {
		return root(p) == root(q); 
	}
	
	//若p,q从未连通
	//则最多访问id[] N 次,最少访问 2 次
	public void union(int p, int q) {
		int i = root(p); // (N - 1) ~ 1
		int j = root(q); // 1 ~ (N - 1)
		id[i] = j;
	}
	
	public String toString() {
		String temp = "{";
		for (int i = 0; i < id.length; i++) {
			if (i == id.length - 1) {
				temp += id[i] + "}";
				break;
			}
			temp += id[i] + ", ";
		}
		return temp;
	}
}

测试类源码:

public class TestQuickUnion {
	public static void main(String[] args) {
		QuickUnionUF qu = new QuickUnionUF(10); //访问数组id[] 10 次
		qu.union(4, 3);
		System.out.println(qu); //{0, 1, 2, 3, 3, 5, 6, 7, 8, 9}
		qu.union(3, 8);
		System.out.println(qu); //{0, 1, 2, 8, 3, 5, 6, 7, 8, 9}
		qu.union(6, 5);
		System.out.println(qu); //{0, 1, 2, 8, 3, 5, 5, 7, 8, 9}
		//连通 N 个对象需要访问id[] (N - 1) * 2 ~ (N - 1) * N 次
		//访问id[]的次数随已连通对象的数目增加而增加
		//最多增量为已连通对象的数目
		//目前的这个算法的union()的时间复杂度有所改进
		//但跟quick-find相比,它的connected()时间代价较大
		System.out.println(qu.connected(8, 4)); //true
		System.out.println(qu.connected(5, 4)); //false
	}
}

quick-union 和 quick-find 同样慢(处理大量数据时花费的时间)。

quick-find 的缺点:

1、union() 的时间代价太大(访问 N 次数组)

2、多个对象连通后形成的树状结构是平展的,但是当需要连通的对象的个数 N 较大时,宏观上看,这种平展的树状结构的延伸,总体时间代价巨大!

quick-union 的缺点:

1、宏观上看,多个对象连通后形成的树状结构可能将变得非常高大;

2、find(connected())的时间代价很大(访问 2 ~ 2N -1 次数组)

© 著作权归作者所有

P
粉丝 0
博文 24
码字总数 17440
作品 0
杨浦
私信 提问
加载中

评论(0)

Cousera 公开课Princeton Algorithms Part 1笔记:Union-Find

1.Dynamic Connectivity 首先介绍了基本的关于dynamic connectivity的概念 两个操作: union command的作用是连接两个对象。find query是检查是否两个对象连通 然后 说明连接是一个等价关系(...

MrPickles
2017/10/16
0
0
算法——union-find算法

问题:问题的输入是一列整数对,其中每个整数都表示一个某种类型的对象,一对整数p q可以被理解为“p和q是相连的”。 当程序从输入中读取了整数对p q时,如果已知的所有整数对都不能说明p和q...

嘿胖丁
2018/03/01
91
1
《算法》笔记 2 - 动态连通性问题

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

zhixin9001
2019/08/19
0
0
并查集(Union-Find)算法介绍

本文主要介绍解决 本文主要介绍解决动态连通性一类问题的一种算法,使用到了一种叫做并查集的数据结构,称为Union-Find。更多的信息可以参考Algorithms 一书的Section 1.5,实际上本文也就是...

面码
2014/06/06
395
0
动态联通性问题--union-find算法

连通性问题 在给定的一张节点网络(也就是图)中,判断两个节点之是否可达的问题就是连通性问题。 场景:判断两个用户之间是否存在间接社交关系;判断两台计算机之间是否建立连接等。 定义数...

akane_oimo
2017/12/11
58
0

没有更多内容

加载失败,请刷新页面

加载更多

host machine and virtual machine communication between the three kinds of connection

1.桥接birdge模式 将虚拟机IP与物理机IP设在一个网段上,此时虚拟机相当于一台网络中与本地物理机公用一个HUB的独立设备。网络中其他机器与虚拟机、本地物理机与虚拟机都可以双向通信。虚拟机...

欣欣向荣666
2分钟前
0
0
Centos7安装gitblit

Gitblit介绍 Gitblit是一款开源工具,使用Java编写,用于管理、查看及服务于Git版本库。 Gitblit两种安装包 Gitblit GO:内部集成了Jetty服务器,不需要再集成其他容器,使用简单方便。(本文...

yhb890430
8分钟前
20
0
Ubuntu 安装 Source Code Pro 字体

1、解压字体 $ tar -zxvf source-code-pro-2.030R-ro-1.050R-it.tar.gz 2、解压字体 $ sudo cp -r source-code-pro-2.030R-ro-1.050R-it/TTF/ /usr/share/fonts/truetype/source-code-pro......

张小渔
10分钟前
17
0
mongo Authentication failed记录

虽然用的管理员账号,但是还是出现了以下的错误: 主要看后面的错误信息: { "ok" : 0.0, "errmsg" : "Authentication failed.", "code" : 18, "codeName" : "AuthenticationFailed" } 在想管......

woshixin
21分钟前
45
0
PHP+jPaginate插件制作无刷新分页实例

jPaginate是一款动感滚动分页插件,它的表现形式是像分页的按钮一样,有意思的是这些按钮却可以左右滚动,可以通过单击或鼠标滑向点两侧的小箭头来控制按钮的左右滚动。 读取第一页数据: <d...

ymkjs1990
26分钟前
53
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部