如何创建 C++ Boost 无向图并以深度优先搜索 (DFS) 顺序遍历它?
// Boost DFS example on an undirected graph.
// Create a sample graph, traverse its nodes
// in DFS order and print out their values.
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <iostream>
using namespace std;
typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS> MyGraph;
typedef boost::graph_traits<MyGraph>::vertex_descriptor MyVertex;
class MyVisitor : public boost::default_dfs_visitor
{
public:
void discover_vertex(MyVertex v, const MyGraph& g) const
{
cerr << v << endl;
return;
}
};
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);
MyVisitor vis;
boost::depth_first_search(g, boost::visitor(vis));
return 0;
}
这是一个现代 C++ 解决方案,支持从任何给定节点开始的前序和后序遍历。
通过使用 EventVisitor 和带有已实现的 [
operator()
] 方法的访问者模板 (https://www.boost.org/doc/libs/1_74_0/libs/graph/doc/EventVisitorList.html),我们可以轻松切换遍历顺序(前序:on_discover_vertex
或后序:on_finish_vertex
)。
// Pre-order and post-order DFS traversal on an undirected graph.
#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>>;
template <typename Event> struct MyVisitor : public boost::null_visitor {
// Capture event type to allow both pre-order and post-order traversal
using event_filter = Event;
template <typename Vertex, typename Graph>
void operator()(Vertex v, Graph &g) {
std::cout << v << std::endl;
}
};
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 map = boost::get(boost::vertex_color, g);
// Pre-order: 0 1 2 3
std::cout << "pre-order traversal : \n";
boost::depth_first_search(
g, boost::make_dfs_visitor(MyVisitor<boost::on_discover_vertex>()), map,
root);
// Post-order: 2 3 1 0
std::cout << "post-order traversal : \n";
boost::depth_first_search(
g, boost::make_dfs_visitor(MyVisitor<boost::on_finish_vertex>()), map,
root);
}