kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

ALDS1_12_A: Minimum Spanning Tree (続き2)

どうやって動いてるのかと言うと

頂点0をMSTのルートとする
頂点0の周りの頂点への暫定最短距離を記録していく

暫定最短距離が一番小さい頂点をMSTに含める
その頂点の周りの頂点への暫定最短距離を更新していく
全部の頂点がMSTに含まれるまで売り返す

て感じか
暫定を覚えておく分処理が少なくて済むってわけだな
あと、最短になりそうなところからやっていく分ムダな努力も少なくて済みそう

やってることはわかったがさて

なぜこのアルゴリズムで正しいのかは書いてないな

1
最短の辺をつぎつぎとMSTに組み込んでいくけれども
その時は最短に見えてあとでもっといい経路が見つかるってことはないのかな
重みが0とかマイナスってことがなければないのか
これはよさそうだ

2
どこから始めても同じなのか?
そうであってもよさそうだけど絶対そうかと言われるとちょっと自信がない
こっちはちょっと簡単に確信できる理屈が見つからない

どうするかね

あとcolorはどうなん
colorを参照しているところはBLACKかどうかしか見ていない
GRAYの状態を持つことにはやはり意味がないように見える
実際、color[v] = GRAYを削除しても動くし遅くもなってない
Tに入ったかどうかは覚えておかないといけないぽいからWHITEとBLACKは必要そうだ
そこの分で自分が書いたコードとの差がでているんだと思う

プリムのアルゴリズムは、二分ヒープ(優先度付きキュー)を使って頂点を決定するようにすれば、高速化を行うことができます。

重みが最小の辺を取り出すところのことかな
なんとなくそんな気はしていた