最小全域木の重みの総和を求める
最小全域木とは
最小全域木とは、グラフの全域の中で辺の重みの総和が最小のもの木のこと。つまり、与えられたグラフの全てのノードを含む木を作成する際に、辺の重みが最小になるように作ったものになる。この木を作成するためにプリムのアルゴリズムを用いる。
プリムのアルゴリズムとは
プリムのアルゴリズムとは、以下のステップで木の作成を行う。
- 初めに任意のノードを木のルートとしstartNodeと名付ける。
- startNodeと連結されているノードの中から辺の重みが最小のノードを選びnextNodeと名付け木に連結する。
- startNodeをnextNodeで更新する。
- 2, 3を作成する木のノード数がグラフのノード数と等しくなるまで繰り替えす。
基本的にはプリムのアルゴリズムの計算量はO(V2)となる(V: 頂点の数)。これは最小の重みの頂点を見つけるために頂点の数だけ調べ、この探索を頂点の数だけ行うからだ。
しかし、最小の辺を見つける時に二分探索を行えばO(longV)で最小の辺を見つける事ができるので全体の計算量はO(VlogV)となる。具体的には優先度付きキューを用いることで実装可能。
