最小全域木(Prim)
説明
最小全域木(全域木のうち、その辺群の重みの総和が最小になる木)を求めるアルゴリズム。既に到達した頂点集合からまだ到達していない頂点集合への辺のうち、コストが最小のものを選んでいくことによって、最小全域木を構成している。
計算量
$O(E \log V)$
$V$: 頂点数, $E$: 辺数
実装例
最小全域木(全域木のうち、その辺群の重みの総和が最小になる木)を求めるアルゴリズム。既に到達した頂点集合からまだ到達していない頂点集合への辺のうち、コストが最小のものを選んでいくことによって、最小全域木を構成している。
$O(E \log V)$
$V$: 頂点数, $E$: 辺数