最小スパニングツリー

最小スパニングツリーを見つける

初めての試み

最小スパニングツリーを発見するアルゴリズムを作るのは非常に簡単です。

関数 MST(G,W)     .T = {}     Tがスパニングツリーを形成していない間：         Eの中でTに対して安全な最小の重み付き辺を求める T = T union {(u,v)}     return T

この場合、「安全」とは、その辺を含めてもグラフのサイクルが形成されないことを意味します。サイクルとは、ある頂点から始まり、他の多くの頂点まで移動し、同じ辺を二度使わずに再び始点で終わることを意味します。

歴史

チェコの科学者オタカル・ボルジュカは、1926年に木を最小化するアルゴリズムを開発しました。彼はモラヴィアの電気の効率的な範囲を見つける問題を解決したいと考えていました。今日、このアルゴリズムはボルジュフカのアルゴリズムとして知られています。他にも2つのアルゴリズムが一般的に使用されています。そのうちの1つは1930年にVojtěch Jarníkによって開発され、1957年にRobert Clay Primによって実用化されました。エドガー・ワイベ・ダイクストラが1959年に再発見し、プリムのアルゴリズムと呼ばれるようになりました。もう一つのアルゴリズムはクルスカルのアルゴリズムと呼ばれ、1956年にジョセフ・クルスカルによって提唱された。3つのアルゴリズムはすべて貪欲で、多項式時間で実行される。

今日までで最速の最小スパニングツリーアルゴリズムは、Bernard Chazelleによって開発されました。このアルゴリズムは、ソフトヒープ（近似優先度キュー）に基づいています。その実行時間はO(m α(m,n))であり、mは辺の数、nは頂点の数、αはアッカーマン関数の古典的な関数逆数です。関数αは非常にゆっくりと成長するので、実用的には4よりも大きくない定数と考えられます。

この問題のために可能な限り最速のアルゴリズムは何か？これはコンピュータサイエンスの中で最も古くからある未解決の問題の一つです。少なくともすべての重みを調べなければならないので、明らかに線形の下界があります。辺の重みがビット長が制限された整数であれば，線形の実行時間を持つ決定論的アルゴリズムが知られています．一般的な重みについては、期待される実行時間が線形であるランダム化アルゴリズムがあります。

この問題は分散的にアプローチすることもできます。各ノードをコンピュータとみなし、ノードが自分の接続されたリンク以外は何も知らない場合でも、分散型最小スパニングツリーを計算することができます。