Skip to content

Commit cad6c55

Browse files
liuyuboboboliuyubobobo
committed
Chapter UF added code to compare the difference between two Path Compression results.
1 parent 38517bc commit cad6c55

File tree

8 files changed

+468
-0
lines changed

8 files changed

+468
-0
lines changed

‎06-Union-Find/Course Code (C++)/Optional-02-Path-Compression-Comparison/CMakeLists.txt

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
cmake_minimum_required(VERSION 3.5)
2+
project(Optional_02_Path_Compression_Comparison)
3+
4+
set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11")
5+
6+
set(SOURCE_FILES main.cpp)
7+
add_executable(Optional_02_Path_Compression_Comparison ${SOURCE_FILES})

‎06-Union-Find/Course Code (C++)/Optional-02-Path-Compression-Comparison/UnionFind5.h

Lines changed: 99 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,99 @@
1+
//
2+
// Created by liuyubobobo on 6/16/17.
3+
//
4+
5+
#ifndef OPTIONAL_02_PATH_COMPRESSION_COMPARISON_UNIONFIND5_H
6+
#define OPTIONAL_02_PATH_COMPRESSION_COMPARISON_UNIONFIND5_H
7+
8+
#include <cassert>
9+
10+
using namespace std;
11+
12+
// 我们的第五版Union-Find, 路径压缩使用迭代的方式
13+
namespace UF5{
14+
15+
class UnionFind{
16+
17+
18+
public: // 后续, 我们要在外部操控并查集的数据, 在这里使用public
19+
int* parent; // parent[i]表示第i个元素所指向的父节点
20+
21+
private:
22+
// rank[i]表示以i为根的集合所表示的树的层数
23+
// 在后续的代码中, 我们并不会维护rank的语意, 也就是rank的值在路径压缩的过程中, 有可能不在是树的层数值
24+
// 这也是我们的rank不叫height或者depth的原因, 他只是作为比较的一个标准
25+
// 关于这个问题，可以参考问答区：http://coding.imooc.com/learn/questiondetail/7287.html
26+
int* rank;
27+
int count; // 数据个数
28+
29+
public:
30+
// 构造函数
31+
UnionFind(int count){
32+
parent = new int[count];
33+
rank = new int[count];
34+
this->count = count;
35+
for( int i = 0 ; i < count ; i ++ ){
36+
parent[i] = i;
37+
rank[i] = 1;
38+
}
39+
}
40+
41+
// 析构函数
42+
~UnionFind(){
43+
delete[] parent;
44+
delete[] rank;
45+
}
46+
47+
// 查找过程, 查找元素p所对应的集合编号
48+
// O(h)复杂度, h为树的高度
49+
int find(int p){
50+
assert( p >= 0 && p < count );
51+
52+
// path compression 1
53+
while( p != parent[p] ){
54+
parent[p] = parent[parent[p]];
55+
p = parent[p];
56+
}
57+
return p;
58+
}
59+
60+
// 查看元素p和元素q是否所属一个集合
61+
// O(h)复杂度, h为树的高度
62+
bool isConnected( int p , int q ){
63+
return find(p) == find(q);
64+
}
65+
66+
// 合并元素p和元素q所属的集合
67+
// O(h)复杂度, h为树的高度
68+
void unionElements(int p, int q){
69+
70+
int pRoot = find(p);
71+
int qRoot = find(q);
72+
73+
if( pRoot == qRoot )
74+
return;
75+
76+
// 根据两个元素所在树的元素个数不同判断合并方向
77+
// 将元素个数少的集合合并到元素个数多的集合上
78+
if( rank[pRoot] < rank[qRoot] ){
79+
parent[pRoot] = qRoot;
80+
}
81+
else if( rank[qRoot] < rank[pRoot]){
82+
parent[qRoot] = pRoot;
83+
}
84+
else{ // rank[pRoot] == rank[qRoot]
85+
parent[pRoot] = qRoot;
86+
rank[qRoot] += 1; // 此时, 我维护rank的值
87+
}
88+
}
89+
90+
// 打印输出并查集中的parent数据
91+
void show(){
92+
for( int i = 0 ; i < count ; i ++ )
93+
cout << parent[i] << " ";
94+
cout <<endl;
95+
}
96+
};
97+
}
98+
99+
#endif //OPTIONAL_02_PATH_COMPRESSION_COMPARISON_UNIONFIND5_H

