最小生成木の実装：Prim法とKruskal法の比較と実装例
グラフ理論における最小生成木を求める主要なアルゴリズムとして、Prim法とKruskal法がある。n個の頂点とm個の辺を持つグラフを対象とする。
アルゴリズムの特性
Prim法は隣接行列で表現された密グラフに適しており、基本実装の時間計算量はO(n²)である。優先度付きキューを用いてO(n log n)に改善可能である。
Kruskal法は疎グラフに向いており、辺の数mに対してO(m log ...
5月16日 12:06 投稿