Выполнение глубины первого поиска и ширины первого поиска в 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.

BFS теоретически лучше, если все ваши края имеют стоимость 1, но в boost :: graph требуется некоторое усилие (это просто пустая оболочка, и вам нужно реализовать своих собственных посетителей, чтобы сохранить расстояние от истоков).

Однако, чтобы использовать dijkstra, вам нужно добавить свойства Edge с весами по краям и использовать его в алгоритме.

В следующем примере http://www.boost.org/doc/libs/1_51_0/libs/graph/example/dijkstra-example.cpp вы можете развернуть кратчайший путь от s до t, посмотрев на карту предшественников: p [t] - это узел до t в кратчайшем пути.

Я надеюсь, что это достаточно :)