チャレンジ！ アルゴリズム③ 解答
こんなふうに計算します。ケーブルを、コストの小さい順につないでいきます。最初は、コスト11のケーブル。つないだところを赤く書きます。
次は、コスト12のケーブルがありますので、それを繋ぎます。
これで２つつながりました。つぎはコスト13のもの、これは3本あるので、それを全部つなぎましょう。
こうなりました。つぎはコスト14のケーブルをつなぎたいのですが、両方の家は、もうすでにつないでいるケーブルを使ってつながっています。ので、このケーブルは不要。よってつなぎません。同様に、2本あるコスト15のケーブルもつなぎません。次、16のケーブルは、まだつながっていない家をつなげますので、つなぎます。
これで、全ての家がつながりましたので、これで終了。コストは78。わかりました？？？ こんなふうに、コストの小さい方から順につないでいき、すでにつながっているところをつなぐものは無視する、とすると、必ず最小コストのつなぎ方が得られます。コストが同じ所は、どういう順番で選んでもかまいません。
ちなみに、この問題は「最小木問題」と呼ばれていて、この方法（アルゴリズム）は「クラスカルのアルゴリズム」と呼ばれています。