How to create a C++ Boost undirected graph and traverse it in depth first search (DFS) order?

Question

How to create a C++ Boost undirected graph and traverse it in depth first search (DFS) order?

Answer 1

// 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;
}

Answer 2

Live on Coliru

Here is a modern C++ solution supporting both pre-order and post-order traversal starting from any given node.

By using EventVisitor and a visitor template with an implemented [operator()] method (https://www.boost.org/doc/libs/1_74_0/libs/graph/doc/EventVisitorList.html), we can toggle traversal order (pre-order: on_discover_vertex or post-order: on_finish_vertex) easily.

// 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 color_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>()), color_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>()), color_map,
      root);
}