从特定顶点执行深度优先算法
我正在尝试找到一种使用 boost 图库从特定顶点执行深度优先算法的方法。
Boost 库提供的深度优先算法评估从起始顶点到最后顶点的图。但是如果必须从特定顶点搜索图怎么办？
有什么建议吗？
I am trying to find a way to perform the depth-first algorithm from a specific vertex by using the boost graph library.
The depth-first algorithm provided by Boost library evaluates the graph beginning from the start vertex to the last vertex. But what if the graph has to be searched from a specific vertex?
Any suggestions?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
BGL 提供了两种机制来设置深度优先搜索的起始顶点。您可以使用需要提供 ColorMap 的重载运算符，也可以直接设置访问者的属性：
boost::depth_first_search(myGraph, boost::visitor(myVisitor).root_vertex(myVertex));
BGL Provides two mechanisms for setting the starting vertex of depth_first_search. You can either use the overload operator which requires supplying a ColorMap, or you can directly set the property of your visitor:
boost::depth_first_search(myGraph, boost::visitor(myVisitor).root_vertex(myVertex));
这只是使用深度优先搜索（）调用的命名参数版本的示例。请参阅命名参数。我发现即使您指定了除图的根之外的顶点作为起始点，算法仍然会访问图中的所有顶点。它只会从您指定的那个开始。
要仅访问从指定顶点可到达的顶点，您需要使用深度优先访问算法。这需要指定颜色图。这是对我有用的彩色图。
using Graph = boost::adjacency_list; using IndexMap = boost::property_map::const_type; IndexMap indexMap = boost::get(boost::vertex_index, m_graph); using ColorMap = boost::iterator_property_map; std::vector color_vec(num_vertices(m_graph)); ColorMap colorMap(&color_vec.front(), indexMap);This is simply an example of using the named parameter version of the call to depth_first_search(). See Named Parameters. I found that even if you do specify a vertex other than the root of the graph to start from, the algorithm will still visit all of the vertices in the graph. It will just start from the one you specify.
To visit only those vertices reachable from a specified vertex you need to use the depth_first_visit algorithm. This requires a color map to be specified. Here's a color map that worked for me.
using Graph = boost::adjacency_list; using IndexMap = boost::property_map::const_type; IndexMap indexMap = boost::get(boost::vertex_index, m_graph); using ColorMap = boost::iterator_property_map; std::vector color_vec(num_vertices(m_graph)); ColorMap colorMap(&color_vec.front(), indexMap);请查看 BGL 文档。
有一个过载，您可以在其中提供起始顶点。
Have a look at BGL's documentation.
There is an overload where you can provide the start vertex.