Boost.Graph 最小全域木を作る

C++

グラフに含まれるすべての頂点を含む最小の部分グラフを、最小全域木(minimum spanning tree)と言います。
Boost.Graphには、最小全域木を作るためのアルゴリズムとして、以下の2つの関数が用意されています。


これらを以下のグラフに適用すると

以下のような最小全域木(赤線部分)が手に入ります。

それぞれの使い方は以下のようになります。

  • boost::kruskal_minimum_spanning_tree()

クラスカル法によって最小全域木を求めるboost::kruskal_minimum_spanning_tree()関数は、Output Iteratorで最小全域木の辺記述子(edge descriptor)を返します。

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS,
    boost::no_property, boost::property<boost::edge_weight_t, int> > Graph;
typedef std::pair<int, int> Edge;
typedef boost::graph_traits<Graph>::edge_descriptor EdgeDesc;

std::string Name = "ABCDE";
enum {A, B, C, D, E, N};

Graph make_graph()
{
    const std::vector<Edge> edges = {
        {A, C},
        {B, D},
        {B, E},
        {C, B},
        {C, D},
        {D, E},
        {E, A}
    };

    const std::vector<int> weights = {
        1,
        1,
        2,
        7,
        3,
        1,
        1
    };
    return Graph(edges.begin(), edges.end(), weights.begin(), N);
}

int main()
{
    const Graph g = make_graph();

    std::vector<EdgeDesc> spanning_tree;
    boost::kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree));

    for (const EdgeDesc& e : spanning_tree) {
        std::cout << "(" << Name[boost::source(e, g)] << ","
                         << Name[boost::target(e, g)] << ")" << std::endl;
    }
}

(A,C)
(D,E)
(E,A)
(B,D)
  • boost::prim_minimum_spanning_tree()

プリム法によって最小全域木を求めるboost::prim_minimum_spanning_tree()関数は、先行ノードマップ(predecessor map)として最小全域木を返します。

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/prim_minimum_spanning_tree.hpp>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS,
    boost::no_property, boost::property<boost::edge_weight_t, int> > Graph;
typedef std::pair<int, int> Edge;
typedef boost::graph_traits<Graph>::vertex_descriptor VertexDesc;

std::string Name = "ABCDE";
enum {A, B, C, D, E, N};

Graph make_graph()
{
    const std::vector<Edge> edges = {
        {A, C},
        {B, D},
        {B, E},
        {C, B},
        {C, D},
        {D, E},
        {E, A},
    }

    const std::vector<int> weights = {
        1,
        1,
        2,
        7,
        3,
        1,
        1,
    };
    return Graph(edges.begin(), edges.end(), weights.begin(), N);
}

int main()
{
    Graph g = make_graph();

    std::vector<VertexDesc> parents(N);
    boost::prim_minimum_spanning_tree(g, &parents[0]);

    for (std::size_t i = 0; i < N; ++i) {
        if (parents[i] != i) {
            std::cout << "parent[" << Name[i] << "] = " << Name[parents[i]] << std::endl;
        }
        else {
            std::cout << "parent[" << Name[i] << "] = no parent" << std::endl;
        }
    }
}

parent[A] = no parent
parent[B] = D
parent[C] = A
parent[D] = E
parent[E] = A

参照：
ALGORITHM NOTE 最小全域木