Union-find并查集

Union-find算法

一、动态连通性

1.动态连通性问题

(1)在这里,当且仅当两个对象相连时它们才属于同一个等价类。

  p与q相连,意味着q与p相连;
  p与q相连,q与r相连,则意味着p与r相连。此时说明p,q,r是同一等价类。

(2)我们的目标是编写一个程序来过滤掉序列中无意义的整数对(两个整数均来自于同一等价类)。

(3)为了达到预期效果,我们需要设计一个 数据结构(并查集)来保存程序
已知的所有整数对的足够多的信息。

(4)若程序从输入中读取了整数对p q时,如果已知的所有整数对都不能说明p与q是相连的,那就调用union()方法并将这一对整数写入到输出中。

(5)若已知的所有整数对能说明p与q是相连的,那么程序应该忽略p q这对整数继续处理下一个整数对。

ps:连通性问题只要求我们的程序能够判别给定的整数对p q是否相连。

2. 例子

Union-find并查集_第1张图片两个连通分量。

3. 应用

(1)网络
输入的整数表示大型计算机网络中的计算机,整数对表示网络中的连接。
这个程序能够判定是否需要在p与q之间架设一条新的连接才能进行通信,
或是可以通过已有的连接在两者之间建立通信线路。
(2)数学集合

4. 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() 连通分量的数量
5.Union-find算法的实现
package Greedy;
public class UF {
		private int[] id;  //等价类id
		private int count;   //等价类数量
		
		public UF(int N)
		{
			//初始化分量id数组
			count = N;
			id = new int[N];
			for(int i=0;i<N;i++)
				id[i] = i;
		}
		
		public int count()
		{
			return count;
		}
		
		public boolean connected(int p,int q)
		{
			return find(p) == find(q);
		}
		
		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(pID == id[i])  id[i] = qID;	
		}	
}

你可能感兴趣的