最小全域木とクラスカル法

最小全域木とはすべての頂点が連結されていて辺の重みの総和が最小のものです。

この場合は赤い部分をつなぐことで答えは39となります。

最小全域木を求める方法のひとつがKruscal(クラスカル)のアルゴリズムです。

辺集合をコストが小さい順にソートする
コストが小さい順に辺を連結させる(ただし閉路ができる場合はなにもしない)

下の動画の説明がわかりやすいです。

C# コンソールアプリで実装する

でははじめてみましょう。動画内の方法で辺の重みの総和が最小になる値を求めます。それからどの辺同士が連結されるのか、ノードの親はどうなるのかも出力させます(37と出力されるはず)。

EdgeクラスとNodeクラスの定義

Edgeクラスのコンストラクタの引数は、連結するふたつのノードの番号(最初は0)と重みです。フィールド変数のJoinは連結されているかどうかを表わすbool変数です。

Nodeクラスのコンストラクタの引数は頂点の番号です。

Mainメソッド

実際の処理をおこないます。頂点の数と辺がふたつのどの頂点につながっているのか、それらの重みをリストにして、計算をするオブジェクトのメソッドに渡します。

連結すると閉路ができるかどうかの判定

辺の重みを小さい順にソートしてノード同士を連結していきます。ただし閉路ができる場合は連結させません。

閉路ができるかどうかは動画にもあるとおりNodeの「親分」なるものを定義することで判断します。まだどことも連結していない頂点同士を連結するときには番号が小さいほうを親とする部分は動画と同様にしていますが、親を持つ頂点同士を連結させるときは要素数が小さなものが大きなものの直接の「子分」にするという処理はやらず、親の頂点の番号のみ比較し、番号が大きいほうが小さなものの直接の子になるようにしています。

GetParentメソッドはノードの親をたどっていき最終的な親を求めます。

どの辺が連結しているのか?

蛇足部分です。どの辺が連結しているのが出力させます。

最小全域木における親はどうなっているか?

蛇足部分その2です。各頂点の親がどうなっているのか順番に出力させます。

上記コードを実行すると、出力は以下のようになります。動画では親は7番になっていますが、親の決め方が違っているので実行結果をみると0がすべての親になっています。