7K12 blog

猫でも分かるアルゴリズム解説

AOJ GRL_2_A Minimum Spanning Tree

f:id:tkr987:20200722234628p:plain

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4213849

f:id:tkr987:20200722235328p:plain

最小全域木は全ての頂点を通るグラフの最短距離となる。最小全域木アルゴリズムにはプリム法とクラスカル法がある。実装方法は蟻本p100に載っている。