最小全域木を求める二つの方法について
例えば日本みたいにたくさんの島があって、それら全ての島を車で往来できるように橋をかけたい。ただし、島A→島B→島C→島Aみたいにループするようには橋をかけないものとする。このような橋の作り方をグラフ理論では全域木(spanning tree)と呼び、特にその橋の合計距離が最短なものを最小全域木(minimum spanning tree, MST)と呼ぶ。考えればすぐわかると思うけど、島の数が N 個の場合、N-1本の橋をかけると全域木ができる。また効率よく最小全域木を求める方法としては、PrimのアルゴリズムとKruskalのアルゴリズムがとっても有名だ。オススメの説明は↓。
PrimとKruskalの違いを簡単に言えば、頂点と辺のどちらをメインに扱うか？にある。Primは全頂点を消化しようとするし、Kruskalは全辺を消化しようとする。それぞれの終了条件なんかそれをシンプルに表してる。このことから↓が感覚的に理解できるはず。
- 密グラフ（頂点数に比べて辺数が多め）であればPrimのほうが速く完了しやすそう。
- 疎グラフ（頂点数に比べて辺数が少なめ）であればKruskalのほうが速く完了しやすそう。
で、実際にオーダーを比べると、Primが O(V^2) でKruskalが O(ElogE) となる。ただし V,E はそれぞれ頂点数・辺数である。密グラフでは E≒V^2 で疎グラフでは E≒V と大雑把に考えると、それぞれの得意な状況っていうのが分かりやすい。ただ、ここで述べたオーダーは素直な実装の場合で、各種データ構造などを工夫することで、それぞれがもっと高速なオーダーになることには注意してほしい。
両者の使い分けについて述べてある記事が少ないようなので書いてみました。ただのニュアンスの説明ですが、ご参考になれば幸い。
