ALDS1_12_A: Minimum Spanning Tree

前章では、グラフの表現方法を確認したうえで基本的な探索アルゴリズムに関する問題を解きました。

ここから上級編に入るってことだな？

Gの最小全域木の辺の重みの総和を1行に出力してください。

最小全域木とは何か、というのは説明されているんだけれども
どうやって求めるのかは書いてない
書かなくてもわかるだろ？ってことだろうか
しかしさっぱりわからない

『最短経路の本 レナのふしぎな数学の旅』に出てたかもしれないけど
どうやってたかは思い出せない

総当たりだとエッジの数の階乗のオーダになるからとてもやっていられない
ゼロからひとつずつ辺を足していくのか
全エッジから削除していくのか
うまく最小であることを保証しながら進めていくにはどうすればいい？
ある時点ではいい選択でもあとで悪くならないとは言えない気がするし

問題の冒頭にある3つの図の真ん中はなにかしらアルゴリズムに関係する
図なはずなんだけれども何を言っているのか読み取れない
二つの島に分かれたノードを、島をまたいでつないでいっているように
見えるんだけれどもそれがこの問題とどう関わってくるのか

重みの総和を求めよ、って言ってるけど実は木自体は求めなくていいとか？
それもなさそうな気はするなあ
もしそうだったとしてもどうやったらいいかはわかんないし

0<=aij<=2000ってのはどういうことだろうなあ
2000は半端な気がしないでもない
バケツソートが使えたりとか？
ないかな
aij=ajiっていうのは無向グラフってことだな

それくらいか
わからんしチャレンジ問題だから先へ進めとも書いてないから解説を読む

プリムのアルゴリズム
グラフ G=(V,E)の頂点全体の集合をV、MSTに属する頂点の集合をTとします。
1. Gから任意の頂点rを選び、それをMSTのルートとして、Tに追加します。
2. 次の処理をT=Vになるまで繰り返します。
Tに属する頂点とV-Tに属する頂点をつなぐ辺の中で、重みが最小のものである辺(pu, u)を選び、それをMSTの辺とし、uをTに追加します。

任意の頂点かあ
どこから始めても同じ、ってことは要証明っぽいなあ
自明？
puってのは重みが最小な辺の、uの反対側の頂点ってことだな
真ん中の図はTの島の頂点とV-Tの島の頂点をつなぐ辺を表してるってわけか
だいたいわかった

1ページめくればもっと詳しく書いてありそうだけどここまでで一度考えてみよう