不相交集合（并查集）

不相交集合（两集合中没有相交元素），因为只能 进行合并和查找所求元素所在的集合，因此被称为并查集，至于怎么标志哪一个集合，可以使用集合的头结点（使用链表表示并查集），若果返回的元素一样则表示为同一个集合。如果使用森林表示，则用根节点代表这一个集合。只连接两个根节点即可。

这一般应用 在无向图的连通分量和一些图的算法中。

下面说明两种实现方式：

1.  不相交森林（数组实现）

森林不需要记录属于那个几个的指针，只合并根节点，在合并根节点时使用启发试的策略是按秩合并和路径压缩。

这里的秩为根节点的深度。秩小的根节点作为秩大的孩子，一个根节点可有很多孩子，是一个森林。

package Algorithms;

/**
 * 不相交集合森林  使用数组实现，单纯的使用父亲指针实现不了
 * 森林，不能找到所表示的节点，而数组可以使用下标。
 *但是可以使用链表实现。节点只有next指针，
 * @param <T>
 */
public class DisjointSet <T>{
	//不相交集合的节点定义
	private static class Node<T>
	{
		public T key;
		public int rank;
		public int p;
		public Node(T key,int rank,int p){
			this.key=key;
			this.rank=rank;
			this.p=p;
		}
	}
	private Node<T> s[];//次数组存放的元素 并不一定是一个集合中
    private int size;//数组元素的个数 
    public DisjointSet(int  eleNum){
    	size=0;
    	s=new Node[eleNum];
    } 
	/**
	 * 构造一个只含有集合，只有一个元素，存放于s中
	 */
	public void makeSet(int x,T key)
	{
		size++;
		s[x]=new Node<T>(key,0,x);
	}
    /**   合并两个元素所在的集合
     * （利用深度合并 深度小的合并到大的上，根节点深度不变，若两个跟秩一样
     * 深度要加1）
     * @param x
     * @param y
     */
    public void union(int x,int y){
    	 x=findSet(x);
    	 y=findSet(y);
    	 if(s[x].rank>s[y].rank)
    		 s[y].p=x;
    	 else
    	 {
    		 s[x].p=y;
    		 if(s[x].rank==s[y].rank)
    			 s[x].rank++;
    	 }
    }
    /**
     * 路径压缩的findSet（发现集合 的代表元素 这里为根节点）
     * 查找的时间复杂度与深度有关 ，所以不相交集合结构为森林结构，一个节点可以
     * 有多个孩子
     */
    public int  findSet(int x)
    {
    	if(s[x].p==x)
    		return x;
    	else 
            return findSet(s[x].p); 
    }
    public static void main(String args[])
    {
    	DisjointSet<Integer>ds=new DisjointSet<Integer>(2);
    	ds.makeSet(0, 0);
    	ds.makeSet(1, 1);
    	ds.union(0, 1);
    }
}

因为此实现比较简单，所以这里只是说明每个节点的结构体：

struct Node{

Node * next；//此节点的下一个元素

Node *  set；//此节点属于的集合  一般指向head指针

T  key；//元素关键字

}

struct Disjoint{

Node *head;

Node*  tail;

int   rank；//每个集合的权值

}

当使用链表实现，合并以后需要改变每个节点的指向的集合，所以为了减少时间复杂度，采用加权合并的启发试策略，这里的权为元素个数，权值小的合并到权值大的链表上。显然不如森林的效果好。