最小全域木をpythonで
最小全域木の勉強をしたので、まとめる。
これ
AtCoder 版！蟻本 (初級編) - Qiita
をやってて、最小全域木の項目があったのでやった。
やり方はwikipedia
全域木 - Wikipedia
を参考にした。
これのKruskal法とPrim法をやった。
Kruskal法
Kruskal法の理論
Kruskal法はだいたい次のような感じ（wikipediaに書いてある）。
ans = 0 とする。
0. Sを全ての辺を格納したものとする。
1. Sにある辺のうち、重みが最小のものを取り出す。
2. その辺の2つの頂点が繋がっていなければ、ans に重みを加算する。
3. 1 と 2 を繰り返す。
Kruskal法の実装
pythonでやると、
0 (1). Sに (辺の重さ, 頂点, 頂点) のようなタプル型を全て格納する。
0 (2). Sを小さい順にソートする。頂点の順番はどうでも良いので、そのままソートすると、辺の重さが小さいものが先頭に来る。
あるいは、優先度付きキューを用いても良い。例えば、python には heapq というモジュールがある。
（私はこちらを使っている。）
(1) と (2) に関しては heapq を使えば、まとめてできる。
1. リストなら、S[i] みたいにすればいいし、heapq なら heapq.heappop(S) とすればよい。
2. union-find を用いて、繋がっているか判断する。
3. 繋がっていなければ、ans に（辺の重さ）を加算し、辺の2つの頂点を union する。
Prim法
Prim法の理論
多分こんな感じ。相変わらず ans = 0 で始める。
0. 適当に一つ頂点を選び、それと隣接する頂点間にある辺の情報(辺の重さ, 頂点, 頂点)をSに入れる。
適当に選んだ頂点を とする。
1. Sにある辺のうち、最も重さの小さいものを取り出す。
2. 取り出した辺の頂点2つが、 と繋がっているか判断する。
3. 繋がっていない場合は、 取り出した辺の重みを ans に加算し、 と繋がっていなかった頂点を繋げる。
さらに、繋がっていなかった頂点と隣接する辺の情報を S に追加する。
4. 2 と 3 を繰り返す。
Prim方の実装
0. Sとして、優先度付きキュー（heapq）を用いて、適当に選んだ頂点 と隣接する、辺の情報を heapq.heappush(S, (辺の重さ, 頂点, 頂点))する。
1. heappop(S)
2. 各頂点が初めの頂点と繋がっているか確認する。
3. 繋がっていない場合は、（辺の重さ）を ans に可算し、 と繋げて、隣接する辺の情報を heapq.heappush(S, (辺の重さ, 頂点, 頂点)) する。
