quick-find法焰、quick-union、加權quick-union(附帶路徑壓縮優(yōu)化)
本算法主要解決動態(tài)連通性一類問題倔毙，這里盡量用精煉簡潔的話來闡述埃仪。
數(shù)據(jù)結構描述:
- 有N個節(jié)點（索引0~N-1），可以查詢節(jié)點數(shù)量
- 可以連接兩個節(jié)點
- 可以查詢兩個節(jié)點是否連通
算法大致設計思路：
- 每個節(jié)點初始化為不同的整數(shù)標記
- 通過一個輔助函數(shù)查詢某個節(jié)點的標記值
- 如果兩節(jié)點標記相同陕赃，說明兩節(jié)點是連通的
用一個包專門處理union-find算法(unionfind)
定義接口和基類(union_find.go)：
package unionfind
//union-find的quick-find實現(xiàn)版
type QuickFind struct {
BaseUnionFind
}
func (qf *QuickFind) Connected(p, q int) bool {
return qf.id[p] == qf.id[q]
}
func (qf *QuickFind) Union(p, q int) {
i, j := qf.id[p], qf.id[q]
if i == j {
return
}
for k, v := range qf.id {
if v == j {
qf.id[k] = i
}
}
qf.count--
}
func NewQuickFind(n int) *QuickFind {
return &QuickFind{*NewBaseUnionFind(n)}
}
QuickFind
- a和b進行union的時候颁股，將b及與b連通節(jié)點的標記都置為和a的標記一樣
- 標記相同的節(jié)點是連通的
quick_find.go:
package unionfind
//union-find的quick-find實現(xiàn)版
type QuickFind struct {
BaseUnionFind
}
func (qf *QuickFind) Connected(i, j int) bool {
return qf.id[i] == qf.id[j]
}
func (qf *QuickFind) Union(i, j int) {
c := qf.id[j]
for k, v := range qf.id {
if v == c {
qf.id[k] = qf.id[i]
}
}
qf.count--
}
func NewQuickFind(n int) *QuickFind {
return &QuickFind{*NewBaseUnionFind(n)}
}
QuickUnion
- 連通的節(jié)點形成一棵樹毙玻，根節(jié)點相同
quick_union.go:
package unionfind
//union-find的quick-union實現(xiàn)版
type QuickUnion struct {
BaseUnionFind
}
//查詢根節(jié)點
func (qu *QuickUnion) findRoot(p int) int {
for p != qu.id[p] {
p = qu.id[p]
}
return p
}
func (qu *QuickUnion) Connected(p, q int) bool {
return qu.findRoot(p) == qu.findRoot(q)
}
func (qu *QuickUnion) Union(p, q int) {
rp := qu.findRoot(p)
rq := qu.findRoot(q)
if rp == rq {
return
}
qu.id[rq] = rp
qu.count--
}
func NewQuickUnion(n int) *QuickUnion {
return &QuickUnion{*NewBaseUnionFind(n)}
}
加權QuickUnion(附帶路徑壓縮優(yōu)化):
- union的時候小樹掛在大樹下
- 查詢根節(jié)點的時候順便將該節(jié)點的父節(jié)點直接指向根節(jié)點廊散，壓縮路徑
weighted_quick_union.go:
package unionfind
//union-find的加權quick-union實現(xiàn)版桑滩，
//另外還作了路徑壓縮優(yōu)化
type WeightedQuickUnion struct {
QuickUnion
sz []int
}
//查詢根節(jié)點，順便壓縮路徑
func (wqu *WeightedQuickUnion) findRoot(p int) int {
for p != wqu.id[p] {
wqu.id[p] = wqu.id[wqu.id[p]]
p = wqu.id[p]
}
return p
}
func (wqu *WeightedQuickUnion) Union(p, q int) {
rp := wqu.findRoot(p)
rq := wqu.findRoot(q)
if rp == rq {
return
}
if wqu.sz[rp] < wqu.sz[rq] {
wqu.id[rp] = rq
wqu.sz[rq] += wqu.sz[rp]
} else {
wqu.id[rp] = rq
wqu.sz[rp] += wqu.sz[rq]
}
wqu.count--
}
func NewWeightedQuickUnion(n int) *WeightedQuickUnion {
sz := make([]int, n)
for i := 0; i < n; i++ {
sz[i] = 1
}
return &WeightedQuickUnion{QuickUnion:*NewQuickUnion(n), sz: sz}
}
