在Boost中执行深度优先搜索和宽度优先搜索

Question

我对Boost库和C++语言都很新颖。

我已经使用Boost创建了一个图并添加了顶点和边并在graphviz中输出了图。

现在我想先执行宽度优先和深度优先搜索，从顶点到图中所有其他顶点。

结果应该是从图的起点到其他顶点的最短路径。

如何在Boost中完成此操作？任何帮助，将不胜感激。

感谢提前一吨。

我还添加了我的源代码供您参考。

#include "stdafx.h" 
#include <iostream> 

#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/breadth_first_search.hpp> 
#include <boost/pending/indirect_cmp.hpp> 
#include <boost/range/irange.hpp> 
#include <boost/graph/graphviz.hpp> 

int main() 
{ 
      using namespace std; 
      using namespace boost; 


     // Property types 
      typedef property<vertex_name_t, std::string, 
      property<vertex_index2_t, int> > VertexProperties; 

     // Graph type 
      typedef adjacency_list<vecS, vecS, undirectedS, 
      VertexProperties> Graph; 

     // Graph instance 
      Graph g; 

     // Property accessors 
      property_map<Graph, vertex_name_t>::type 
      profinet_name = get(vertex_name, g); 
      property_map<Graph, vertex_index2_t>::type 
      profinet_index2 = get(vertex_index2, g); 

     // Create the vertices 
      typedef graph_traits<Graph>::vertex_descriptor Vertex; 
      Vertex u1; 
      u1 = add_vertex(g); 
      profinet_name[u1] = "Profinet 1"; 
      profinet_index2[u1] = 1; 

      Vertex u2; 
      u2 = add_vertex(g); 
      profinet_name[u2] = "Profinet 2"; 
      profinet_index2[u2] = 2; 

      Vertex u3; 
      u3 = add_vertex(g); 
      profinet_name[u3] = "Profinet 3"; 
      profinet_index2[u3] = 3; 

      Vertex u4; 
      u4 = add_vertex(g); 
      profinet_name[u4] = "Profinet 4"; 
      profinet_index2[u4] = 4; 

      Vertex u5; 
      u5 = add_vertex(g); 
      profinet_name[u5] = "Profinet 5"; 
      profinet_index2[u5] = 5; 

      Vertex u6; 
      u6 = add_vertex(g); 
      profinet_name[u6] = "Profinet 6"; 
      profinet_index2[u6] = 6; 


     // Create the edges 
      typedef graph_traits<Graph>::edge_descriptor Edge; 
      Edge e1; 
      e1 = (add_edge(u1, u2, g)).first; 

      Edge e2; 
      e2 = add_edge(u1, u4, g).first; 

      Edge e3; 
      e3 = (add_edge(u1, u6, g)).first; 

      Edge e4; 
      e4 = (add_edge(u2, u3, g)).first; 

      Edge e5; 
      e5 = (add_edge(u2, u4, g)).first; 

      Edge e6; 
      e6 = (add_edge(u2, u5, g)).first; 

      Edge e7; 
      e7 = (add_edge(u3, u6, g)).first; 

      Edge e8; 
      e8 = (add_edge(u6, u5, g)).first; 

      Edge e9; 
      e9 = (add_edge(u5, u4, g)).first; 


      write_graphviz(cout, g); 

      return 0; 


} 

Answer 1

如果要执行从a到b的最短路径，则应该使用Dijkstra算法。

如果所有边缘的成本都是1，BFS理论上会更好，但是在boost :: graph中它需要一些努力（它只是一个空壳，您需要实现自己的访问者以存储距离从起源）。

但是，为了使用dijkstra，您需要在边缘添加具有权重的边缘属性，并在算法中使用它。

在下面的示例http://www.boost.org/doc/libs/1_51_0/libs/graph/example/dijkstra-example.cpp中，可以通过查看前置映射来展开从s到t的最短路径：p [t]是t在最短路径之前的节点。

我希望这是足够的:)