切换主题
并查集
本篇来手动实现JavaScript中没有的数据结构：并查集。
定义节点
首先定义包装节点结构：
JavaScript
class Ele {
constructor(ele) {
this.ele = ele
}
}初始化
该数据结构会用到三个
hashMap数据结构，为了方便描述，将值ele的包装节点new Ele(ele)记为node，node的父元素记为nodeP：
eMap：用于存放值与包装节点，即{ ele : node }；fMap：用于存放包装节点与包装节点的父节点，即{ node : nodeP }；sMap：用于存放某个集合的头节点与该集合大小，即{ node : number}。并查集是建立在数据初始化之上的，未被初始化的数据均可视为无效数据！！！
JavaScript
class UnionFindSet {
constructor(elements) {
this.eMap = new Map()
this.fMap = new Map()
this.sMap = new Map()
// 初始化
for (const ele of elements) {
const node = new Ele(ele)
this.eMap.set(ele, node)
this.fMap.set(node, node) // 父节点设为自己
this.sMap.set(node, 1)
}
}
}查找集合
JavaScript
class UnionFindSet {
// 其它逻辑
// 辅助函数
findHead(node, path = []) {
// 找到集合代表节点，即头节点
while (node != this.fmap.get(node)) {
path.push(node)
node = this.fMap.get(node)
}
// 扁平化优化
while (path.length) {
this.fMap.set(path.pop(), node)
}
// 返回头节点
return node
}
// 查找集合
isSameSet(e1, e2) {
if (this.eMap.has(e1) && this.eMap.has(e2)) {
const [n1, n2] = [this.eMap.get(e1), this.eMap.get(e2)]
return this.findHead(n1) == this.findHead(n2)
}
return false
}
}合并集合
JavaScript
class UnionFindSet {
// 其它逻辑
union(e1, e2) {
// 只管初始化后的数据
if (this.eMap.has(e1) && this.eMap.has(e2)) {
const e1P = findHead(this.eMap.get(e1))
const e2P = findHead(this.eMap.get(e2))
if (e1P != e2P) { // 头节点不一样，一定不是同一集合，故合并
const [s1, s2] = [this.sMap.get(e1P), this.sMap.get(e2P)]
const big = s1 >= s2 ? e1P : e2P
const small = big == e1P ? e2P : e1P
this.fMap.set(small, big) // 将小集合挂在大集合的下面
this.sMap.set(big, s1 + s2) // 更新集合大小
this.sMap.delete(small) // 小集合已经被合并了，需删除
}
}
}
}完整代码
查看
JavaScript
class Ele {
constructor(ele) {
this.ele = ele
}
}
class UnionFindSet {
constructor(elements) {
this.eMap = new Map()
this.fMap = new Map()
this.sMap = new Map()
// 初始化
for (const ele of elements) {
const node = new Ele(ele)
this.eMap.set(ele, node)
this.fMap.set(node, node) // 父节点设为自己
this.sMap.set(node, 1)
}
}
// 辅助函数
findHead(node, path = []) {
// 找到集合代表节点，即头节点
while (node != this.fmap.get(node)) {
path.push(node)
node = this.fMap.get(node)
}
// 扁平化优化
while (path.length) {
this.fMap.set(path.pop(), node)
}
// 返回头节点
return node
}
// 查找集合
isSameSet(e1, e2) {
if (this.eMap.has(e1) && this.eMap.has(e2)) {
const [n1, n2] = [this.eMap.get(e1), this.eMap.get(e2)]
return this.findHead(n1) == this.findHead(n2)
}
return false
}
// 合并集合
union(e1, e2) {
// 只管初始化后的数据
if (this.eMap.has(e1) && this.eMap.has(e2)) {
const e1P = findHead(this.eMap.get(e1))
const e2P = findHead(this.eMap.get(e2))
if (e1P != e2P) { // 头节点不一样，一定不是同一集合，故合并
const [s1, s2] = [this.sMap.get(e1P), this.sMap.get(e2P)]
const big = s1 >= s2 ? e1P : e2P
const small = big == e1P ? e2P : e1P
this.fMap.set(small, big) // 将小集合挂在大集合的下面
this.sMap.set(big, s1 + s2) // 更新集合大小
this.sMap.delete(small) // 小集合已经被合并了，需删除
}
}
}
}