Union-Find并查集
并查集的作用
并查集主要用來解決集合類的問題，集合間的連通性問題
并查集的實(shí)現(xiàn)
主要有兩個(gè)操作
find：查詢節(jié)點(diǎn)所在的集合
merge：合并兩個(gè)節(jié)點(diǎn)所在的集合
方案A:quick find
用數(shù)組存儲每個(gè)索引對應(yīng)的集合，數(shù)組的值就是集合的名稱代表。
時(shí)間復(fù)雜度
查找：O(1)
合并：O(n)
function Unionfind(n) {
this.data = new Array(n)
//初始化每個(gè)節(jié)點(diǎn)的值為自己，每個(gè)不同的值都是一個(gè)集合
for (let i = 0; i < n; i++) {
this.data[i] = i
}
}
// 查找所在集合
Unionfind.prototype.find = function (i) {
return this.data[i]
}
// 合并集合
Unionfind.prototype.merge = function (x, y) {
let UnionX = this.data[x]
let UnionY = this.data[y]
if (UnionX == UnionY) {
return
}
// 數(shù)組內(nèi)：集合為X的節(jié)點(diǎn)都變成Y
for (let i = 0; i < this.data.length; i++) {
this.data[i] == UnionX && (this.data[i] = UnionY)
}
}
方案B:quick union
將各個(gè)集合抽象成倒著的樹，每個(gè)兒子節(jié)點(diǎn)指向父親節(jié)點(diǎn)，根節(jié)點(diǎn)指向自己
即根節(jié)點(diǎn)data[i] = i，兒子節(jié)點(diǎn)data[i] = fatherIndex
image.png
function Unionfind(n) {
this.data = new Array(n)
//倒著的樹，兒子指向父親。根節(jié)點(diǎn)指向自己
//初始時(shí)都是獨(dú)立的樹，都是根節(jié)點(diǎn)，都指向自己
for (let i = 0; i < n; i++) {
this.data[i] = i
}
}
// 查找所在集合，需要一直查，直到指向自己
Unionfind.prototype.find = function (i) {
let root = i
while (this.data[root] !== root) {
root = this.data[root]
}
return root
}
// 合并集合
Unionfind.prototype.merge = function (x, y) {
let UnionX = this.find(x)
let UnionY = this.find(y)
if (UnionX == UnionY) {
return
}
// 集合X的root指向y集合根節(jié)點(diǎn)，所有的節(jié)點(diǎn)都掛到y(tǒng)節(jié)點(diǎn)上了，y節(jié)點(diǎn)的根節(jié)點(diǎn)稱為兩個(gè)集合的根節(jié)點(diǎn)
this.data[x] = UnionY
}
方案B的優(yōu)化
一：帶權(quán)合并
在執(zhí)行merge時(shí)，上個(gè)實(shí)現(xiàn)是無規(guī)則的將兩個(gè)樹合并成一個(gè)。
我們可以優(yōu)化：掛載時(shí)將少的節(jié)點(diǎn)樹掛到多的節(jié)點(diǎn)樹上，這樣合并后較少的節(jié)點(diǎn)多個(gè)一個(gè)父級。（另一種思路是將樹高低的合入樹高高的）
二：路徑壓縮
樹的合并極端情況下會合并成為一個(gè)鏈表，查找根節(jié)點(diǎn)遍歷次數(shù)很多，
可以在每次find操作時(shí)，直接將遇到的節(jié)點(diǎn)都指向根節(jié)點(diǎn)，減少后面查找根節(jié)點(diǎn)的遍歷次數(shù)。
路徑壓縮示意圖：
image.png
function Unionfind(n) {
this.data = new Array(n)
// 增加一個(gè)以i為根節(jié)點(diǎn)的樹的節(jié)點(diǎn)數(shù)量，初始都為1
this.treeSize = new Array(n).fill(1)
for (let i = 0; i < n; i++) {
this.data[i] = i
}
}
// 查找所在集合，需要一直查，直到指向自己
Unionfind.prototype.find = function (i) {
let root = i
while (this.data[root] !== root) {
root = this.data[root]
}
//路徑壓縮：將遍歷時(shí)遇到的各層節(jié)點(diǎn)都直接指向根節(jié)點(diǎn)
while (this.data[i] !== root) {
let t = i
i = this.data[i]
this.data[t] = root
}
return root
}
// 合并集合
Unionfind.prototype.merge = function (x, y) {
let UnionX = this.find(x)
let UnionY = this.find(y)
if (UnionX == UnionY) {
return
}
// 帶權(quán)合并：
// 掛載時(shí)將少的節(jié)點(diǎn)樹掛到多的節(jié)點(diǎn)樹上，這樣較少的節(jié)點(diǎn)多一個(gè)父級
if (this.treeSize[UnionX] < this.treeSize[UnionY]) {
this.data[UnionX] = UnionY
this.treeSize[y] = this.treeSize[x] + this.treeSize[y]
} else {
this.data[UnionY] = UnionX
this.treeSize[x] = this.treeSize[x] + this.treeSize[y]
}
}
