当前位置：网站首页>The Principle of Union Search and API Design

The Principle of Union Search and API Design

2022-08-10 05:52:00 【cbys-1357】

目录

前言：

原理：

并查集API设计 

1.​UF(int N)构造方法实现

2.union(int p,int q)合并方法实现  

 代码实现：

UF_Tree算法优化

 1 UF_Tree API设计

路径压缩

案例-畅通工程

前言：

In the last chapter, I introduced you to the tree structure of the red-black tree,以及实现原理,In this chapter I will introduce you to a simple union search,It is also a tree structure,但相对于二叉查找树,红黑树等,会相对比较简单,好理解.

原理：

并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中.

并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题.常常在使用中以森林来表示.

并查集结构
并查集也是一种树型结构,但这棵树跟我们之前讲的二叉树、红黑树、B树等都不一样,这种树的要求比较简单：
1. 每个元素都唯一的对应一个结点;
2. 每一组数据中的多个元素都在同一颗树中;
3. 一个组中的数据对应的树和另外一个组中的数据对应的树之间没有任何联系;
4. 元素在树中并没有子父级关系的硬性要求;

 

 

并查集API设计 

1.​UF(int N)构造方法实现

1. 初始情况下,每个元素都在一个独立的分组中,所以,初始情况下,并查集中的数据默认分为N个组;
2. 初始化数组eleAndGroup;
3. 把eleAndGroup数组的索引看做是每个结点存储的元素,把eleAndGroup数组每个索引处的值看做是该结点 所在的分组,那么初始化情况下,i索引处存储的值就是i

2.union(int p,int q)合并方法实现  

1. 如果p和q已经在同一个分组中,则无需合并

2. 如果p和q不在同一个分组,则只需要将p元素所在组的所有的元素的组标识符修改为qThe identifier of the group the element is in ie 可
3. 分组数量-1

 

 代码实现：

public class UF {
	//记录结点元素和该元素所在分组的标识
	private int[] eleAndGroup;
	//Record the number of groups to group by
	private int count;
	//	构造方法
	public UF(int N) {
		//初始情况下,每个元素都在一个独立的分组中,所以,初始情况下,并查集中的数据默认分为N个组
		this.count=N;
		//初始化数组
		this.eleAndGroup=new int[N];
		//把eleAndGroup数组的索引看做是每个结点存储的元素,把eleAndGroup数组每个索引处的值看做是该结点所在的分组,那么初始化情况下,i索引处存储的值就是i
		for(int i=0;i<eleAndGroup.length;i++) {
			eleAndGroup[i]=i;
		}
	}
	//获取当前并查集中的数据有多少个分组
	public int count() {
		return this.count;
	}
	//元素p所在分组的标识符
	public int find(int p) {
		return this.eleAndGroup[p];
	}
	//判断并查集中元素p和元素q是否在同一分组中
	public boolean connected(int p,int q) {
		return find(p)==find(q);
	}
	//把p元素所在分组和q元素所在分组合并
	public void union(int p,int q) {
		//如果p和q已经在同一个分组中,则无需合并;
		if(connected(p,q)) {
			return;
		}
		//如果p和q不在同一个分组,则只需要将p元素所在组的所有的元素的组标识符修改为q元素所在组的标识 符即可
		int pGroup=find(p);
		int qGroup=find(q);
		for(int i=0;i<eleAndGroup.length;i++) {
			if(find(i)==pGroup) {
				eleAndGroup[i]=qGroup;
			}
		}
		//分组数量-1
		count--;
	}

}

Everyone's brain thinks and wants to put oneN个小组,All together, how many times do we have to use it at leastunion方法?Probably everyone knows it isN-1次,而我们在union方法中又使用for循环,That is to say, combine all the groups together,The time complexity of the merge algorithm is O(n^2).If so then it might be relatively better for few groupings,Well, for problems like computing networks, the interconnection may have tens of millions,That is not optimistic.所以我们需要对算法进行优 化.

