ブルーフカ法

このアルゴリズムは1926年に、チェコの数学者オタカル・ブルーフカ（英語版）がモラヴィアでの電力網を敷く際に発見した^[1][2][3]。またその後、ギュスターヴ・ショケ（英語版）（1938）^[4]、ウカシェヴィチら（1951）^[5]、ソリン（1965）^[6] がそれぞれ再発見した。前記した発見者のうち英語圏で生活していたのはソリンしかいないため、特に並列計算の分野ではソリンアルゴリズムとも呼ばれる。

このアルゴリズムではまず、頂点ひとつの木を全てのノードについて作成し、それぞれ全ての木について、重みが最小の辺を探索する。この際、選ばれる辺は重複しても良い。選択された辺で繋がれた木は森（木の集合）に追加する。次に、重みが最小の辺を探索するという手順を、全ての森についても行う。これを森が一つの木になるまで繰り返す。一つの木になったらそれが最小全域木である。

辺の数をE、Vを頂点の数として、ブルーフカ法はO(log V)回の反復をするため、計算には時間O(E log V)かかる。平面グラフでは、反復するごとにふたつの木の間で重みが最小の辺以外を取り除くことにより、より線形に近い計算量で済む。

クラスカル法はブルーフカ法と同じく、アルゴリズム開始時に全ての頂点でノード一つの木を作成する。それに対して、プリム法では木を最初に決定したひとつの頂点から拡大していく。

知られている最小全域木を求める最適化問題のアルゴリズムの中でもっとも効率の良い バーナード・チャゼル（英語版） のアルゴリズムは O(E α(E,V)) の計算量で、ブルーフカ法を参考にしている。