Skip to content

Commit 3ad7e9c

Browse files
hackfengJamhackfengJam
committed
完成 并查集
1 parent 8e68c7f commit 3ad7e9c

4 files changed

Lines changed: 208 additions & 8 deletions

File tree

‎UnionFind/src/Main.java‎

Lines changed: 15 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -29,20 +29,27 @@ private static double testUF(UF uf, int m) {
2929
}
3030

3131
public static void main(String[] args) {
32-
int size = 100000;
33-
int m = 100000;
32+
int size = 10000000;
33+
int m = 10000000;
3434

3535

36-
UnionFind1 uf1 = new UnionFind1(size);
37-
System.out.println("UnionFind1 : " + testUF(uf1, m) + " s");
38-
39-
40-
UnionFind2 uf2 = new UnionFind2(size);
41-
System.out.println("UnionFind2 : " + testUF(uf2, m) + " s");
36+
// UnionFind1 uf1 = new UnionFind1(size);
37+
// System.out.println("UnionFind1 : " + testUF(uf1, m) + " s");
38+
//
39+
//
40+
// UnionFind2 uf2 = new UnionFind2(size);
41+
// System.out.println("UnionFind2 : " + testUF(uf2, m) + " s");
4242

4343

4444
UnionFind3 uf3 = new UnionFind3(size);
4545
System.out.println("UnionFind3 : " + testUF(uf3, m) + " s");
4646

47+
48+
UnionFind4 uf4 = new UnionFind4(size);
49+
System.out.println("UnionFind4 : " + testUF(uf4, m) + " s");
50+
51+
UnionFind5 uf5 = new UnionFind5(size);
52+
System.out.println("UnionFind5 : " + testUF(uf5, m) + " s");
53+
4754
}
4855
}

‎UnionFind/src/UnionFind4.java‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
public class UnionFind4 implements UF {
2+
3+
private int[] parent;
4+
private int[] rank; // rank[i] 表示以i为根的集合所表示的树的层数
5+
6+
public UnionFind4(int size) {
7+
parent = new int[size];
8+
rank = new int[size];
9+
10+
for (int i = 0; i < size; i++) {
11+
parent[i] = i;
12+
rank[i] = 1;
13+
}
14+
}
15+
16+
@Override
17+
public int getSize() {
18+
return parent.length;
19+
}
20+
21+
// 查找过程，查找元素p对应的集合编号
22+
// O(h)复杂度，h为树的高度
23+
private int find(int p) {
24+
25+
if (p < 0 && p >= parent.length) {
26+
throw new IllegalArgumentException("p is out of bound");
27+
}
28+
29+
while (p != parent[p]) {
30+
p = parent[p];
31+
}
32+
return p;
33+
}
34+
35+
// 查看元素p和元素q是否所属一个集合
36+
@Override
37+
public boolean isConnected(int p, int q) {
38+
return find(p) == find(q);
39+
}
40+
41+
// 合并元素p和元素q所属的集合
42+
// O(h) 复杂度，h为树的高度
43+
@Override
44+
public void unionElements(int p, int q) {
45+
int pRoot = find(p);
46+
int qRoot = find(q);
47+
if (pRoot == qRoot) {
48+
return;
49+
}
50+
51+
// 基于 size 优化 quick union
52+
// 根据两个元素所在树的rank不同判断合并方向
53+
// 将rank低的集合合并到元素个数多的集合上
54+
if (rank[pRoot] < rank[qRoot]) {
55+
parent[pRoot] = qRoot;
56+
57+
} else if (rank[pRoot] > rank[qRoot]) {
58+
parent[qRoot] = pRoot;
59+
} else { // rank[pRoot] == rank[qRoot]
60+
parent[qRoot] = pRoot;
61+
rank[pRoot] += 1;
62+
}
63+
}
64+
}

