Matsushita's Blog

最小全域木の重みの総和を求める

最小全域木とは

最小全域木とは、グラフの全域の中で辺の重みの総和が最小のもの木のこと。つまり、与えられたグラフの全てのノードを含む木を作成する際に、辺の重みが最小になるように作ったものになる。この木を作成するためにプリムのアルゴリズムを用いる。

プリムのアルゴリズムとは

プリムのアルゴリズムとは、以下のステップで木の作成を行う。

  • 初めに任意のノードを木のルートとしstartNodeと名付ける。
  • startNodeと連結されているノードの中から辺の重みが最小のノードを選びnextNodeと名付け木に連結する。
  • startNodeをnextNodeで更新する。
  • 2, 3を作成する木のノード数がグラフのノード数と等しくなるまで繰り替えす。

基本的にはプリムのアルゴリズムの計算量はO(V2)となる(V: 頂点の数)。これは最小の重みの頂点を見つけるために頂点の数だけ調べ、この探索を頂点の数だけ行うからだ。

しかし、最小の辺を見つける時に二分探索を行えばO(longV)で最小の辺を見つける事ができるので全体の計算量はO(VlogV)となる。具体的には優先度付きキューを用いることで実装可能。

ソースコード