Skip to content

Commit dcc3135

Browse files
liuyuboboboliuyubobobo
committed
Chapter 06 Optional 01 Java code added.
1 parent 46bae3a commit dcc3135

File tree

9 files changed

+518
-0
lines changed

9 files changed

+518
-0
lines changed

‎06-Union-Find/Course Code (Java)/Optional-01-Same-Cases-Test-for-UF/src/bobo/algo/Main.java

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package bobo.algo;
2+
3+
public class Main {
4+
5+
// 对比UF1, UF2, UF3, UF4和UF5的时间性能
6+
// 在这里, 我们对于不同的UnionFind的实现, 使用相同的测试用例, 让测试结果更加准确
7+
public static void main(String[] args) {
8+
9+
// 使用1000000的数据规模
10+
int n = 1000000;
11+
12+
// 生成unionElements的测试用例
13+
Pair<Integer, Integer>[] unionTest = new Pair[n];
14+
for(int i = 0 ; i < n ; i ++){
15+
int a = (int)(Math.random()*n);
16+
int b = (int)(Math.random()*n);
17+
unionTest[i] = new Pair<Integer, Integer>(a, b);
18+
}
19+
20+
// 生成isConnected的测试用例
21+
Pair<Integer, Integer>[] connectTest = new Pair[n];
22+
for(int i = 0 ; i < n ; i ++){
23+
int a = (int)(Math.random()*n);
24+
int b = (int)(Math.random()*n);
25+
connectTest[i] = new Pair<Integer, Integer>(a, b);
26+
}
27+
28+
// 测试我们的UF1 ~ UF5
29+
30+
// 100万数据对于UF1和UF2来说太慢了, 不再测试
31+
// UnionFind1 uf1 = new UnionFind1(n);
32+
// UnionFindTestHelper.testUF("UF1", uf1, unionTest, connectTest);
33+
//
34+
// UnionFind2 uf2 = new UnionFind2(n);
35+
// UnionFindTestHelper.testUF("UF2", uf2, unionTest, connectTest);
36+
37+
UnionFind3 uf3 = new UnionFind3(n);
38+
UnionFindTestHelper.testUF("UF3", uf3, unionTest, connectTest);
39+
40+
UnionFind4 uf4 = new UnionFind4(n);
41+
UnionFindTestHelper.testUF("UF4", uf4, unionTest, connectTest);
42+
43+
UnionFind5 uf5 = new UnionFind5(n);
44+
UnionFindTestHelper.testUF("UF5", uf5, unionTest, connectTest);
45+
}
46+
}

‎06-Union-Find/Course Code (Java)/Optional-01-Same-Cases-Test-for-UF/src/bobo/algo/Pair.java

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
package bobo.algo;
2+
3+
public class Pair<A, B> {
4+
5+
private A a;
6+
private B b;
7+
8+
public Pair(A a, B b) {
9+
this.a = a;
10+
this.b = b;
11+
}
12+
13+
public A a() {
14+
return a;
15+
}
16+
17+
public B b() {
18+
return b;
19+
}
20+
}

‎06-Union-Find/Course Code (Java)/Optional-01-Same-Cases-Test-for-UF/src/bobo/algo/UF.java

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
package bobo.algo;
2+
3+
// 我们设计一个UF的接口，让不同的UF实现具体实现这个接口
4+
public interface UF {
5+
6+
public boolean isConnected( int p , int q );
7+
public void unionElements(int p, int q);
8+
}

‎06-Union-Find/Course Code (Java)/Optional-01-Same-Cases-Test-for-UF/src/bobo/algo/UnionFind1.java

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package bobo.algo;
2+
3+
// 我们的第一版Union-Find
4+
public class UnionFind1 implements UF {
5+
6+
private int[] id; // 我们的第一版Union-Find本质就是一个数组
7+
private int count; // 数据个数
8+
9+
public UnionFind1(int n) {
10+
count = n;
11+
id = new int[n];
12+
// 初始化, 每一个id[i]指向自己, 没有合并的元素
13+
for (int i = 0; i < n; i++)
14+
id[i] = i;
15+
}
16+
17+
// 查找过程, 查找元素p所对应的集合编号
18+
private int find(int p) {
19+
assert p >= 0 && p < count;
20+
return id[p];
21+
}
22+
23+
// 查看元素p和元素q是否所属一个集合
24+
// O(1)复杂度
25+
public boolean isConnected(int p, int q) {
26+
return find(p) == find(q);
27+
}
28+
29+
// 合并元素p和元素q所属的集合
30+
// O(n) 复杂度
31+
public void unionElements(int p, int q) {
32+
33+
int pID = find(p);
34+
int qID = find(q);
35+
36+
if (pID == qID)
37+
return;
38+
39+
// 合并过程需要遍历一遍所有元素, 将两个元素的所属集合编号合并
40+
for (int i = 0; i < count; i++)
41+
if (id[i] == pID)
42+
id[i] = qID;
43+
}
44+
}

