Project Euler 107(2) クラスカル法

Problem 107

次はクラスカル法です。

まず、一つのノードのみの木を全てのノードについて作ります。すなわち例では木が7つ作成されることになります。ノードはルート(根)がすぐにわかるようにしておきます。ノードに親を持たせれば、親を辿っていくとルートに辿りつくようになります。辺は重みの昇順にソートしておきます。

最小の重みの辺を取り出します。例ではEGですね。この辺の両端点が同じ木に属するかどうか調べます。同じ木ならその辺は捨てます。そうでなければ辺で木を同士をつなげて一つの木にします。具体的には一方の木のルートをもう一方の木のルートの親にします。これを繰り返して辺の数が(ノードの数-1)になればそれが最小全域木です。