如何遍历提振使用BFS图

本文介绍了如何遍历提振使用BFS图的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我有问题越来越编译一个非常简单的图形的BFS。无论我做什么我得到了约无与伦比的方法调用不同的编译器消息（我试过的boost ::访问者并延长的boost :: default_bfs_visitor 等）

I have problems getting to compile the BFS of a very simple graph. Whatever I do I got various compiler messages about unmatched method calls (I've tried boost::visitor and extending boost::default_bfs_visitor etc.)

#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, 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, 0, graph); result = boost::add_edge(a, c, 1, graph); result = boost::add_edge(c, b, 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创建一个C ++提升无向图和深度遍历它优先搜索（DFS）的命令？但它并没有帮助。

PS. I've seen and compiled "How to create a C++ Boost undirected graph and traverse it in depth first search (DFS) order?" but it didn't helped.

推荐答案

您可以看到的这里 breadth_first_search 的重载列表。如果你不想指定参数中的每一个你需要使用命名参数版本。它是这样的：

You can see here a list of the overloads of breadth_first_search. If you don't want to specify every one of the parameters you need to use the named-parameter version. It would look like this:

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

这将工作的是，如果你使用了血管内皮细胞或你的VertexList时，存储在您的图形清晰度，如果你已经建造并初始化内部的vertex_index属性映射。由于您使用的 hash_setS 你需要调用更改为：

This would work as is if you had used vecS as your VertexList storage in your graph definition or if you had constructed and initialized an internal vertex_index property map. Since you are using hash_setS you need to change the invocation to:

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

您已经使用在你的uint32_t的捆绑属性的索引图。您可以使用 GET（升压:: vertex_bundle，图表）来访问它。

You are already using an index map in your uint32_t bundled property. You can use get(boost::vertex_bundle, graph) to access it.

有也有访问者的一个问题。你应该从的boost :: default_bfs_visitor 和你的成员函数 graph_t 参数获得它需要被const修饰。

There was also a problem with your visitor. You should derive it from boost::default_bfs_visitor and the graph_t parameter of your member functions needs to be const qualified.

全部code：

#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::hash_setS, boost::undirectedS, uint32_t, uint32_t, 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); 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, 0, graph); result = boost::add_edge(a, c, 1, graph); result = boost::add_edge(c, b, 2, graph); my_visitor vis; breadth_first_search(graph, a, boost::visitor(vis).vertex_index_map(get(boost::vertex_bundle,graph))); return 0; }