‎UnionFind/src/UnionFind5.java‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
public class UnionFind5 implements UF {
2+
3+
private int[] parent;
4+
private int[] rank; // rank[i] 表示以i为根的集合所表示的树的层数
5+
6+
public UnionFind5(int size) {
7+
parent = new int[size];
8+
rank = new int[size];
9+
10+
for (int i = 0; i < size; i++) {
11+
parent[i] = i;
12+
rank[i] = 1;
13+
}
14+
}
15+
16+
@Override
17+
public int getSize() {
18+
return parent.length;
19+
}
20+
21+
// 查找过程，查找元素p对应的集合编号
22+
// O(h)复杂度，h为树的高度
23+
private int find(int p) {
24+
25+
if (p < 0 && p >= parent.length) {
26+
throw new IllegalArgumentException("p is out of bound");
27+
}
28+
29+
while (p != parent[p]) {
30+
parent[p] = parent[parent[p]];// 路径压缩
31+
p = parent[p];
32+
}
33+
return p;
34+
}
35+
36+
// 查看元素p和元素q是否所属一个集合
37+
@Override
38+
public boolean isConnected(int p, int q) {
39+
return find(p) == find(q);
40+
}
41+
42+
// 合并元素p和元素q所属的集合
43+
// O(h) 复杂度，h为树的高度
44+
@Override
45+
public void unionElements(int p, int q) {
46+
int pRoot = find(p);
47+
int qRoot = find(q);
48+
if (pRoot == qRoot) {
49+
return;
50+
}
51+
52+
// 基于 size 优化 quick union
53+
// 根据两个元素所在树的rank不同判断合并方向
54+
// 将rank低的集合合并到元素个数多的集合上
55+
if (rank[pRoot] < rank[qRoot]) {
56+
parent[pRoot] = qRoot;
57+
58+
} else if (rank[pRoot] > rank[qRoot]) {
59+
parent[qRoot] = pRoot;
60+
} else { // rank[pRoot] == rank[qRoot]
61+
parent[qRoot] = pRoot;
62+
rank[pRoot] += 1;
63+
}
64+
}
65+
}

‎UnionFind/src/UnionFind6.java‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
public class UnionFind6 implements UF {
2+
3+
private int[] parent;
4+
private int[] rank; // rank[i] 表示以i为根的集合所表示的树的层数
5+
6+
public UnionFind6(int size) {
7+
parent = new int[size];
8+
rank = new int[size];
9+
10+
for (int i = 0; i < size; i++) {
11+
parent[i] = i;
12+
rank[i] = 1;
13+
}
14+
}
15+
16+
@Override
17+
public int getSize() {
18+
return parent.length;
19+
}
20+
21+
// 查找过程，查找元素p对应的集合编号
22+
// O(h)复杂度，h为树的高度
23+
private int find(int p) {
24+
25+
if (p < 0 && p >= parent.length) {
26+
throw new IllegalArgumentException("p is out of bound");
27+
}
28+
29+
if (p != parent[p]) {
30+
parent[p] = find(parent[p]);
31+
}
32+
return parent[p];
33+
}
34+
35+
// 查看元素p和元素q是否所属一个集合
36+
@Override
37+
public boolean isConnected(int p, int q) {
38+
return find(p) == find(q);
39+
}
40+
41+
// 合并元素p和元素q所属的集合
42+
// O(h) 复杂度，h为树的高度
43+
@Override
44+
public void unionElements(int p, int q) {
45+
int pRoot = find(p);
46+
int qRoot = find(q);
47+
if (pRoot == qRoot) {
48+
return;
49+
}
50+
51+
// 基于 size 优化 quick union
52+
// 根据两个元素所在树的rank不同判断合并方向
53+
// 将rank低的集合合并到元素个数多的集合上
54+
if (rank[pRoot] < rank[qRoot]) {
55+
parent[pRoot] = qRoot;
56+
57+
} else if (rank[pRoot] > rank[qRoot]) {
58+
parent[qRoot] = pRoot;
59+
} else { // rank[pRoot] == rank[qRoot]
60+
parent[qRoot] = pRoot;
61+
rank[pRoot] += 1;
62+
}
63+
}
64+
}

0 commit comments

Comments
 (0)