‎06-Union-Find/Course Code (Java)/Optional-01-Same-Cases-Test-for-UF/src/bobo/algo/UnionFind2.java

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
package bobo.algo;
2+
3+
// 我们的第二版Union-Find
4+
public class UnionFind2 implements UF {
5+
6+
// 我们的第二版Union-Find, 使用一个数组构建一棵指向父节点的树
7+
// parent[i]表示第一个元素所指向的父节点
8+
private int[] parent;
9+
private int count; // 数据个数
10+
11+
// 构造函数
12+
public UnionFind2(int count){
13+
parent = new int[count];
14+
this.count = count;
15+
// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
16+
for( int i = 0 ; i < count ; i ++ )
17+
parent[i] = i;
18+
}
19+
20+
// 查找过程, 查找元素p所对应的集合编号
21+
// O(h)复杂度, h为树的高度
22+
private int find(int p){
23+
assert( p >= 0 && p < count );
24+
// 不断去查询自己的父亲节点, 直到到达根节点
25+
// 根节点的特点: parent[p] == p
26+
while( p != parent[p] )
27+
p = parent[p];
28+
return p;
29+
}
30+
31+
// 查看元素p和元素q是否所属一个集合
32+
// O(h)复杂度, h为树的高度
33+
public boolean isConnected( int p , int q ){
34+
return find(p) == find(q);
35+
}
36+
37+
// 合并元素p和元素q所属的集合
38+
// O(h)复杂度, h为树的高度
39+
public void unionElements(int p, int q){
40+
41+
int pRoot = find(p);
42+
int qRoot = find(q);
43+
44+
if( pRoot == qRoot )
45+
return;
46+
47+
parent[pRoot] = qRoot;
48+
}
49+
}

‎06-Union-Find/Course Code (Java)/Optional-01-Same-Cases-Test-for-UF/src/bobo/algo/UnionFind3.java

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
package bobo.algo;
2+
3+
// 我们的第三版Union-Find
4+
public class UnionFind3 implements UF {
5+
6+
private int[] parent; // parent[i]表示第一个元素所指向的父节点
7+
private int[] sz; // sz[i]表示以i为根的集合中元素个数
8+
private int count; // 数据个数
9+
10+
// 构造函数
11+
public UnionFind3(int count){
12+
parent = new int[count];
13+
sz = new int[count];
14+
this.count = count;
15+
// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
16+
for( int i = 0 ; i < count ; i ++ ){
17+
parent[i] = i;
18+
sz[i] = 1;
19+
}
20+
}
21+
22+
// 查找过程, 查找元素p所对应的集合编号
23+
// O(h)复杂度, h为树的高度
24+
private int find(int p){
25+
assert( p >= 0 && p < count );
26+
// 不断去查询自己的父亲节点, 直到到达根节点
27+
// 根节点的特点: parent[p] == p
28+
while( p != parent[p] )
29+
p = parent[p];
30+
return p;
31+
}
32+
33+
// 查看元素p和元素q是否所属一个集合
34+
// O(h)复杂度, h为树的高度
35+
public boolean isConnected( int p , int q ){
36+
return find(p) == find(q);
37+
}
38+
39+
// 合并元素p和元素q所属的集合
40+
// O(h)复杂度, h为树的高度
41+
public void unionElements(int p, int q){
42+
43+
int pRoot = find(p);
44+
int qRoot = find(q);
45+
46+
if( pRoot == qRoot )
47+
return;
48+
49+
// 根据两个元素所在树的元素个数不同判断合并方向
50+
// 将元素个数少的集合合并到元素个数多的集合上
51+
if( sz[pRoot] < sz[qRoot] ){
52+
parent[pRoot] = qRoot;
53+
sz[qRoot] += sz[pRoot];
54+
}
55+
else{
56+
parent[qRoot] = pRoot;
57+
sz[pRoot] += sz[qRoot];
58+
}
59+
}
60+
}

