最小生成木のアルゴリズムと応用
最小生成木は、無向重み付きグラフにおいて、すべてのノードをつなぐことを保証しつつ、選ばれた辺の総和が最小となる構造である。この構造には複数の可能性があり、その中でも総和が最小のものを最小生成木と呼ぶ。n個のノードを持つグラフでは、最小生成木は必ずn-1本の辺で構成される。また、最小生成木にはサイクルが存在しない。
Kruskalアルゴリズムは、最小生成木を ...
8月12日 06:44 投稿
最小生成木の実装：Prim法とKruskal法の比較と実装例
グラフ理論における最小生成木を求める主要なアルゴリズムとして、Prim法とKruskal法がある。n個の頂点とm個の辺を持つグラフを対象とする。
アルゴリズムの特性
Prim法は隣接行列で表現された密グラフに適しており、基本実装の時間計算量はO(n²)である。優先度付きキューを用いてO(n log n)に改善可能である。
Kruskal法は疎グラフに向いており、辺の数mに対してO(m log ...
5月16日 03:06 投稿