UF_Tree算法优化

为了提升union算法的性能,我们需要重新设计fifind方法和union方法的实现,此时我们先需要对我们的之前数据结构中的eleAndGourp数组的含义进行重新设定：
1.我们仍然让eleAndGroup数组的索引作为某个结点的元素;
2.eleAndGroup[i]的值不再是当前结点所在的分组标识,而是该结点的父结点;

 1 UF_Tree API设计

1. fifind(int p)查询方法实现
1.判断当前元素p的父结点eleAndGroup[p]是不是自己,如果是自己则证明已经是根结点了;
2.如果当前元素p的父结点不是自己,则让p=eleAndGroup[p],继续找父结点的父结点,直到找到根until the node;
2.union(int p,int q)合并方法实现
1. 找到p元素所在树的根结点
2. 找到q元素所在树的根结点
3. 如果p和q已经在同一个树中,则无需合并;
4. 如果p和q不在同一个分组,则只需要将p元素所在树根结点的父结点设置为q元素的根结点即可;
5. 分组数量-1

 

public class UF_Tree {
	private int[] eleAndGroup;
	private int count;
	public UF_Tree(int N) {
		this.count=N;
		this.eleAndGroup=new int[N];
		for(int i=0;i<eleAndGroup.length;i++) {
			eleAndGroup[i]=i;
		}
	}
	public int count() {
		return this.count;
	}
	
	public boolean connected(int p,int q) {
		return find(p)==find(q);
	}
	//元素p所在分组的标识符
	public int find(int p) {
		while(true) {
			//判断当前元素p的父结点eleAndGroup[p]是不是自己,如果是自己则证明已经是根结点了;
			if(p==eleAndGroup[p]) {
				return p;
			}
			//如果当前元素p的父结点不是自己,则让p=eleAndGroup[p],继续找父结点的父结点,直到找到根 until the node;
			p=eleAndGroup[p];
		}
	}
	public void union(int p,int q) {
		//找到p元素所在树的根结点
		int proot=find(p);
		//找到q元素所在树的根结点
		int qroot=find(q);
		//如果p和q已经在同一个树中,则无需合并;
		if(proot==qroot) {
			return;
		}
		//如果p和q不在同一个分组,则只需要将p元素所在树根结点的父结点设置为q元素的根结点即可;
		eleAndGroup[p]=qroot;
		//分组数量-1
		this.count--;
		
	}
}

 

优化后的性能分析
我们优化后的算法union,如果要把并查集中所有的数据连通,仍然至少要调用N-1次union方法,但是,我们发现 union方法中已经没有了for循环,所以union算法的时间复杂度由O(N^2)变为了O(N).
但是这个算法仍然有问题,因为我们之前不仅修改了union算法,还修改了find算法.我们修改前的fifind算法的时 The inter-complexity is in any caseO(1),但修改后的fifind算法在最坏情况下是O(N)：

在union方法中调用了fifind方法,所以在最坏情况下union算法的时间复杂度仍然为O(N^2).

路径压缩

 

UF_Tree中最坏情况下union算法的时间复杂度为O(N^2),其最主要的问题在于最坏情况下,The depth of the tree and the size of the array 小一样,如果我们能够通过一些算法让合并时,生成的树的深度尽可能的小,就可以优化fifind方法.
之前我们在union算法中,合并树的时候将任意的一棵树连接到了另外一棵树,这种合并方法是比较暴力的,如果 We record the size of each tree in the union,然后在每次合并树的时候,把较小的树连接到较大的树上,就可以减小 树的深度
只要我们保证每次合并,都能把小树合并到大树上,就能够压缩合并后新树的路径,这样就能提高fifindeffectiveness of the method 率.为了完成这个需求,我们需要另外一个数组来记录存储每个根结点对应的树中元素的个数,and requires some code Adjust the values ​​in the array.
public class UF_Tree_Weighted {
	//记录结点元素和该元素所的父结点
	private int[] eleAndGroup;
	//记录并查集中数据的分组个数
	private int count;
	//存储每个根结点对应的树中元素的个数
	private int[] sz;
	public UF_Tree_Weighted(int N) {
		this.count=N;
		this.eleAndGroup=new int[N];
//		/把eleAndGroup数组的索引看做是每个结点存储的元素,把eleAndGroup数组每个索引处的值看做是该 结点的父结点,那么初始化情况下,i索引处存储的值就是i
		for(int i=0;i<eleAndGroup.length;i++) {
			eleAndGroup[i]=i;
		}
		//把sz数组中所有的元素初始化为1,默认情况下,每个结点都是一个独立的树,每个树中只有一个元素
		this.sz=new int[N];
		for(int i=0;i<sz.length;i++) {
			sz[i]=1;
		}
	}
	public int count() {
		return this.count;
	}
	
