c + + Boost图库：建立无向图搜索访问顶点的载体？ [英] C++ Boost graph library: Building a vector of vertices visited in an undirected graph search?

问题描述

从我可以收集如何使用BGL，以便从我需要做的沿

东西线已知的根节点调用图的DFS

 类MyVisitor：公​​众的boost :: default_dfs_visitor
{
  上市：
  无效discover_vertex（MyVertex V，常数为MyGraph和放大器; G）常量
 {
    CERR＆LT;＆LT; V族;＆下; ENDL;
    返回;
 }};
 无效bfsMethod（图G，INT rootNodeId）
 {   提高:: undirected_dfs（G，顶点（rootNodeId，G），提振::访问者（VIS））; }
 

现在我不知道我如何改变这一点，以便的std ::矢量 vertexId（或指针）是建立为DFS访问所有顶点在图中类似的方式到最小生成树算法如何使用如

 的std ::矢量＆lt; JPEdge＆GT; spanning_tree;
kruskal_minimum_spanning_tree（克，性病:: back_inserter（spanning_tree））;
 

解决方案

的载体必须是你的访客中的一员。在 discover_vertex 功能，只需轻轻一按发现元素插入载体。

 类MyVisitor：公​​众的boost :: default_dfs_visitor
{
  上市：
  无效discover_vertex（MyVertex V，常数为MyGraph和放大器; G）常量
 {
    CERR＆LT;＆LT; V族;＆下; ENDL;
    vv.push_back（五）;
    返回;
 }  矢量＆lt; MyVertex＆GT; GetVector（）const的{返回VV; } 私人的：
 矢量＆lt; MyVertex＆GT; VV;};无效bfsMethod（图G，INT rootNodeId）
{
  MyVisitor可见;
  提高:: undirected_dfs（G，顶点（rootNodeId，克），VIS）;
  矢量＆lt; MyVertex＆GT; VCTR = vis.GetVector（）; }
 

From what I can gather of how to use BGL in order to invoke a DFS of a graph from a known root node I need to do something along the lines of

class MyVisitor : public boost::default_dfs_visitor
{
  public:
  void discover_vertex(MyVertex v, const MyGraph& g) const
 {
    cerr << v << endl;
    return;
 }

};


 void bfsMethod(Graph g, int rootNodeId)
 {

   boost::undirected_dfs(g, vertex(rootNodeId,g), boost::visitor(vis)); 

 }

Now I am not sure how I alter this so that std::vector of vertexId's (or pointers) is built as the DFS visits all vertices in the graph in a similar way to how the minimum spanning tree algorithm can be used e.g.

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

解决方案

The vector must be a member of your visitor. In the discover_vertex function, just push the discovered element into the vector.

class MyVisitor : public boost::default_dfs_visitor
{
  public:
  void discover_vertex(MyVertex v, const MyGraph& g) const
 {
    cerr << v << endl;
    vv.push_back(v);
    return;
 }

  vector<MyVertex> GetVector() const {return vv; }

 private: 
 vector<MyVertex> vv;

};

void bfsMethod(Graph g, int rootNodeId)
{
  MyVisitor vis;
  boost::undirected_dfs(g, vertex(rootNodeId,g), vis); 
  vector<MyVertex> vctr = vis.GetVector();

 }

这篇关于c + + Boost图库：建立无向图搜索访问顶点的载体？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！