c++ - 从特定顶点执行深度优先算法

Question

我正在尝试通过使用 boost 图形库找到一种从特定顶点执行深度优先算法的方法。

Boost 库提供的深度优先算法评估从起始顶点到最后一个顶点的图。但是，如果必须从特定顶点搜索图形怎么办？

有什么建议么？

Answer 1

查看BGL 的文档。

有一个重载，您可以在其中提供起始顶点。

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)

Answer 2

BGL 提供了两种机制来设置 depth_first_search 的起始顶点。您可以使用需要提供 ColorMap 的重载运算符，也可以直接设置访问者的属性：

boost::depth_first_search(myGraph, boost::visitor(myVisitor).root_vertex(myVertex));

Answer 3

boost::depth_first_search(myGraph, boost::visitor(myVisitor).root_vertex(myVertex));

这只是一个使用对 depth_first_search() 调用的命名参数版本的示例。请参阅命名参数。我发现即使您确实指定了一个顶点而不是图的根，算法仍然会访问图中的所有顶点。它只会从您指定的那个开始。

要仅访问从指定顶点可到达的那些顶点，您需要使用 depth_first_visit 算法。这需要指定颜色图。这是一张对我有用的彩色地图。

    使用 Graph = boost::adjacency_list;
    使用 IndexMap = boost::property_map::const_type;
    IndexMap indexMap = boost::get(boost::vertex_index, m_graph);

    使用 ColorMap = boost::iterator_property_map;
    std::vector color_vec(num_vertices(m_graph));
    ColorMap colorMap(&color_vec.front(), indexMap);