使用图形权重提升深度第一个访问者最小生成树

1 回答

• 4

  MyVisitor vis();
  

  这是一个函数声明 . 见Most Vexing Parse

  boost::depth_first_search(spanning_tree, visitor(vis));
  

  这称为 std::list<Edge> 上的图算法 . depth_first_search requires a graph that models the right graph concepts：

  std :: list既不模型也不模拟 .

  建议

  您可以构建一个仅包含MST集边缘的图形 . 您链接到的问题的答案尝试了 .

  但是，创建同一图形的 filtered_graph<> 视图似乎更容易，更有效，因此边缘属性可通过相同的机制简单地获得 .

  首先，让我们更喜欢在 set<> 而不是 list<> 中获取MST边缘：

  struct InSpanning {
      std::set<Edge> edges;
      bool operator()(Edge e) const { return edges.count(e); }
  } spanning;
  
  boost::kruskal_minimum_spanning_tree(g, std::inserter(spanning.edges, spanning.edges.end()));
  

  你会注意到的有趣的事情是 InSpanning 也是一个函数对象，可用作 filtering_graph 的过滤谓词：

  boost::filtered_graph<MyGraph, InSpanning, boost::keep_all> mst(g, spanning, {});
  

  现在你可以调用de DFS：

  boost::depth_first_search(mst, visitor(vis));
  

  我稍微调整了访问者：

  struct MyVisitor : boost::default_dfs_visitor {
      template <typename Graph>
      void tree_edge(Edge e, const Graph& g) {
          std::cout << "Visiting: " << e << " with weight " << get(boost::edge_weight, g, e) << "\n";
      }
  };
  

  注意：

  • 它不再对 MyGraph 类型进行硬编码（因为filtered_graph具有不同的类型） .

  • 它打印您想要查看的信息 .

  现场演示

  Live On Coliru

  #include <boost/graph/adjacency_list.hpp>
  #include <boost/graph/filtered_graph.hpp>
  #include <boost/graph/depth_first_search.hpp>
  #include <boost/graph/kruskal_min_spanning_tree.hpp>
  #include <iostream>
  
  #include <string>
  #include <vector>
  
  typedef boost::property<boost::edge_weight_t, double> EdgeWeightProperty;
  typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::no_property, EdgeWeightProperty>
      MyGraph;
  
  typedef MyGraph::edge_descriptor Edge;
  
  struct MyVisitor : boost::default_dfs_visitor {
      template <typename Graph>
      void tree_edge(Edge e, const Graph& g) {
          std::cout << "Visiting: " << e << " with weight " << get(boost::edge_weight, g, e) << "\n";
      }
  };
  
  void run_mst_test() {
      MyGraph g;
      boost::add_edge(0, 1, 0.7, g);
      boost::add_edge(0, 2, 0.1, g);
  
      boost::add_edge(1, 2, 0.3, g);
      boost::add_edge(1, 0, 0.7, g);
      boost::add_edge(1, 3, 0.8, g);
      boost::add_edge(1, 4, 0.2, g);
  
      boost::add_edge(2, 1, 0.3, g);
      boost::add_edge(2, 0, 0.1, g);
      boost::add_edge(2, 5, 0.1, g);
      boost::add_edge(2, 4, 0.5, g);
  
      boost::add_edge(3, 1, 0.8, g);
  
      boost::add_edge(4, 1, 0.2, g);
      boost::add_edge(4, 2, 0.5, g);
  
      boost::add_edge(5, 2, 0.1, g);
  
      struct InSpanning {
          std::set<Edge> edges;
          bool operator()(Edge e) const { return edges.count(e); }
      } spanning;
  
      boost::kruskal_minimum_spanning_tree(g, std::inserter(spanning.edges, spanning.edges.end()));
  
      MyVisitor vis;
      boost::filtered_graph<MyGraph, InSpanning, boost::keep_all> mst(g, spanning, {});
      boost::depth_first_search(mst, visitor(vis));
  }
  
  int main() {
      run_mst_test();
  }
  

  打印

  Visiting: (0,2) with weight 0.1
  Visiting: (2,1) with weight 0.3
  Visiting: (1,3) with weight 0.8
  Visiting: (1,4) with weight 0.2
  Visiting: (2,5) with weight 0.1
  

  回复于 2024-04-29T18:46:41+08:00