Skip to content

Commit 3b79bf0

Browse files
taokexiataokexia
committed
add UnionFindV
1 parent 6b05f21 commit 3b79bf0

4 files changed

Lines changed: 172 additions & 1 deletion

File tree

‎JavaScript/UnionFind/Test.js‎

Lines changed: 43 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
11
// 设置测试数量
2-
var n = 10000;
2+
var n = 100000;
33
// 测试并查集
44
console.log("=======================测试并查集I============================");
55
// 虽然isConnected只需要O(1)的时间，但由于union操作需要O(n)时间
@@ -58,4 +58,46 @@ for(let i = 0; i < n; i++) {
5858
uf.isConnected(a, b);
5959
}
6060
console.timeEnd('UnionFindIII');
61+
// console.log(uf.parent);
62+
63+
// 测试并查集
64+
console.log("=======================测试并查集IV============================");
65+
// 时间性能是O(n*h)的，h为并查集表达的树的最大高度
66+
// 相对III进行了优化，但优化地方出现情况较少，所以性能更优表现不明显，
67+
// 甚至在一些数据下性能会更差
68+
var UF = require('./UnionFindIV');
69+
var uf = new UF(n);
70+
console.time('UnionFindIV');
71+
for(let i = 0; i < n; i++) {
72+
let a = Math.floor(Math.random()*n);
73+
let b = Math.floor(Math.random()*n);
74+
uf.unionElements(a, b);
75+
}
76+
for(let i = 0; i < n; i++) {
77+
let a = Math.floor(Math.random()*n);
78+
let b = Math.floor(Math.random()*n);
79+
uf.isConnected(a, b);
80+
}
81+
console.timeEnd('UnionFindIV');
82+
// console.log(uf.parent);
83+
84+
// 测试并查集
85+
console.log("=======================测试并查集V============================");
86+
// 时间性能是O(n*h)的，h为并查集表达的树的最大高度
87+
// 相对III进行了优化，但优化地方出现情况较少，所以性能更优表现不明显，
88+
// 甚至在一些数据下性能会更差
89+
var UF = require('./UnionFindV');
90+
var uf = new UF(n);
91+
console.time('UnionFindV');
92+
for(let i = 0; i < n; i++) {
93+
let a = Math.floor(Math.random()*n);
94+
let b = Math.floor(Math.random()*n);
95+
uf.unionElements(a, b);
96+
}
97+
for(let i = 0; i < n; i++) {
98+
let a = Math.floor(Math.random()*n);
99+
let b = Math.floor(Math.random()*n);
100+
uf.isConnected(a, b);
101+
}
102+
console.timeEnd('UnionFindV');
61103
// console.log(uf.parent);

‎JavaScript/UnionFind/UnionFindIV.js‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
/*
2+
* 并查集
3+
* 第四版基于rank树的高度进行优化
4+
*/
5+
module.exports = class UF {
6+
constructor(count) {
7+
// rank[i] 表示以i为根的集合所表示树的层数
8+
this.rank = [];
9+
// parent[i] 表示第i个元素所指向的父节点
10+
this.parent = [];
11+
this.count = count;
12+
for(let i = 0; i < this.count; i++) {
13+
this.parent[i] = i;
14+
this.rank[i] = 1;
15+
}
16+
}
17+
// 查找过程，查找元素p所对应集合的编号
18+
// O(h)复杂度，h为树的高度
19+
find(p) {
20+
// 不断去查询自己的父亲节点，直到到达根节点
21+
// 根节点的特点：parent[p] === p
22+
while(p !== this.parent[p]) {
23+
p = this.parent[p];
24+
}
25+
return p;
26+
}
27+
// 查找元素p和元素q是否属于一个集合
28+
// O(h)复杂度，h为树的高度
29+
isConnected(p, q) {
30+
return this.find(p) === this.find(q);
31+
}
32+
// 合并元素p和元素q所属的集合
33+
// O(h)复杂度，h为树的高度
34+
unionElements(p, q) {
35+
let pRoot = this.find(p);
36+
let qRoot = this.find(q);
37+
if(pRoot === qRoot) return;
38+
// 根据两个元素所在树的元素个数不同判断合并方向
39+
// 将元素个数少的集合合并到元素个数多的集合上
40+
if(this.rank[pRoot] < this.rank[qRoot]) {
41+
this.parent[pRoot] = qRoot;
42+
} else if(this.rank[qRoot] < this.rank[pRoot]) {
43+
this.parent[qRoot] = pRoot;
44+
} else {
45+
// this.rank[qRoot] = this.rank[pRoot]
46+
this.parent[pRoot] = qRoot;
47+
this.rank[qRoot] += 1; // 此时维护rank的值,qRoot对应的树高度加1
48+
}
49+
}
50+
}

