在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在最短路徑之前的節點。

我希望這是足夠的:)