今度はブルーフカ法です。日本語での解説ページが見当たらなかったので少し丁寧に説明します。
まず、クラスカル法と同様にノード一つの木を全てのノードについて作ります。次に全ての木について、他の木と繋がる辺の中で最も重みの小さい辺を選びます。全ての木について選んだらそれをグラフに追加します。新たな木の集まり（森）について同じように辺を追加します。これを繰り返して一つの木になったらそれが最小全域木です。
問題の例で見ると、Aのみからなる木と他の木を繋がる最小の辺はACです。同様にBに対してはBA、CはCA、DはDB、EはEG、FはFD、GはGEです。これらの辺をグラフに追加すると、
19 12 16 17 F - C - A - B - D 11 E - G
という2つの木になります。次の辺はDEでこれを追加して最小全域木になります。
実装は、ノードに親を持たせるのは同じです。ルート（根）には最小の辺の重みともう一方の端点をもたせます。全ての辺についてその両端点のルートを調べ、ルートが異なっていればそのルートが持つ最小の辺の重みと比べて、この辺の重みの方が小さければ置き換えます。全て終わったら、全てのルートが持つ最小の辺でルートとルートを繋ぎます。そしてルートをクリアして、ルートの個数を調べます。ルートの個数が一つになるまでこれを繰り返します。
この例では40個のルートが12 -> 3 -> 1個となります。わずか3回繰り返すだけです。