‎JavaScript/UnionFind/UnionFindV.js‎

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
/*
2+
* 并查集
3+
* 第五版采用路径压缩的方式优化:
4+
* 压缩前后及压缩最优情况：
5+
* 0->0 0->0 0->0
6+
* / / \ /|\\
7+
* 1 1 2 / | \\
8+
* / / \ 1 3 24
9+
* 2 3 4
10+
* /
11+
* 3
12+
* /
13+
* 4
14+
*/
15+
module.exports = class UF {
16+
constructor(count) {
17+
// // rank[i] 表示以i为根的集合所表示树的层数
18+
this.rank = [];
19+
this.parent = [];
20+
this.count = count;
21+
for(let i = 0; i < this.count; i++) {
22+
this.parent[i] = i;
23+
this.rank[i] = 0;
24+
}
25+
}
26+
// 查找过程，查找元素p所对应集合的编号
27+
// O(h)复杂度，h为树的高度
28+
find(p) {
29+
// 不断去查询自己的父亲节点，直到到达根节点
30+
// 根节点的特点：parent[p] === p
31+
// 路径压缩1
32+
while(p !== this.parent[p]) {
33+
// 查找的同时，压缩路径
34+
this.parent[p] = this.parent[this.parent[p]];
35+
p = this.parent[p];
36+
}
37+
return p;
38+
// 路径压缩2，递归算法，更快
39+
// if(p !== parent[p])
40+
// parent[p] = this.find(parent[p]);
41+
// return parent[p];
42+
}
43+
// 查找元素p和元素q是否属于一个集合
44+
// O(h)复杂度，h为树的高度
45+
isConnected(p, q) {
46+
return this.find(p) === this.find(q);
47+
}
48+
// 合并元素p和元素q所属的集合
49+
// O(h)复杂度，h为树的高度
50+
unionElements(p, q) {
51+
let pRoot = this.find(p);
52+
let qRoot = this.find(q);
53+
if(pRoot === qRoot) return;
54+
// 根据两个元素所在树的元素个数不同判断合并方向
55+
// 将元素个数少的集合合并到元素个数多的集合上
56+
if(this.rank[pRoot] < this.rank[qRoot]) {
57+
this.parent[pRoot] = qRoot;
58+
} else if(this.rank[qRoot] < this.rank[pRoot]) {
59+
this.parent[qRoot] = pRoot;
60+
} else {
61+
// this.rank[qRoot] = this.rank[pRoot]
62+
this.parent[pRoot] = qRoot;
63+
this.rank[qRoot] += 1; // 此时维护rank的值,qRoot对应的树高度加1
64+
}
65+
}
66+
}

‎README.md‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -24,6 +24,10 @@ JavaScript用于测试算法性能的常用方法总结:<br/>
2424
- [插入排序](./JavaScript/Sort/InsertSort.js)
2525
- [归并排序](./JavaScript/Sort/MergeSortI.js)
2626

27+
数组：
28+
29+
- [数组](./JavaScript/Array/Array.js)
30+
2731
链表：
2832

2933
- [单向链表](./JavaScript/LinkedList/LinkedList.js)
@@ -40,6 +44,15 @@ JavaScript用于测试算法性能的常用方法总结:<br/>
4044
- [二叉树I](./JavaScript/Tree/BSTI.js)
4145
- [二叉树II](./JavaScript/Tree/BSTII.js)
4246

47+
并查集:
48+
一种树形结构，下面代码逐步优化.
49+
50+
- [并查集I](./JavaScript/UnionFind/UnionFindI.js)
51+
- [并查集II](./JavaScript/UnionFind/UnionFindII.js)
52+
- [并查集III](./JavaScript/UnionFind/UnionFindIII.js)
53+
- [并查集IV](./JavaScript/UnionFind/UnionFindIV.js)
54+
- [并查集V](./JavaScript/UnionFind/UnionFindV.js)
55+
4356
经典算法：
4457

4558
- [二分查找](./JavaScript/Typical/binarySearch.js)

0 commit comments

Comments
 (0)