競プロ用ライブラリを作る Advent Calendar 2024の5日目です.
Kruskal法って?
$V$頂点$E$辺の重み付き無向グラフが与えられたとき, その最小全域木を$O(E\log V)$で構築するアルゴリズムです.
グラフが連結でない場合は最小全域森(連結成分それぞれで最小全域木作ったやつ)が求まります.
$O(E\alpha(V))$のアルゴリズムもあるらしいですが, 実装してる人を見たことが無いです.
仕組み
- 全ての辺をコスト順にソートします
- 辺のコストが小さい順に「その辺の頂点2つがまだ連結でないならばその辺を追加する」という操作を行います
これだけで最終的に最小全域木が完成します
正当性を証明しましょう. まず, 以下の命題を示します.
自己辺のない連結なグラフ$G$を考え, $G$のコストが最小の辺の中から任意に1つ選んで$e_\text{min}$と置くと, $e_\text{min}$を含む$G$の最小全域木が存在する.
グラフ$G$の最小全域木を1つ選びます. この全域木が$e_\text{min}$を含んでいたなら命題は正しいので, 以下含んでいなかった場合を考えます.
全域木なので, 木に含まれない辺$e_\text{min}$を付け加えると必ず閉路が生まれます. 自己辺が無いと仮定しているのでこの閉路は2つ以上の辺からなり, つまり$e_\text{min}$以外の辺を持ちます.
この閉路から$e_\text{min}$以外の辺を1つ選んで消してみます. 閉路から辺を1つ取り除いても連結性は保たれるので, これは全域木になります.
この全域木のコスト総和を考えると, $e_\text{min}$がコスト最小の辺だったことから最初の最小全域木よりもコストが大きくなることはありません. (閉路がコストの大きさが同じ辺だけで構成されていたと分かります)
よって新しい全域木は最小全域木になり, 辺$e_\text{min}$を含む最小全域木が必ず存在すると分かりました.
という訳で最小の辺を追加します. そして, 繋いだ2つの頂点をくっつけて1つの頂点と見做してしまいます. すると, 同じ議論が適用できるようになり, 別のコストが最小の辺を追加できます. これを繰り返して辺を追加していく事で最小全域木を作ることができます.
繋いだ頂点をくっつけると自己辺が生まれることがありますが,「連結でないなら辺を追加する」という風に条件付けすることで自己辺を無視するようにできています.
実装
やるだけです. UnionFindを既に実装しているので十数行くらいで書けました. ライブラリ化する意味...
まとめ
いかがでしたか?
明日は競プロライブラリと言えばのModIntを実装します.