0

我正在尝试将 Kruskal 的最小生成树应用于我的图，以将其从无向循环图变成真正的树。边权重都是一样的，因为 MST 是否唯一并不重要。

到目前为止，我已按如下方式实现它：

typedef boost::adjacency_list<boost::setS, boost::listS, 
            boost::undirectedS, CoordNode, CoordSegment> BGraph;

和

class CoordSegment {
public:
    double weight;
[...]
}

我需要向我的图表添加一些功能，因此我的图表对象实际上是一个派生（如果重要的话）：

class Graph : public BGraph {
protected:
    unsigned int _idCounter;

[...]
}

我的问题在这里：

// compiles ok
boost::property_map<BGraph, double CoordSegment::*>::type weightMap = boost::get(&CoordSegment::weight, _graph);

    std::vector<EdgeDesc> tree;
// doesn't compile 
    boost::kruskal_minimum_spanning_tree(_graph, std::back_inserter(tree), weightMap);

它抱怨如下：

\src\PGraphSkel.cpp(376) : error C2784: "void boost::kruskal_minimum_spanning_tree(const Graph &,OutputIterator,const boost::bgl_named_params<P,T,R> &)": template-argument for "const boost::bgl_named_params<P,T,R> &" could not be deduced from "boost::bundle_property_map<Graph,Descriptor,Bundle,T>".
1>        with
1>        [
1>            Graph=BGraph,
1>            Descriptor=boost::detail::edge_desc_impl<boost::undirected_tag,void *>,
1>            Bundle=CoordSegment,
1>            T=double
1>        ]
1>        C:\Libraries\boost_1_46_1\boost/graph/kruskal_min_spanning_tree.hpp(120): See declaration of 'boost::kruskal_minimum_spanning_tree'

为什么它会抱怨呢？

如何使我的 bundled_property_map 成为此 Kruskal MST 函数所需的正确 bgl_named_pa​​rams 参数？

4

1 回答 1

0

从定义的 adjacency_list 模板类继承根本不是一个好主意。删除这个继承解决了这个问题。使用 boost::graph 作为成员变量并将其他所有内容包装在一个类中会更好。

于 2013-09-05T07:14:04.733 回答