Java 代码实现并查集_并查集 java代码

Java 代码实现并查集

并查集表示：用树的形式表示，采用双亲表示法。根结点的双亲节点设置为-1.那么整个集合就可以用一个数组表示，数组中的元素可以设置为数组的下标。

1、并查集结点类

/*
 * 并查集结点的实现
 */
public class UFSetNode {
	int parent;		// 当前结点的双亲节点，初始化为-1
	int number;		// 以当前结点为根的子树的结点个数，初始化为1
	
	// 构造函数
	public UFSetNode () {
		parent = -1;
		number = 1;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2、并查集的实现
（1）、在集合中查找元素x的根结点
由于并查集采用的表示方法是树的形式，并且采用双亲表示法。那么在查找的时候就应该从叶子结点开始向上查找直到到达根结点。
并查集的简单查找算法：

	/*
	 * 查找某个元素的子集根结点
	 */
	public int getParent (int x) {
		while (nodes[x].parent != -1) {
			x = nodes[x].parent;
		}
		return x;
	}
1
2
3
4
5
6
7
8
9

在实际的并查集的实现过程中，树的深度是影响速度的一个重要因素，树的深度越小，查找越快，合并也就越快。（在并查集中，不在乎父子结点的层次关系，只需要能够通过父亲更快的找到根结点即可）。所以，一种优化策略是：在查找元素的过程中，将路径上的所有结点都变成根结点的儿子。
优化后的并查集查找算法

	/*
	 * 查找某个元素所在的子集的根结点改进版
	 */
	public int mix_getParent (int x) {
		int i = x;
		while (nodes[x].parent != -1) {
			x = nodes[x].parent;
		}
		
		if (x != i) {
			while (nodes[i].parent != x) {
				int temp = nodes[i].parent;
				nodes[i].parent = x;
				i = temp;
			}
		}
		return x;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

（2）、合并两个子集
基本思想：先找到两个元素所在集合的根结点，将其中一个根结点的双亲设置为另一个根结点即可。同时需要将根结点的number进行累计。

	/*
	 * 合并两个元素所在的子集
	 */
	public void unionSet (int x, int y) {
		int parentX = mix_getParent(x);
		int parentY = mix_getParent(y);
		
		if (parentX != parentY) {
			if (nodes[parentX].number < nodes[parentY].number) {
				nodes[parentY].parent = parentX;
				nodes[parentX].number += nodes[parentY].number;
			} else {
				nodes[parentX].parent = parentY;
				nodes[parentY].number += nodes[parentX].number;
			}
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3、整个集合中有多少个非空子集
遍历整个集合，统计双亲为-1 的结点数量

	/*
	 * 查看当前并查集中的非空子集有多少个
	 */
	public int getNonNullSet () {
		int num = 0;
		for (int i = 1; i < nodes.length; i++) {
			if (nodes[i].parent == -1) {
				num++;
			}
		}
		
		return num;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13

4、得到元素所在集合的元素数量
在这里，元素数量是记录在集合的根结点的number值中，只需要对其输出即可。

	/*
	 * 得到当前元素所在的子集中的元素数量
	 */
	public int getNumber (int x) {
		return nodes[getParent(x)].number;
	}
1
2
3
4
5
6

5、测试程序及运行结果显示

	public static void main(String[] args) {
		int max = 10;
		UFSet ufSet = new UFSet(max);
		// 下面的操作表示两个结点之间有父子关系，需要将其合并
		ufSet.unionSet(1, 7);
		ufSet.unionSet(1, 8);
		ufSet.unionSet(1, 9);
		ufSet.unionSet(2, 5);
		ufSet.unionSet(10, 5);
		ufSet.unionSet(5, 4);
		ufSet.unionSet(4, 3);
		ufSet.unionSet(6, 3);
		int number = ufSet.getNonNullSet();
		System.out.println(number);
		
		System.out.println(ufSet.getNumber(7));
		System.out.println(ufSet.getNumber(5));
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

运行结果：

2
4
6
1
2
3

解释：有两个不相交的子集，一个的元素个数是4，另一个是6

完整代码：

public class UFSet {
	UFSetNode[] nodes;		// 保存所有的结点
	
	/*
	 * 构造函数
	 */
	public UFSet (int max) {
		nodes = new UFSetNode[max+1];
		
		// 对申请的空间进行初始化
		for (int i = 1; i <= max; i++) {
			nodes[i] = new UFSetNode();
		}
// 测试代码之用		
//		nodes[0].parent = -1;
//		nodes[1].parent = 4;
//		nodes[2].parent = -1;
//		nodes[3].parent = 2;
//		nodes[4].parent = 3;
	}
	
	/*
	 * 合并两个元素所在的子集
	 */
	public void unionSet (int x, int y) {
		int parentX = mix_getParent(x);
		int parentY = mix_getParent(y);
		
		if (parentX != parentY) {
			if (nodes[parentX].number < nodes[parentY].number) {
				nodes[parentY].parent = parentX;
				nodes[parentX].number += nodes[parentY].number;
			} else {
				nodes[parentX].parent = parentY;
				nodes[parentY].number += nodes[parentX].number;
			}
		}
	}
	
	/*
	 * 查找某个元素的子集根结点
	 */
	public int getParent (int x) {
		while (nodes[x].parent != -1) {
			x = nodes[x].parent;
		}
		return x;
	}
	
	/*
	 * 查找某个元素所在的子集的根结点改进版
	 */
	public int mix_getParent (int x) {
		int i = x;
		while (nodes[x].parent != -1) {
			x = nodes[x].parent;
		}
		
		if (x != i) {
			while (nodes[i].parent != x) {
				int temp = nodes[i].parent;
				nodes[i].parent = x;
				i = temp;
			}
		}
		return x;
	}
	
	/*
	 * 查看当前并查集中的非空子集有多少个
	 */
	public int getNonNullSet () {
		int num = 0;
		for (int i = 1; i < nodes.length; i++) {
			if (nodes[i].parent == -1) {
				num++;
			}
		}
		
		return num;
	}
	
	/*
	 * 得到当前元素所在的子集中的元素数量
	 */
	public int getNumber (int x) {
		return nodes[getParent(x)].number;
	}
	
	/*
	 * 主函数 测试
	 */
	public static void main(String[] args) {
		int max = 10;
		UFSet ufSet = new UFSet(max);
//		int parentX = ufSet.getParent(4);
//		System.out.println(parentX);
//		int parentX = ufSet.mix_getParent(4);
//		System.out.println(parentX);
		ufSet.unionSet(1, 7);
		ufSet.unionSet(1, 8);
		ufSet.unionSet(1, 9);
		ufSet.unionSet(2, 5);
		ufSet.unionSet(10, 5);
		ufSet.unionSet(5, 4);
		ufSet.unionSet(4, 3);
		ufSet.unionSet(6, 3);
		int number = ufSet.getNonNullSet();
		System.out.println(number);
		
//		int parentX = ufSet.mix_getParent(5);
//		System.out.println(parentX);
		
		System.out.println(ufSet.getNumber(7));
		System.out.println(ufSet.getNumber(5));
	}
}

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118