‎06-Union-Find/Course Code (C++)/Optional-02-Path-Compression-Comparison/UnionFind6.h

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
//
2+
// Created by liuyubobobo on 6/16/17.
3+
//
4+
5+
#ifndef OPTIONAL_02_PATH_COMPRESSION_COMPARISON_UNIONFIND6_H
6+
#define OPTIONAL_02_PATH_COMPRESSION_COMPARISON_UNIONFIND6_H
7+
8+
#include <cassert>
9+
10+
using namespace std;
11+
12+
// 我们的第六版Union-Find, 路径压缩使用递归的方式
13+
namespace UF6{
14+
15+
class UnionFind{
16+
17+
public: // 后续, 我们要在外部操控并查集的数据, 在这里使用public
18+
int* parent; // parent[i]表示第i个元素所指向的父节点
19+
20+
private:
21+
// rank[i]表示以i为根的集合所表示的树的层数
22+
// 在后续的代码中, 我们并不会维护rank的语意, 也就是rank的值在路径压缩的过程中, 有可能不在是树的层数值
23+
// 这也是我们的rank不叫height或者depth的原因, 他只是作为比较的一个标准
24+
// 关于这个问题，可以参考问答区：http://coding.imooc.com/learn/questiondetail/7287.html
25+
int* rank;
26+
int count; // 数据个数
27+
28+
public:
29+
// 构造函数
30+
UnionFind(int count){
31+
parent = new int[count];
32+
rank = new int[count];
33+
this->count = count;
34+
for( int i = 0 ; i < count ; i ++ ){
35+
parent[i] = i;
36+
rank[i] = 1;
37+
}
38+
}
39+
40+
// 析构函数
41+
~UnionFind(){
42+
delete[] parent;
43+
delete[] rank;
44+
}
45+
46+
// 查找过程, 查找元素p所对应的集合编号
47+
// O(h)复杂度, h为树的高度
48+
int find(int p){
49+
assert( p >= 0 && p < count );
50+
51+
// path compression 2, 递归算法
52+
if( p != parent[p] )
53+
parent[p] = find( parent[p] );
54+
return parent[p];
55+
}
56+
57+
// 查看元素p和元素q是否所属一个集合
58+
// O(h)复杂度, h为树的高度
59+
bool isConnected( int p , int q ){
60+
return find(p) == find(q);
61+
}
62+
63+
// 合并元素p和元素q所属的集合
64+
// O(h)复杂度, h为树的高度
65+
void unionElements(int p, int q){
66+
67+
int pRoot = find(p);
68+
int qRoot = find(q);
69+
70+
if( pRoot == qRoot )
71+
return;
72+
73+
// 根据两个元素所在树的元素个数不同判断合并方向
74+
// 将元素个数少的集合合并到元素个数多的集合上
75+
if( rank[pRoot] < rank[qRoot] ){
76+
parent[pRoot] = qRoot;
77+
}
78+
else if( rank[qRoot] < rank[pRoot]){
79+
parent[qRoot] = pRoot;
80+
}
81+
else{ // rank[pRoot] == rank[qRoot]
82+
parent[pRoot] = qRoot;
83+
rank[qRoot] += 1; // 此时, 我维护rank的值
84+
}
85+
}
86+
87+
// 打印输出并查集中的parent数据
88+
void show(){
89+
for( int i = 0 ; i < count ; i ++ )
90+
cout << parent[i] << " ";
91+
cout <<endl;
92+
}
93+
};
94+
}
95+
96+
#endif //OPTIONAL_02_PATH_COMPRESSION_COMPARISON_UNIONFIND6_H

