不相交集合（并查集）

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

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

下面说明两种实现方式：

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

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

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

<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPjwvcD4KPHA+PHByZSBjbGFzcz0="brush:java;">package Algorithms; /** * 不相交集合森林 使用数组实现，单纯的使用父亲指针实现不了 * 森林，不能找到所表示的节点，而数组可以使用下标。 *但是可以使用链表实现。节点只有next指针， * @param */ public class DisjointSet { //不相交集合的节点定义 private static class Node { 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 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 (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 ds=new DisjointSet (2); ds.makeSet(0, 0); ds.makeSet(1, 1); ds.union(0, 1); } } 2.不相交集合的链表实现