c – 如何在boost使用BFS中遍历图形

发布时间：2020-12-16 05:01:08 所属栏目：百科来源：网络整理

导读：我在编译一个非常简单的图表的BFS时遇到了问题.无论我做什么,我得到了关于不匹配的方法调用的各种编译器消息(我尝试过boost :: visitor并扩展boost :: default_bfs_visitor等) #include stdint.h#include iostream#include vector#include boost/graph/adjac

我在编译一个非常简单的图表的BFS时遇到了问题.无论我做什么,我得到了关于不匹配的方法调用的各种编译器消息(我尝试过boost :: visitor并扩展boost :: default_bfs_visitor等)

#include <stdint.h>
#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>

int main() {
  typedef boost::adjacency_list<boost::vecS,boost::hash_setS,boost::undirectedS,uint32_t,boost::no_property> graph_t;
  graph_t graph(4);
  graph_t::vertex_descriptor a = boost::vertex(0,graph);
  graph_t::vertex_descriptor b = boost::vertex(1,graph);
  graph_t::vertex_descriptor c = boost::vertex(2,graph);
  graph_t::vertex_descriptor d = boost::vertex(3,graph);
  graph[a] = 0;
  graph[b] = 1;
  graph[c] = 2;
  graph[d] = 3;
  std::pair<graph_t::edge_descriptor,bool> result = boost::add_edge(a,b,graph);
  result = boost::add_edge(a,c,1,graph);
  result = boost::add_edge(c,2,graph);
  class {
  public:
    void initialize_vertex(const graph_t::vertex_descriptor &s,graph_t &g) {
      std::cout << "Initialize: " << g[s] << std::endl;
    }
    void discover_vertex(const graph_t::vertex_descriptor &s,graph_t &g) {
      std::cout << "Discover: " << g[s] << std::endl;
    }
    void examine_vertex(const graph_t::vertex_descriptor &s,graph_t &g) {
      std::cout << "Examine vertex: " << g[s] << std::endl;
    }
    void examine_edge(const graph_t::edge_descriptor &e,graph_t &g) {
      std::cout << "Examine edge: " << g[e] << std::endl;
    }
    void tree_edge(const graph_t::edge_descriptor &e,graph_t &g) {
      std::cout << "Tree edge: " << g[e] << std::endl;
    }
    void non_tree_edge(const graph_t::edge_descriptor &e,graph_t &g) {
      std::cout << "Non-Tree edge: " << g[e] << std::endl;
    }
    void gray_target(const graph_t::edge_descriptor &e,graph_t &g) {
      std::cout << "Gray target: " << g[e] << std::endl;
    }
    void black_target(const graph_t::edge_descriptor &e,graph_t &g) {
      std::cout << "Black target: " << g[e] << std::endl;
    }
    void finish_vertex(const graph_t::vertex_descriptor &s,graph_t &g) {
      std::cout << "Finish vertex: " << g[s] << std::endl;
    }
  } bfs_visitor;
  boost::breadth_first_search(graph,a,bfs_visitor);
  return 0;
}

如何使用bfs_visitor访问图表？

PS.我已经看到并编译了“How to create a C++ Boost undirected graph and traverse it in depth first search (DFS) order?”,但它没有帮助.

解决方法

您可以在 here中看到breadth_first_search的重载列表.如果您不想指定每个参数,则需要使用命名参数版本.它看起来像这样：

breadth_first_search(graph,boost::visitor(bfs_visitor));

如果您已在图形定义中使用vecS作为VertexList存储,或者已构建并初始化内部vertex_index属性映射,则此方法可以正常工作.由于您使用的是hash_setS,因此需要将调用更改为：

breath_first_search(graph,boost::visitor(bfs_visitor).vertex_index_map(my_index_map));

您已在uint32_t捆绑属性中使用索引映射.您可以使用get(boost :: vertex_bundle,graph)来访问它.

你的访客也有问题.您应该从boost :: default_bfs_visitor派生它,并且您的成员函数的graph_t参数需要是const限定的.

完整代码：

#include <stdint.h>
#include <iostream>
#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>

typedef boost::adjacency_list<boost::vecS,boost::no_property> graph_t;


struct my_visitor : boost::default_bfs_visitor{

    void initialize_vertex(const graph_t::vertex_descriptor &s,const graph_t &g) const {
      std::cout << "Initialize: " << g[s] << std::endl;
    }
    void discover_vertex(const graph_t::vertex_descriptor &s,const graph_t &g) const {
      std::cout << "Discover: " << g[s] << std::endl;
    }
    void examine_vertex(const graph_t::vertex_descriptor &s,const graph_t &g) const {
      std::cout << "Examine vertex: " << g[s] << std::endl;
    }
    void examine_edge(const graph_t::edge_descriptor &e,const graph_t &g) const {
      std::cout << "Examine edge: " << g[e] << std::endl;
    }
    void tree_edge(const graph_t::edge_descriptor &e,const graph_t &g) const {
      std::cout << "Tree edge: " << g[e] << std::endl;
    }
    void non_tree_edge(const graph_t::edge_descriptor &e,const graph_t &g) const {
      std::cout << "Non-Tree edge: " << g[e] << std::endl;
    }
    void gray_target(const graph_t::edge_descriptor &e,const graph_t &g) const {
      std::cout << "Gray target: " << g[e] << std::endl;
    }
    void black_target(const graph_t::edge_descriptor &e,const graph_t &g) const {
      std::cout << "Black target: " << g[e] << std::endl;
    }
    void finish_vertex(const graph_t::vertex_descriptor &s,const graph_t &g) const {
      std::cout << "Finish vertex: " << g[s] << std::endl;
    }
  };

int main() {
  graph_t graph(4);
  graph_t::vertex_descriptor a = boost::vertex(0,graph);

  my_visitor vis;

  breadth_first_search(graph,boost::visitor(vis).vertex_index_map(get(boost::vertex_bundle,graph)));
  return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!