算法起步之并查集（不相交集合数据结构）

         在java中经典的数据结构基本都给实现好了，我们可以直接调用，但是并查集这种数据结构却没有很好的替代工具，在这里我们我们自己去实现并查集数据结构。首先我们先要去了解什么是并查集。并查集也是一种非常经典常用的数据结构。像求连通子图跟我们下面要研究的最小生成树问题都会用到并查集。并查集就是能够实现若干个不相交集合，较快的合并和判断元素所在集合的操作。不相交集合:一个不相交集合维护了一个不相交动态集合{s1，s2，s3……}我们用一个代表标示每一个集合，他是这个集合的成员。我们不关心哪个成员作为代表，仅关心2次查询这个集合时放回结果应该相同（如果我们不修改集合）。

    并查集主要就有三个方法：

    make-set（x）建立一个新集合唯一元素就是x，因为是不相交集合所以x不会出现在其他集合中。

    union（x，y）将包含x和y的2个动态集合合并成一个新集合。

    find-set(x)返回一个指针，这个指针指向包含x的集合的代表。

    这样说是不是有点懵，我们来看一个图。

        上图两棵树就是一个不相交集合，a数的代表就是a而e树代表就是e我们在a树上查找b则返回a而查找c也返回a说明b与c在同一结合上，而查找f返回e，说明b与e是在两个结合上，他们两个是不相交的。而union操作就是将两颗树合并成一棵树。

     我们先给出一个一般的实现，数组表示不相交集合保存的各个集合的元素。初始化时：

           每个元素都指向自己的父节点也就是自己。这种方式每个节点都指向自己的上一节点。而只有代表节点指向的是自己。所以我们根据这个来搜索代表节点。

public class Ufsarry {

	
	private int[] node;
	private int max;
	public void makeset(int n){
		node=new int[n+1];
		max=n;
		//所有的节点都是不相交集合，代表节点都指向自己。
		for (int i = 0; i < node.length; i++) {
			node[i]=i;
		}
	}
	public int findset(int x){
		while (x!=node[x]) {
			x=node[x];
		}
		return x;
	}
	public void union(int x,int y){
		node[x]=y;
	}
}

            第一张图就是路径压缩，我们之前都是指向的上一节点，而压缩则是直接指向代表节点。而按秩合并则是我们外加一个属性来记录集合的秩。而秩多的则说明树比较高，我们将矮的树嫁接在高的树上，这样总的高度较小。而如果高度相同，则只需要将一个树嫁接过去，给他的秩加一即可。

public class Ufs {
	
	private int[] father;
	private int[] rank;
	
	public void makeset(int x){
		father[x]=x;
		rank[x]=0;
	}
	public int findset(int x){
		if (father[x]!=x) {
			father[x]=findset(father[x]);
		}
		return father[x];
	}
	
	public void union(int x,int y){
		x=findset(x);
		y=findset(y);
		if (x==y) {
			return;
		}else {
			if (rank[x]>rank[y]) {
				father[y]=x;
			}else{
				if (rank[x]==rank[y]) {
					rank[y]++;
				}
				father[x]=y;
			}
		}
	}


}