グラフに含まれるすべての頂点を含む最小の部分グラフを、最小全域木(minimum spanning tree)と言います。 Boost.Graphには、最小全域木を作るためのアルゴリズムとして、以下の2つの関数が用意されています。 boost::kruskal_minimum_spanning_tree() : クラスカル法 boost::prim_minimum_spanning_tree() : プリム法 これらを以下のグラフに適用すると 以下のような最小全域木(赤線部分)が手に入ります。 それぞれの使い方は以下のようになります。 boost::kruskal_minimum_spanning_tree() クラスカル法によって最小全域木を求めるboost::kruskal_minimum_spanning_tree()関数は、Output Iteratorで最小全域木の辺記述子(ed
![Boost.Graph 最小全域木を作る - Faith and Brave - C++で遊ぼう](https://cdn-ak-scissors.b.st-hatena.com/image/square/c724daa32e123b3015bdf4f8d0ba92ca8b78cc3d/height=288;version=1;width=512/http%3A%2F%2Fcdn-ak.f.st-hatena.com%2Fimages%2Ffotolife%2Ff%2Ffaith_and_brave%2F20120627%2F20120627165416.png)