C++ Boost 图库：构建无向图搜索中访问的顶点向量？

Question

据我所知，如何使用 BGL 来从已知的根节点调用图形的 DFS，我需要按照以下方式做一些事情

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)); 

 }

现在我不知道如何改变它，以便在 DFS 访问图中的所有顶点时构建 vertexId（或指针）的

std::vector

，其方式与最小生成树算法的使用方式类似，例如

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

Answer 1

引导者必须是您访客的成员。在

discover_vertex

函数中，只需将发现的元素推入向量即可。

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();

 }

Answer 2

因为

depth_first_search

和

undirected_dfs

都是按值传递

DFSVisitor vis

，所以我们不能用

std::vector<>

来存储遍历到的顶点，否则退出

depth_first_search

或

undirected_dfs

后其大小始终为0。相反，我们可以使用

std::shared_ptr<std::vector<>>

或

static std::vector<>

来存储顶点。在我看来，使用

static

数据成员更简单且更具表现力。

这里我们可以用

discover_vertex()

得到前序遍历，用

finish_vertex

得到后序遍历。请参阅DFS 访客了解更多详情。

Coliru 直播

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <iostream>

using MyGraph = boost::adjacency_list<
    boost::listS, boost::vecS, boost::undirectedS,
    boost::property<boost::vertex_color_t, boost::default_color_type>>;

using MyVertex = boost::graph_traits<MyGraph>::vertex_descriptor;

struct MyDFSVisitor : public boost::default_dfs_visitor {
  inline static std::vector<MyVertex> m_preorder_vertices;
  inline static std::vector<MyVertex> m_postorder_vertices;

  void discover_vertex(MyVertex v, const MyGraph &g) {
    m_preorder_vertices.push_back(v);
  }

  void finish_vertex(MyVertex v, const MyGraph &g) {
    m_postorder_vertices.push_back(v);
  }
};

int main() {
  MyGraph g{};
  boost::add_edge(0, 1, g);
  boost::add_edge(0, 2, g);
  boost::add_edge(1, 2, g);
  boost::add_edge(1, 3, g);

  auto root = boost::vertex(0, g);
  auto color_map = boost::get(boost::vertex_color, g);

  MyDFSVisitor vis;
  boost::depth_first_search(g, vis, color_map, root);
  std::cout << "pre-order traversal : \n"; // 0 1 2 3
  for (auto v : vis.m_preorder_vertices) {
    std::cout << v << std::endl;
  }
  std::cout << "post-order traversal : \n"; // 2 3 1 0
  for (auto v : vis.m_postorder_vertices) {
    std::cout << v << std::endl;
  }
}

请注意

inline static

是 C++17 功能。