Loading article…
_Anim.gif/500px-Boruvka's_algorithm_(Sollin's_algorithm)_Anim.gif) Borůvka のアルゴリズムのアニメーション | |
| クラス | 最小全域木アルゴリズム |
|---|---|
| データ構造 | グラフ |
| 最悪の場合の パフォーマンス | |
Borůvka アルゴリズムは、グラフ内の最小全域木、または連結されていないグラフの場合は最小全域森を 見つけるための貪欲アルゴリズムです。
このアルゴリズムは、1926年にオタカル・ボルフカによって、モラビアの効率的な電力網を構築する方法として初めて発表されました。[1] [2] [3]このアルゴリズムは、1938年にショケ によって再発見され、 [4] 1951年にフロレク、 ルカシェヴィチ、ペルカル、シュタインハウス、ズブジツキによって再び発見され、[5] 1965年にジョルジュ・ソリンによって再び発見されました。 [6]このアルゴリズムは、特に並列コンピューティングの文献では、ソリンのアルゴリズムと呼ばれることがよくあります。
アルゴリズムは、グラフの各頂点に接する最小重みのエッジを見つけることから始まり、それらのエッジをすべてフォレストに追加します。次に、これまでに構築された各ツリーから別のツリーへの最小重みのエッジを見つけ、それらのエッジをすべてフォレストに追加するという同様のプロセスを繰り返します。このプロセスを繰り返すたびに、グラフの各接続コンポーネント内のツリーの数は最大で以前の値の半分にまで減少するため、対数的に繰り返されるとプロセスは終了します。終了すると、追加されたエッジのセットが最小全域フォレストを形成します。
擬似コード
次の擬似コードは、Borůvka アルゴリズムの基本的な実装を示しています。条件節では、すべてのエッジuv は「なし」よりも安価であると見なされます。completed 変数の目的は、フォレストFがまだスパニング フォレストであるかどうかを判断することです。
エッジに明確な重みがない場合は、たとえば頂点またはエッジの全体的な順序に基づいて、一貫したタイブレーク ルールを使用する必要があります。これは、頂点を整数として表現してそれらを直接比較する、メモリ アドレスを比較するなどによって実現できます。タイブレーク ルールは、作成されたグラフが実際にフォレストであること、つまりサイクルが含まれていないことを保証するために必要です。たとえば、ノード { a、b、c } があり、すべてのエッジの重みが 1 である三角形のグラフを考えます。この場合、 { a }の最小重みエッジとしてabを、{ b } のbcを、{ c } のca を選択すると、サイクルが作成されます。最初にソースでエッジを順序付けし、次に宛先でエッジを順序付けるタイブレーク ルールは、サイクルの作成を防ぎ、最小スパニング ツリー { ab、bc } を生成します。
アルゴリズムBorůvkaの
入力:重み付き無向グラフG = ( V , E )。
出力: F 、 Gの最小全域森。
フォレストFを ( V , E ′ ) に初期化します。ここで、E ′ = {} です。
完了 := false
完了していない場合はFの連結成分
を探し、各頂点にその成分を割り当てる
各コンポーネントの最も安価なエッジを「なし」に初期化します
Eの各辺uvに対して、uとv はFの異なる要素にあります。wx を
uの
コンポーネントの最も安価なエッジとします。if is -preferred-over( uv , wx ) then uv をuのコンポーネントの最も安価なエッジとして
設定します。yz を
vの
コンポーネントの最も安価なエッジとします。if is -preferred-over( uv , yz ) then uv をv
のコンポーネントの最も安価なエッジとして
設定します。すべてのコンポーネントの最も安価なエッジが "None" に設定されている場合、
// これ以上ツリーをマージすることはできません。これで完了です。completed
: = true
、else
completes := false
最も安価なエッジが "None" ではない各コンポーネントについて、その最も安価なエッジをE'
に追加します。
関数is-preferred-over( edge1 , edge2 )は
( edge2が "None")を返すか、
(重み(エッジ1 ) < 重み(エッジ2 )) または
(重み(エッジ1 ) = 重み(エッジ2 ) かつ タイブレークルール(エッジ1、エッジ2 ))
関数tie-breaking-rule( edge1 , edge2 )は
、タイブレークルールです。同点の場合に
edge1がedge2
より優先される場合にのみtrue を返します。
最適化として、同じコンポーネント内の 2 つの頂点を接続することがわかった各エッジをGから削除して、後のコンポーネントで最も安価なエッジを検索する時間に影響しないようにすることができます。
複雑
Borůvka のアルゴリズムは、外側のループが終了するまでO (log V )回繰り返すため、実行時間O ( E log V )で実行できることが示されています。ここで、Eは辺の数、V はG内の頂点の数です( E ≥ Vと仮定)。平面グラフ、およびより一般的にはグラフマイナー操作で閉じたグラフの族では、アルゴリズムの各段階の後に各コンポーネントのペア間の最も安価な辺以外をすべて削除することで、線形時間で実行できます。[7]
例
その他のアルゴリズム
この問題に対する他のアルゴリズムとしては、プリムのアルゴリズムとクラスカルのアルゴリズムがある。プリムのアルゴリズムとボルフカのアルゴリズムを組み合わせることで、高速な並列アルゴリズムが得られる。[8]
Karger、Klein、および Tarjan による、Borůvka アルゴリズムに部分的に基づく、より高速なランダム最小全域木アルゴリズムは、期待されるO( E )時間で実行されます。[9] Bernard Chazelle による最もよく知られている (決定論的) 最小全域木アルゴリズムも、Borůvka のアルゴリズムに部分的に基づいており、O( E α( E、V ))時間で実行されます。ここで、α は逆アッカーマン関数です。[10]これらのランダム化および決定論的アルゴリズムは、接続される残りのコンポーネントの数を減らす Borůvka アルゴリズムのステップと、コンポーネントのペア間のエッジの数を減らす異なるタイプのステップを組み合わせています。
注記
- ^ ボルフカ、オタカル(1926)。 「O jistém problému minimálním」[ある最小限の問題について]。モルをプレースプルシーロドヴェド。スポル。 V ブルネ III (チェコ語とドイツ語)。3：37～ 58。
- ^ ボルフカ、オタカル(1926)。 「Příspěvek k šešení otázky ekonomické stavby elektrovodních sítí (電力網の経済的な構築の問題の解決への貢献)」。Elektronický Obzor (チェコ語)。15 : 153–154 .
- ^ ネシェトジル、ヤロスラフ;ミルコバ、エヴァ。ネシェトジロヴァ、ヘレナ (2001)。 「最小スパニングツリー問題に関するOtakar Borůvka: 1926年の両方の論文の翻訳、コメント、歴史」。離散数学。233 ( 1–3 ): 3–36 .土井:10.1016/S0012-365X(00)00224-7。hdl : 10338.dmlcz/500413。MR1825599 。
- ^ ギュスターヴ・ショケ(1938)。 「あるルートの研究」。Comptes Rendus de l'Académie des Sciences (フランス語)。206 : 310 – 313.
- ^ フロレク、K.;ウカシェヴィチ、J . ;パーカル、J.ヒューゴ・シュタインハウス;ズブジツキ、S. (1951)。 「最終的なアンサンブルの連絡と点の分割」。Colloquium Mathematicum (フランス語)。2 ( 3–4 ): 282–285 .ドイ:10.4064/cm-2-3-4-282-285。MR0048832 。
- ^ ジョルジュ・ソラン (1965)。 「運河の跡」。プログラミング、ゲーム、交通ネットワーク(フランス語)。
- ^ Eppstein, David (1999)。「スパニングツリーとスパナ」。Sack , J.-R. ; Urrutia, J. (編)。計算幾何学ハンドブック。Elsevier。pp. 425– 461。;マレシュ、マルティン (2004)。 「マイナー閉グラフ クラスにおける MST の 2 つの線形時間アルゴリズム」(PDF)。数学のアーカイブ。40 (3): 315–320 .。
- ^ Bader, David A.; Cong, Guojing (2006). 「スパースグラフの最小スパニングフォレストを計算するための高速共有メモリアルゴリズム」。Journal of Parallel and Distributed Computing . 66 (11): 1366– 1378. CiteSeerX 10.1.1.129.8991 . doi :10.1016/j.jpdc.2006.06.001. S2CID 2004627.
- ^ Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995). 「最小スパニングツリーを見つけるためのランダム線形時間アルゴリズム」Journal of the ACM . 42 (2): 321– 328. CiteSeerX 10.1.1.39.9012 . doi :10.1145/201019.201022. S2CID 832583.
- ^ Chazelle, Bernard (2000). 「逆アッカーマン型複雑度を持つ最小全域木アルゴリズム」(PDF) . J. ACM . 47 (6): 1028– 1047. CiteSeerX 10.1.1.115.2318 . doi :10.1145/355541.355562. S2CID 6276962.