欢迎访问优讯网!
您当前的位置:首页 > 爱编程

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

时间:2020-01-19 08:11:22  来源:优讯网  作者:小卡司  浏览次数:
 

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 次数组)

来顶一下
返回首页
返回首页

原文链接:https://my.oschina.net/u/3637389/blog/3159658


推荐资讯
如何下载旧版centos iso镜像 如何下载迷你mini版的centos镜像
如何下载旧版centos i
计算机的正确使用姿势 电脑痴如何正确的使用电脑
计算机的正确使用姿势
好用的后台管理的前端框架模版H-ui H-ui框架模版分享
好用的后台管理的前端
微信电脑多开方法 无需辅助电脑版微信双开方法分享
微信电脑多开方法 无
相关文章
栏目更新
栏目热门