最小全域木

最大流問題

最小全域木 †

このページは競技プログラミングに興味のある方向けに最小全域木を簡単に説明するページです

最小全域木 †

ある重み付き連結グラフ(辺にコストが設定されている)から適当に辺を削除し
「連結グラフであることを維持しつつ辺に設定されているコストの総和が最小となるように操作した時の連結グラフ」 を最小全域木といいます

求め方(クラスカル法) †

クラスカル法と呼ばれる手法で求められます。これは以下の貪欲法です

1.全ての辺のフラグをOFFにする
2.与えられたグラフ内の辺をコストの小さな順にソートする。n=1にする
3.コストがn番目に小さな辺とフラグがONになっている辺とで閉路が形成されていなければ、その辺のフラグをONにする
4.フラグがONになっている辺の数 E がノード数 V に対して E = V - 1 が成立していれば終了する。そうでなけれ3に戻る

この手法であればO(E log E),O(E log V) で最小全域木を得ることが出来ます。この二つは等価です。

そのほかの求め方(プリム法) †

プリム法などが有名です。これは以下の手順をとるとり方です
1.すべてのノードのフラグをOFFにする。ノードを適当に一つ選び、選んだノードのフラグをONにする
2.フラグがONになっているノードとフラグがOFFになっているノードを結ぶ辺のうち最もコストの小さな辺を選び、
　それを結ぶノードのフラグをONにする
3.全てのノードのフラグがONなら終了する。そうでなければ2にもどる

最小全域木では辺の数 E はノード数 V に対して E = V - 1 が成立し、手順2で必ず一つのノードのフラグがONになるので
ループ回数はノード数に依存します
安直に実装すると計算量が大きくなりますが、ダイストラクト法のような手法を用いることで計算量を軽減できます