并查集的实现

并查集 就是只有合并和 查找操作的一种数据结构 很简单，主要判断一个元素是否在一个集合里 主要应用在最小生成树（Kruskal算法)，看到图的时候会将实现代码贴上 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
package chapter8;
/**
 * 类名：DisjSets 说明：实现并查集 按高度求并，路径压缩 s[i]代表i的父节点
 */
public class DisjSets {
	public DisjSets(int numElements) {
		s = new int[numElements];
		for (int i = 0; i < numElements; i++)
			s[i] = -1;
	}
	/**
	 * 方法名：union1 说明：将root2的父节点指为root1
	 */
	public void union1(int root1, int root2) {
		s[root2] = root1;
	}
	/**
	 * 方法名：union2 说明：按高度求并
	 */
	public void union2(int root1, int root2) {
		root1 = find(root1);
		root2 = find(root2);
		if(root1 == root2)
			return;
		else{
			//root1的高度大于 root2的 则将root2成为root1的子树
			if(s[root1] > s[root2])
				s[root2] = root1;
			else{
				if(s[root1] == s[root2])
					s[root2]++;
				s[root1] = root2;
			}
			
		}
	}
	/**
	 * 方法名：union3 说明：按树的大小来合并，每个根的数组元素就是它包含树的大小的负值
	 */
	public void union3(int root1, int root2) {
		root1 = find(root1);
		root2 = find(root2);
		if (root1 == root2)
			return;
		else {
			// s[root1]< s[root2]说明 root1树大 将root2成为它的子树
			if (s[root1] < s[root2]) {
				s[root2] = root1;
				s[root1] += s[root2];//更新根节点
			} else
				s[root1] = root2;
				s[root2] += s[root1] + s[root2];
		}
	}
	/**
	 * 方法名：find 说明：实现路径压缩 只是加了简单的一步 将s[x]指向不断递归所得到的根
	 */
	public int find(int x) {
		if (s[x] < 0)
			return x;
		else
			return s[x] = find(s[x]);
	}
	private int[] s;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
	}
}