プリム法
キーワード
概要
連結無向グラフの最小全域木を求めるアルゴリズム。
探索済みの頂点と未確定の頂点を単点に持つ辺のなかで、最もコストが小さい辺を選択し、その先の頂点を探索済みとする。これを全ての頂点が探索済みになるまで繰り返す。
最小の辺を選択するためには、優先度付きキューを用いる。
点が確定するたびに、その点から出る辺のうち、未確定の点に向かう辺を優先度付きキューに追加する。
計算量
応用例
実装
func main() {
var n, m int
scanIntVariables(&n, &m)
G := make([][][2]int, n+1)
for i := 0; i < m; i++ {
var a, b, c int
scanIntVariables(&a, &b, &c)
G[a] = append(G[a], [2]int{b, c})
G[b] = append(G[b], [2]int{a, c})
}
U := make(map[int]bool)
U[1] = true
q := priorityqueue.New[[2]int](func(a, b [2]int) int {
return a[1] - b[1]
})
for _, e := range G[1] {
q.Push(e)
}
ans := 0
for len(U) < n {
E := q.Pop()
u, w := E[0], E[1]
if U[u] {
continue
}
U[u] = true
ans += w
for _, e := range G[u] {
if U[e[0]] {
continue
}
q.Push(e)
}
}
writeLine(ans)
}