プリム法

最小全域木を求める方法の1つ

成長する木の数は1つだけ

手順

適当な頂点を選ぶ

そこから生えてる一番重みの少ない辺を採用する

つながっている辺のすべての点からたどれる辺のうち、重みが一番少なくかつ閉路にならない辺を採用する

生やせなくなったらおしまい

詳しくは以下