Borůvka のアルゴリズム

最も古くそしておそらくは最も単純な最小全域木アルゴリズムは、チェコ人数学者 Otakar Borůvka (オタカール・ブルーフカ) によって 1926 年に発見されました。彼がこのアルゴリズムを発見したのは、いくつかの都市を最小の電線で結ぶ電気ネットワークを作るにはどうすればよいかと Jindřich Saxel という人物に尋ねられてから約一年後のことでした1。このアルゴリズムは Gustav Choquet (グスタフ・ショケ) によって 1938 年に、Józef Łukaszewicz (ヨゼフ・ウカセビッチ) を代表とするポーランド人数学者らによって 1951 年に、George Sollin (ジョージ・ソリン) によって 1961 年に再発見されています。Sollin は再発見を公表することはありませんでしたが、このアルゴリズムを詳しく説明したグラフアルゴリズムの最初期の教科書が彼を発見者だとしていたので、このアルゴリズムは "Sollin のアルゴリズム" と呼ばれることがあります。

Borůvka / Choquet / Florek-Łukaziewicz-Perkal-Steinhaus-Zubrzycki / Prim / Sollin / Brosh2 のアルゴリズムは次の一行に要約できます:

Borůvka: 安全な辺をスベテ見つけて再帰する。

例のグラフに対する Borůvka のアルゴリズムの実行例。赤い辺が \(F\) の辺を、破線が不要な辺を、矢印が各成分の安全な辺を表す。実行はたった二回の反復で終了する。
図 7.3
例のグラフに対する Borůvka のアルゴリズムの実行例。赤い辺が \(F\) の辺を、破線が不要な辺を、矢印が各成分の安全な辺を表す。実行はたった二回の反復で終了する。

Borůvka のアルゴリズムの概形を次に示します。このアルゴリズムは 五章で説明した \(\textsc{CountAndLabel}\) アルゴリズムを使っています。\(\textsc{CountAndLabel}\) は \(F\) の各頂点を属する成分の番号を表す \(\mathit{count}(v)\) でラベル付けします。

procedure \(\texttt{Borůvka}\)(\(V, E\))

\(F = (V, \varnothing)\)

\(\mathit{count} \leftarrow\)\(\texttt{CountAndLabel}\)(\(F\))

while \(\mathit{count} > 1\) do

\(\texttt{AddAllSafeEdges}\)(\(E, F, \mathit{count}\))

\(\mathit{count} \leftarrow \)\(\texttt{CountAndLabel}\)(\(F\))

return \(F\)

後は \(F\) の安全な辺を全て見つける方法を説明すれば良いことになります。\(F\) に成分が一つだけならば全域木が手に入っているので、そうでないと仮定します。このとき次に示すサブルーチンは安全な辺 \(\mathit{safe}[1..V]\) を全て見つけます。ここで \(\mathit{safe}[i]\) が端点のちょうど一方が \(F\) の \(i\) 番目の成分に属する辺の中で重みが最小なものを表し、値の計算は \(G\) の辺に対する総当たりによって行われます。各辺 \(uv\) について、\(u\) と \(v\) が同じ成分に属しているなら \(uv\) は不要な辺あるいは \(F\) に含まれる辺なので、何もしません。そうでなければ、\(uv\) の重みと \(\mathit{safe}[\mathit{comp}(u)]\) と \(\mathit{safe}[\mathit{comp}(v)]\) を比べ、必要ならば値を更新します。全ての安全な辺を特定し終えたら、辺 \(\mathit{safe}[i]\) を \(F\) に加えます。

procedure \(\texttt{AddAllSafeEdges}\)(\(E, F, \mathit{count}\))

for \(i \leftarrow 1\) to \(\mathit{count}\) do

\(\mathit{safe}[i] \leftarrow \textsc{Null}\)

for \(uv \in E\) do

if \(\mathit{comp}(u) \neq \mathit{comp}(v)\) then

if \(\mathit{safe}[\mathit{comp}(u)] = \textsc{Null} \text{ or } w(uv) < w(\mathit{safe}[\mathit{comp}(u)])\) then

\(\mathit{safe}[\mathit{comp}(u)] \leftarrow uv\)

if \(\mathit{safe}[\mathit{comp}(v)] = \textsc{Null} \text{ or } w(uv) < w(\mathit{safe}[\mathit{comp}(v)])\) then

\(\mathit{safe}[\mathit{comp}(v)] \leftarrow uv\)

for \(i \leftarrow 1\) to \(\mathit{count}\) do

\(\mathit{safe}[i]\) を \(F\) に加える

\(F\) は最大で \(V-1\) 本の辺を持つので、\(\textsc{CountAndLabel}\) の実行時間は \(O(V)\) です。また \(\textsc{AddAllSafeEdges}\) は \(G\) の各辺と\(F\) の各成分に対して定数時間の処理を行うので、実行時間は \(O(V+E)\) です。入力グラフは連結なことから \(V \leq E + 1\) なので、\(\textsc{Borůvka}\) の while ループ一回分の実行時間は \(O(E)\) だと分かります。

各反復において \(F\) の成分数は少なくとも半分になります ――最悪ケースでは \(F\) の成分が全て組になるからです。\(F\) は最初 \(V\) 個の成分を持つことから、while ループは最大でも \(O(\log V)\) 回反復します。以上より、Borůvka のアルゴリズム全体の実行時間は \(\pmb{O(E \log V)}\) となります。

これこそがあなたの望む MST アルゴリズム

Borůvka のアルゴリズムは誰によって発見されたかが比較的はっきりしなかったにもかかわらず、初期の西洋のアルゴリズム研究者はこのアルゴリズムの存在に気が付いていました。しかし Borůvka アルゴリズムは "複雑すぎる" という理由で忘れられ、結果としてほとんどのアルゴリズムとデータ構造の教科書は単純さと効率の良さを兼ね備えた Borůvka のアルゴリズムに触れることさえしません。これは残念なことであり、重大な誤りです。Borůvka のアルゴリズムは他の古典的なアルゴリズムと比べていくつもの明確な利点があります:

まとめると、もし最小全域木アルゴリズムを実装することになったら、Borůvka のアルゴリズムを使っておけば間違いありません。ただし最小全域木に関する命題を効率良く証明したいなら、次に示す二つのアルゴリズムも知っておく必要があります。

  1. Saxel は West Moravian Power Company の従業員であり、Borůvka によると "とても才能のある、良く働く" 人物であったそうです。彼はユダヤ人の家系であったために、後にナチスによって処刑されています。[return]

  2. Hyperbole and a Half を全部読んで、本を買って、猫用にもう一冊買ってください。え？ 猫を飼ってないって？ とんでもない変人ですね。猫を見つけてきて、その猫用に Hyperbole and a Half をもう一冊買ってください。[return]

広告
このページの文章はテキストゆれないくんを使って校正されました。