🌳
クラスカル法
とは？
最小全域木 (Minimum Spanning Tree) を知りたいときに使うアルゴリズムの一つ。他にはプリム法もあるがクラスカル法のほうが人気がある。
アルゴリズム
- コストが低い辺から順に素集合森を作る
- そのときあってもなくてもいい余分な辺は捨てる (余分な辺 = 閉路になる辺)
- 必要最低限の辺だけで作ったので、使った辺のコストの合計が最小コストになる
ひとことで言えば「安い材料を使って作れば安く済むじゃん」というだけの話である。
具体例
次の路線の設計図は無駄があるので必要最低限にしたい。
| 辺 | 費用 |
|---|---|
| A-B | 3 |
| B-C | 2 |
| C-A | 1 |
↓ 安い順に並び替えてから順に作る。
| 辺 | 費用 | 考え方 | 必要 |
|---|---|---|---|
| C-A | 1 | C も A も初登場なのでいる | ○ |
| B-C | 2 | B はどことも繋がっていないのでいる | ○ |
| A-B | 3 | A-B は C 経由で繋がっているのでいらない |
すると路線図は、
となるので 1 + 2 = 3 が答えになる。
実装例
edges = [["A", "B", 3], ["B", "C", 2], ["C", "A", 1]] # => [["A", "B", 3], ["B", "C", 2], ["C", "A", 1]]
edges = edges.sort_by { |*_, cost| cost } # => [["C", "A", 1], ["B", "C", 2], ["A", "B", 3]]
ds = DisjointSet.new
total = 0
edges.each do |*edge, cost|
if ds.different?(*edge)
total += cost # => 1, 3
ds.unite(*edge)
end
end
p total # => 3
最小全域森になる場合もある
もとから辺が足りていないと木にならない。たとえば陸地の線路をうまく繋げても離島があれば繋がらない。その場合は森と呼ぶのが相応わしい。このあたり用意された辺を使うと一本の木になるのかどうか前提の情報をよく確認する。
過去問を解く
典型アルゴリズム問題集 F - 最小全域木問題
https://atcoder.jp/contests/typical-algorithm/tasks/typical_algorithm_f
コード (AC 375 ms) ※上の実装例とほぼ同じ
N, M = gets.split.collect(&:to_i) # => [5, 7]
edges = M.times.collect { gets.split.collect(&:to_i) } # => [[0, 1, 10], [0, 4, 30], [1, 2, 10], [1, 4, 20], [2, 3, 30], [4, 2, 20], [4, 3, 10]]
edges = edges.sort_by { |*_, cost| cost } # => [[0, 1, 10], [1, 2, 10], [4, 3, 10], [1, 4, 20], [4, 2, 20], [0, 4, 30], [2, 3, 30]]
ds = DisjointSet.new
total = 0
edges.each do |*edge, cost|
if ds.different?(*edge)
total += cost # => 10, 20, 30, 50
ds.unite(*edge)
end
end
p total # => 50
競技プログラミングの鉄則 演習問題集 A67 - MST
https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_bo
コード (AC 382 ms) ※上と完全に同じ
N, M = gets.split.collect(&:to_i) # => [7, 9]
edges = M.times.collect { gets.split.collect(&:to_i) } # => [[1, 2, 12], [1, 3, 10], [2, 6, 160], [2, 7, 15], [3, 4, 1], [3, 5, 4], [4, 5, 3], [4, 6, 120], [6, 7, 14]]
edges = edges.sort_by { |*_, cost| cost } # => [[3, 4, 1], [4, 5, 3], [3, 5, 4], [1, 3, 10], [1, 2, 12], [6, 7, 14], [2, 7, 15], [4, 6, 120], [2, 6, 160]]
ds = DisjointSet.new
total = 0
edges.each do |*edge, cost|
if ds.different?(*edge)
total += cost # => 1, 4, 14, 26, 40, 55
ds.unite(*edge)
end
end
p total # => 55
応用: 最大全域木
金が余ってしょうがないので、なるべく安く済ませているように見せかけて、いちばん金をかけたい場合には、「費用が高い順」に並び換えて作ればよい。
現実的な問題で言えば、ゲームのレベルデザインにおいて「コスト = 難易度」と定義し、高難易度のステージを選択したルートを自動で作りたい場合などに応用できるかもしれない。
関連
Discussion