最小全域木(Kruskal)
説明
最小全域木(全域木のうち、その辺群の重みの総和が最小になる木)を求めるアルゴリズム。Union-Findを用いて辺集合にある辺を加えて閉路を作らないか判定しながら、辺を重みが小さい順に走査する。
使い方
Union-Find が必要
計算量
$O(E \log V)$
$V$: 頂点数, $E$: 辺数
実装例
最小全域木(全域木のうち、その辺群の重みの総和が最小になる木)を求めるアルゴリズム。Union-Findを用いて辺集合にある辺を加えて閉路を作らないか判定しながら、辺を重みが小さい順に走査する。
Union-Find が必要
$O(E \log V)$
$V$: 頂点数, $E$: 辺数