最小全域木からの脱線に次ぐ脱線
最小全域木というキーワードが会話に出てきて、ふと思った。
定義は想像できるけど、それを求めるアルゴリズムはわかんない。
調べてたら脱線に次ぐ脱線でいろいろ調べた。
最小全域木
あるグラフの全域木とは、与えられたグラフの頂点と辺の部分集合で作る、全ての頂点をもつ木構造のこと。
連結グラフであることと全域木の存在は同値、のはず。
ある重み付きグラフの最小全域木とは、全域木の中で辺の重みの和が最小になるもの。
全域木 - Wikipedia
プリム法
最小全域木は貪欲法で求められるらしい。
確かにそんな気がするので、ちょっと考えてみる。
テキトーに頂点選んで、そこから出ている辺で重みが一番小さいやつを選んでくっつける。
「頂点から出てる辺」を「木から出てる辺」に読み替えて繰り返せば、全域木はできる。
枝の選び方的に最小っぽい気もする。
この方法はプリム法というらしい。
最小全域木を構成できることは背理法で示すんだろうなあと思ったら、ちょっと違った。
ある最小全域木とプリム法の結果があるとき、最小全域木の性質を保ちながら前者を後者に変換できることを示してる。
プリム法 - Wikipedia
プリム法の計算量は、重みが一番小さい辺の選び方を変えることで変わってくる。
隣接行列へのランダムアクセスが定数時間でできると仮定すると、ダイクストラ法みたいに各頂点を追加したときのコストを保存しておけば、一回の木の成長がになるから全体で
になる。
もうちょっと高速にするためにヒープを使った方法があるらしいけど、詳細までは理解できていない。
二分ヒープを使ったくらいではくらいにしかならなくて、密なグラフだと上記のやり方より遅い*1。
それを改善するにはフィボナッチヒープを使う必要がある、らしい。
計算量の理解は下記の記事に助けられた。
プリム法（最小全域木問題）
クラスカル法
最小全域木を作るもう一つのアルゴリズムが、クラスカル法。
最初は頂点を別々のグループだと思って、重みの小さい辺でグループをつなげていくアルゴリズム。
ただし、すでに同じグループの頂点間には辺を追加しない（閉路ができて木ではなくなるので）。
クラスカル法 - Wikipedia
最小全域木になることの証明は背理法だった。こっちかよ。
しかもネストしてて面倒だった。
でもプリム法の証明よりは読みやすかった。
計算量は、
- 辺のリストを重み順にソートする計算量
- 二つの頂点が同じグループに属するか判定する計算量×辺の数
- グループの更新（マージ）
が関わってくるはず。
ソートはでできる。
問題は残り二つの項目だけど、これにはUnion Findというデータ構造が使える。
先に結果だけ言えば、ボトルネックがソートの部分になるので、計算量はになる
Union Find
ある二つの要素が同じグループか否かを判定できるのと、グループをまとめること（結合）ができるデータ構造。
判定の最悪計算量は要素数のオーダーだけど、何回も判定することを前提にした工夫をすると、平均的な計算量が対数オーダーより改善する（ならし計算量と呼ばれる）。
結合は要素数の対数オーダーでできるはず。
クラスカル法では、要素が個あって、
回の判定と
回の結合が必要なので、雑に抑えても
になる。
連結グラフであることを考えるとだから、クラスカル法のボトルネックは辺のソートになる。
ならし計算量（償却計算量）
何回も（同じ）操作をすることを前提として、その平均的な計算量で評価する方法。
一見うさんくさいように思えるけど、結局何回も操作するので、合計で評価しましょうと言っているだけ。
言い換えれば、一つひとつを統一のオーダーで抑えるとガバガバになるから、和を考えることで個別にできるだけ厳密な評価をしましょう、という話。
下記の記事などがわかりやすかった。
topcoder.g.hatena.ne.jp
きまぐれ日記: 動的配列への追加コストはなぜ O(1)?
平衡二分木とか、B treeとか、いろんなデータ構造が気になり始めている*2。