	public boolean connected(int p,int q) {
		return find(p)==find(q);
	}
	public int find(int p) {
		while(true) {
			if(p==eleAndGroup[p]) {
				return p;
			}
			p=eleAndGroup[p];
		}
	}
	public void union(int p,int q) {
		int proot=find(p);
		int qroot=find(q);
		//如果p和q已经在同一个树中,则无需合并;
		if(proot==qroot) {
			return;
		}
		//如果p和q不在同一个分组,比较p所在树的元素个数和q所在树的元素个数,Merge the smaller tree into the larger tree
		if(sz[proot]<sz[qroot]) {
			//重新调整较大树的元素个数
			eleAndGroup[proot]=qroot;
			sz[qroot]+=sz[proot];
		}else {
			eleAndGroup[qroot]=proot;
			sz[proot]=sz[qroot];
		}
		//分组数量-1
		this.count--;
		
	}

}

案例-畅通工程

题目概述：
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇.省政府“畅通工程”的目 The goal is to enable transportation between any two towns in the province（但不一定有直接的道路相连,只要互相间接通过道路可达即可）.问 At least how many roads need to be built？
在我们的测试数据文件夹中有一个trffiffiffic_project.txt文件,它就是诚征道路统计表,下面是对数据的解释：

总共有20个城市,目前已经修改好了7条道路,问还需要修建多少条道路,才能让这20个城市之间全部相通？

解题思路：
1.创建一个并查集UF_Tree_Weighted(20);
2.分别调用union(0,1),union(6,9),union(3,8),union(5,11),union(2,12),union(6,10),union(4,8),Indicates that it has been constructed Roads connect corresponding cities;
3.如果城市全部连接起来,那么并查集中剩余的分组数目为1,所有的城市都在一个树中,所以,Just get the current one And check the number remaining in the set,减去1,就是还需要修建的道路数目;
代码实现
public class Traffic_Project_Test {

	public static void main(String[] args) throws IOException{
		BufferedReader br=new BufferedReader(new InputStreamReader(Traffic_Project.class.getClassLoader().getResourceAsStream("traffic_projec t.txt")));
        读取城市数目,初始化并查集
		int totalNumber=Integer.parseInt(br.readLine());
		UF_Tree_Weighted uf=new UF_Tree_Weighted(totalNumber);
        //读取已经修建好的道路数目
		int roadNumber=Integer.parseInt(br.readLine());
    //循环读取已经修建好的道路,并调用union方法
		for(int i=0;i<roadNumber;i++) {
			String line=br.readLine();
			String[] s=line.split(" ");
			int p=Integer.parseInt(s[0]);
			int q=Integer.parseInt(s[1]);
			uf.union(p, q);
		}
    //At least the number of roads that need to be built=获取剩余的分组数量-1;
		int roads=uf.count()-1;
		System.out.println("还需要修建"+roads+"to smooth the project");
	}

}

And the explanation of the collection is over here,Then see you next time！！！

活动地址：CSDN21天学习挑战赛

原网站

版权声明
本文为[cbys-1357]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/222/202208100529245542.html

边栏推荐

猜你喜欢

随机推荐