最小全域木

1926年、オタカル・ブルーフカ(Otakar Borůvka)は、南モラヴィアの電力網をできるだけ安く計画するよう依頼されました。線の長さの合計を最小にしてすべての場所をつなぐにはどうすればよいか。この問いが最小全域木問題であり、コンピューターサイエンス全体でも特に簡潔で美しい解法がいくつもあります。

エッジに長さがあるグラフ。育っていく木の短いエッジが強調され、閉路ができるため飛ばしたエッジが赤い破線で示され、その下にまだ試していないエッジの一覧がある
エッジに長さがあるグラフ。育っていく木の短いエッジが強調され、閉路ができるため飛ばしたエッジが赤い破線で示され、その下にまだ試していないエッジの一覧がある

問題

エッジに長さ(コスト)がある連結グラフを考えます。全域木は、すべてのノードをつなぎ、閉路を含まないエッジの集まりです。ノードが n 個なら、エッジは必ずちょうど n − 1 本です。エッジ1本ごとにノードが1つずつつながるからです。すべての全域木のうち、長さの合計が最小のものが最小全域木です。グラフには膨大な数の全域木がありえますが、すべてを試す必要はありません。

貪欲法がうまくいく理由

ノードを好きなように2つのグループに分けます。グループ間をまたぐ最短のエッジは、必ずいずれかの最小全域木に含まれます。もし木がもっと長いまたぐエッジを使っていたら、それを短いほうに取り替えれば、同じノードをより安くつなげるからです。これがカット性質です。その裏返しが閉路性質で、どの閉路でも最も長いエッジは決して必要ありません。以下の2つのアルゴリズムは、これらの規則を当てはめ続けるだけです。

例

エッジ A–B の長さを 1、B–C を 2、A–C を 3、C–D を 4、B–D を 5 とします。クラスカル法は A–B、次に B–C を取り、A–C は飛ばします。A と C はすでにつながっていて閉路ができるからです。そして C–D を取ります。木はノード4つに対してエッジが3本なので完成で、長さの合計は 7。B–D は調べられることさえありません。A から始めるプリム法は、まず A–B で B を加えます。C への道として B のエッジ B–C (2) が A–C (3) に勝つので、C は B–C で加わります。C のエッジ C–D (4) は B–D (5) に勝つので、D は C–D で加わります。同じ木、同じ 7 です。

クラスカル法、プリム法、ブルーフカ法

1956年にジョゼフ・クラスカル(Joseph Kruskal)が発表したクラスカル法は、エッジを並べ替え、Union-Find 構造を使って1つの部分の中のエッジを飛ばします。そのため計算量は E log E で増えます。プリム法は1930年にヴォイチェフ・ヤルニーク(Vojtěch Jarník)が最初に示し、1957年にロバート・プリム(Robert Prim)、1959年にエドガー・ダイクストラ(Edsger Dijkstra)が再発見しました。二分ヒープを使うと計算量は E log V で、単純な配列を使うと V² で増え、後者は密なグラフに向いています。ブルーフカの1926年のアルゴリズムは、すべての部分が外へ出る最短のエッジを同時に取るので、並列計算機に向いています。

1981年のオタカル・ボルフカ。1926年、南モラヴィアの電力網をできるだけ安く計画するよう求められ、最初の最小全域木アルゴリズムを与えた。
1981年のオタカル・ボルフカ。1926年、南モラヴィアの電力網をできるだけ安く計画するよう求められ、最初の最小全域木アルゴリズムを与えた。

用途

最小全域木は、ケーブル、パイプ、道路の安価なネットワークの設計に使われます。データをクラスタに分けることもできます。木の最も長いエッジを取り除くと、残った部分がクラスタです。距離が三角不等式を満たすとき、巡回セールスマン問題で最良の巡回路の2倍以内の長さの巡回路をすばやく得られます。また、エッジの長さをランダムにした格子でクラスカル法やプリム法を実行するのは、迷路を作る定番の方法です。

試してみよう

アプリを開き、クラスカル法かプリム法を選んで「ステップ」を押しましょう。クラスカル法では、まだ試していないエッジがグラフの下に短い順に並びます。閉路を作るエッジは赤い破線で描かれます。プリム法では、木に加わるのを待つノードが最良のエッジの長さとともに並び、そのエッジは破線で描かれます。同じグラフで両方を実行して比べてみましょう。順番は違っても、長さの合計は必ず同じです。

よくある質問

全域木のエッジは何本ですか?

ノード数よりちょうど1本少ない本数です。それより少ないとすべてのノードをつなげず、1本でも多いと必ず閉路ができます。

クラスカル法とプリム法はどちらが速いですか?

エッジを並べ替えるクラスカル法は、たいていより簡単で、エッジの少ない疎なグラフで速く動きます。ヒープを使うプリム法は密なグラフで力を発揮し、単純な配列を使うと、エッジがいくつあっても約 V² ステップかかります。

Union-Find とは何ですか?

どのノードが同じ部分にあるかを管理するデータ構造です。「この2つはつながっている?」に答え、2つの部分をほぼ一瞬で併合します。クラスカル法がエッジごとに必要とするのはまさにこれです。

最小全域木は有向グラフにも使えますか?

そのままでは使えません。一方向のエッジを持つグラフでは、対応する問題は最小全域有向木で、Chu–Liu/Edmonds のアルゴリズムで解けます。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

最小全域木を作る