Kruskal

説明

最小全域木(全域木のうち、その辺群の重みの総和が最小になる木)を求めるアルゴリズム。Union-Findを用いて辺集合にある辺を加えて閉路を作らないか判定しながら、辺を重みが小さい順に走査する。

---

情報

項目	データ
計算量	$O(E\log_{2}E)$

関数

int kruskal(graph)
機能	最小全域木のコストを求める
引数	$edges$: 辺集合 $V$: 頂点数
戻り値	コスト

実装例

問題例

#	ソース	難易度
AOJ GRL_2_A - 最小全域木	-
AOJ 0180 - デブンキー一家の大活躍	PCK2008予選	★
AOJ 0072 - 灯篭	PCK2004本選	★★
ARC029_C - 高橋君と国家	ARC029_C	★★★
AOJ 0575 - JOI 国のお祭り事情	JOI2011本選	★★★★
ARC026_D - 道を直すお仕事	ARC026_D	★★★★