クラスカル法
キーワード
概要
連結無向グラフの最小全域木を求めるアルゴリズム。
全ての辺をコストの小さい順にソートし、閉路が生じないように順に最小全域木を求める。
閉路の判定はUnionFindを用いる。辺の両端点が同じ連結成分に属している時、閉路が生じる。
計算量
uf での比較は とみてよく、ソートにかかる時間が全体の計算量となる。
応用例
実装
func main() {
var n, m int
scanIntVariables(&n, &m)
E := make([][3]int, m)
for i := 0; i < m; i++ {
scanIntVariables(&E[i][0], &E[i][1], &E[i][2])
}
uf := newUnionFind(n+1)
sort.Slice(E, func(i, j int) bool {
return E[i][2] < E[j][2]
})
ans := 0
for _, e := range E {
if !uf.isSame(e[0], e[1]) {
uf.unite(e[0], e[1])
ans += e[2]
}
}
writeLine(ans)
}
type UnionFind struct {
n int
root []int
}
func newUnionFind(n int) UnionFind {
root := make([]int, n)
for i := 0; i < n; i++ {
root[i] = -1
}
uf := UnionFind{n: n, root: root}
return uf
}
func (u *UnionFind) find(x int) int {
if u.root[x] < 0 {
return x
}
u.root[x] = u.find(u.root[x]) // 再帰で根に直接繋ぎ直す
return u.root[x]
}
func (u *UnionFind) unite(x, y int) {
x = u.find(x) // xを根に書き換え
y = u.find(y) // yを根に書き換え
if x == y {
return
}
if -u.root[x] < -u.root[y] {
x, y = y, x
} // xの集合の要素数の方が大きいようにスワップ
u.root[x] += u.root[y]
u.root[y] = x
}
func (u *UnionFind) isSame(x, y int) bool {
return u.find(x) == u.find(y)
}
func (u *UnionFind) size(x int) int {
return -u.root[u.find(x)]
}