最小全域木問題

今度は最小全域木問題に関してまとめてみます。

まず、最小全域木問題を解くには2つの方法が知られています。

1.プリム法
2.クラスカル法

1.プリム法

これはダイクストラ法と似ていて、O(ElogV)のアルゴリズムです。
ある頂点群Vの部分集合であるXとXの補集合を結ぶ辺で最小コストのものを順々にくっつけていくだけです。Xに属さない頂点のうちXからの辺コストが最小になる頂点を探します。そうしたらその頂点を集合Xに追加し、そこからつながる頂点へのコストを更新します。たったそれだけです。

2.クラスカル法

これは少しアルゴリズムが変わるだけでほとんどプリム法と同じですね。まず辺をソートし、閉路ができなければ部分集合Xに追加していきます。同じ連結成分かどうかはUnionFindで管理してあげれば楽でしょう。

次は最大フロー最小カットだ！(昔心折れた)