‎06-Union-Find/Course Code (Java)/Optional-01-Same-Cases-Test-for-UF/src/bobo/algo/UnionFind4.java

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
package bobo.algo;
2+
3+
// 我们的第四版Union-Find
4+
public class UnionFind4 implements UF {
5+
6+
private int[] rank; // rank[i]表示以i为根的集合所表示的树的层数
7+
private int[] parent; // parent[i]表示第i个元素所指向的父节点
8+
private int count; // 数据个数
9+
10+
// 构造函数
11+
public UnionFind4(int count){
12+
rank = new int[count];
13+
parent = new int[count];
14+
this.count = count;
15+
// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
16+
for( int i = 0 ; i < count ; i ++ ){
17+
parent[i] = i;
18+
rank[i] = 1;
19+
}
20+
}
21+
22+
// 查找过程, 查找元素p所对应的集合编号
23+
// O(h)复杂度, h为树的高度
24+
private int find(int p){
25+
assert( p >= 0 && p < count );
26+
// 不断去查询自己的父亲节点, 直到到达根节点
27+
// 根节点的特点: parent[p] == p
28+
while( p != parent[p] )
29+
p = parent[p];
30+
return p;
31+
}
32+
33+
// 查看元素p和元素q是否所属一个集合
34+
// O(h)复杂度, h为树的高度
35+
public boolean isConnected( int p , int q ){
36+
return find(p) == find(q);
37+
}
38+
39+
// 合并元素p和元素q所属的集合
40+
// O(h)复杂度, h为树的高度
41+
public void unionElements(int p, int q){
42+
43+
int pRoot = find(p);
44+
int qRoot = find(q);
45+
46+
if( pRoot == qRoot )
47+
return;
48+
49+
// 根据两个元素所在树的元素个数不同判断合并方向
50+
// 将元素个数少的集合合并到元素个数多的集合上
51+
if( rank[pRoot] < rank[qRoot] ){
52+
parent[pRoot] = qRoot;
53+
}
54+
else if( rank[qRoot] < rank[pRoot]){
55+
parent[qRoot] = pRoot;
56+
}
57+
else{ // rank[pRoot] == rank[qRoot]
58+
parent[pRoot] = qRoot;
59+
rank[qRoot] += 1; // 此时, 我维护rank的值
60+
}
61+
}
62+
}

‎06-Union-Find/Course Code (Java)/Optional-01-Same-Cases-Test-for-UF/src/bobo/algo/UnionFind5.java

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
package bobo.algo;
2+
3+
// 我们的第五版Union-Find
4+
public class UnionFind5 implements UF {
5+
6+
// rank[i]表示以i为根的集合所表示的树的层数
7+
// 在后续的代码中, 我们并不会维护rank的语意, 也就是rank的值在路径压缩的过程中, 有可能不在是树的层数值
8+
// 这也是我们的rank不叫height或者depth的原因, 他只是作为比较的一个标准
9+
// 关于这个问题，可以参考问答区：http://coding.imooc.com/learn/questiondetail/7287.html
10+
private int[] rank;
11+
private int[] parent; // parent[i]表示第i个元素所指向的父节点
12+
private int count; // 数据个数
13+
14+
// 构造函数
15+
public UnionFind5(int count){
16+
rank = new int[count];
17+
parent = new int[count];
18+
this.count = count;
19+
// 初始化, 每一个parent[i]指向自己, 表示每一个元素自己自成一个集合
20+
for( int i = 0 ; i < count ; i ++ ){
21+
parent[i] = i;
22+
rank[i] = 1;
23+
}
24+
}
25+
26+
// 查找过程, 查找元素p所对应的集合编号
27+
// O(h)复杂度, h为树的高度
28+
private int find(int p){
29+
assert( p >= 0 && p < count );
30+
31+
// path compression 1
32+
while( p != parent[p] ){
33+
parent[p] = parent[parent[p]];
34+
p = parent[p];
35+
}
36+
return p;
37+
38+
// path compression 2, 递归算法
39+
// if( p != parent[p] )
40+
// parent[p] = find( parent[p] );
41+
// return parent[p];
42+
}
43+
44+
// 查看元素p和元素q是否所属一个集合
45+
// O(h)复杂度, h为树的高度
46+
public boolean isConnected( int p , int q ){
47+
return find(p) == find(q);
48+
}
49+
50+
// 合并元素p和元素q所属的集合
51+
// O(h)复杂度, h为树的高度
52+
public void unionElements(int p, int q){
53+
54+
int pRoot = find(p);
55+
int qRoot = find(q);
56+
57+
if( pRoot == qRoot )
58+
return;
59+
60+
// 根据两个元素所在树的元素个数不同判断合并方向
61+
// 将元素个数少的集合合并到元素个数多的集合上
62+
if( rank[pRoot] < rank[qRoot] ){
63+
parent[pRoot] = qRoot;
64+
}
65+
else if( rank[qRoot] < rank[pRoot]){
66+
parent[qRoot] = pRoot;
67+
}
68+
else{ // rank[pRoot] == rank[qRoot]
69+
parent[pRoot] = qRoot;
70+
rank[qRoot] += 1; // 此时, 我维护rank的值
71+
}
72+
}
73+
}

0 commit comments

Comments
 (0)