为 depth_first_search 定义 ColorMap 的最简单方法

Question

我想使用 depth_first_search 算法。因为我需要指定起始顶点的 DFS 版本，我也必须定义一个 ColorMap。这就是我想要的功能使用 :

template <class Graph, class DFSVisitor, class ColorMap>
void depth_first_search(const Graph& g, DFSVisitor vis, ColorMap color, 
             typename graph_traits<Graph>::vertex_descriptor start)

https://www.boost.org/doc/libs/1_67_0/libs/graph/doc/depth_first_search.html

由于地图与我无关，所以默认的 ColorMap 就足够了。你能告诉我如何创建它并将其作为参数传递给 depth_first_search 吗？

Answer 1

只需使用命名参数重载，这样您就可以在使用默认颜色贴图的同时指定起始顶点。

template <class Graph, class class P, class T, class R>
void depth_first_search(Graph& G, const bgl_named_params<P, T, R>& params);

示例：

boost::depth_first_search(graph, boost::root_vertex(start_vertex));

Answer 2

我同意0x5453的回答。使用命名参数重载更容易。但是如果你确实想知道如何初始化一个 ColorMap 对象，这里就是答案。

Default: an iterator_property_map created from a std::vector of default_color_type of size num_vertices(g) and using the i_map for the index map.

Graph g;

/*
 * do something with graph
 */

// number of colors should be the same as number of vertices.
std::vector<boost::default_color_type> colors(boost::num_vertices(g));

// create a ColorMap object (cpp_version < 17)
auto color_map = boost::make_iterator_property_map(colors.begin(),
    boost::get(boost::vertex_index, g));

// In C++17, make_iterator_property_map isn't necessary, as we have class 
// template argument deduction
boost::iterator_property_map color_map(colors.begin(),
    boost::get(boost::vertex_index, g));

这里 make_iterator_property_map 接受两个参数，returns 一个 iterator_property_map。第一个参数是颜色值的迭代器，第二个参数是图的顶点索引和 colors 索引之间的映射。

为 depth_first_search 定义 ColorMap 的最简单方法

Simplest way to define ColorMap for depth_first_search

c++

boost

boost-graph