‎06-Union-Find/Course Code (C++)/Optional-02-Path-Compression-Comparison/main.cpp

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
#include <iostream>
2+
#include "UnionFind5.h"
3+
#include "UnionFind6.h"
4+
5+
using namespace std;
6+
7+
int main() {
8+
9+
// 为了能够方便地看出两种路径压缩算法的不同,我们只使用有5个元素的并查集进行试验
10+
int n = 5;
11+
12+
UF5::UnionFind uf5 = UF5::UnionFind(n);
13+
UF6::UnionFind uf6 = UF6::UnionFind(n);
14+
15+
// 我们将我们的并查集初始设置成如下的样子
16+
// 0
17+
// /
18+
// 1
19+
// /
20+
// 2
21+
// /
22+
// 3
23+
// /
24+
// 4
25+
for(int i = 1 ; i < n ; i ++){
26+
uf5.parent[i] = i-1;
27+
uf6.parent[i] = i-1;
28+
}
29+
30+
// 现在, 我们对两个并查集调用find(4)操作
31+
uf5.find(n-1);
32+
uf6.find(n-1);
33+
34+
// 通过show, 我们可以看出, 使用迭代的路径压缩, 我们的并查集变成这个样子:
35+
// 0
36+
// / \
37+
// 1 2
38+
// / \
39+
// 3 4
40+
cout << "UF implements Path Compression by recursion:" << endl;
41+
uf5.show();
42+
43+
cout << endl;
44+
45+
// 使用递归的路径压缩, 我们的并查集变成这个样子:
46+
// 0
47+
// / / \ \
48+
// 1 2 3 4
49+
cout << "UF implements Path Compression without recursion:" << endl;
50+
uf6.show();
51+
52+
53+
// 大家也可以调大n的值, 看看结果的不同:)
54+
55+
return 0;
56+
}

‎06-Union-Find/Course Code (Java)/Optional-02-Path-Compression-Comparison/src/bobo/algo/Main.java

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
package bobo.algo;
2+
3+
public class Main {
4+
5+
public static void main(String[] args) {
6+
7+
// 为了能够方便地看出两种路径压缩算法的不同,我们只使用有5个元素的并查集进行试验
8+
int n = 5;
9+
10+
UnionFind5 uf5 = new UnionFind5(n);
11+
UnionFind6 uf6 = new UnionFind6(n);
12+
13+
// 我们将我们的并查集初始设置成如下的样子
14+
// 0
15+
// /
16+
// 1
17+
// /
18+
// 2
19+
// /
20+
// 3
21+
// /
22+
// 4
23+
for(int i = 1 ; i < n ; i ++){
24+
uf5.parent[i] = i-1;
25+
uf6.parent[i] = i-1;
26+
}
27+
28+
// 现在, 我们对两个并查集调用find(4)操作
29+
uf5.find(n-1);
30+
uf6.find(n-1);
31+
32+
// 通过show, 我们可以看出, 使用迭代的路径压缩, 我们的并查集变成这个样子:
33+
// 0
34+
// / \
35+
// 1 2
36+
// / \
37+
// 3 4
38+
System.out.println("UF implements Path Compression by recursion:");
39+
uf5.show();
40+
41+
System.out.println();
42+
43+
// 使用递归的路径压缩, 我们的并查集变成这个样子:
44+
// 0
45+
// / / \ \
46+
// 1 2 3 4
47+
System.out.println("UF implements Path Compression without recursion:");
48+
uf6.show();
49+
50+
// 大家也可以调大n的值, 看看结果的不同:)
51+
}
52+
}

‎06-Union-Find/Course Code (Java)/Optional-02-Path-Compression-Comparison/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+
}

0 commit comments

Comments
 (0)