1

Привет всем! имеется неориентированные невзвешенный граф...по графу хочу найти кратчайший путь между двумя вершинами...я так понимаю нужно использовать алгоритм поиск в ширину... для решение задачи я использую boost BGL... для поиска в ширину предназначен алгоритм breadth_firstsearch, и чтобы этот алгоритм искал кратчайший путь, нужно написать класс Посетитель который унаследован от boost::default_bfs____visitor ... как этот класс реализовать, чтобы показывал кратчайший путь между двумя вершинами ? пришлите пример или ссылку на какую либо статью или книгу (только не "C++ Boost Graph Library. Библиотека программиста") !

1 ответ 1

1

А чем вам не угодила книга "C++ Boost Graph Library. Библиотека программиста"? Там может быть всё очень запутано на первый взгляд, но если с ней немного повозиться, то вещи становятся яснее. Ещё, на мой взгляд, есть очень неплохая Wiki по BGL, когда-то даже пользовался ей. Так вот, в этой документации есть пример применения посетителя, унаследованного от default_dfs_visitor - BreadthFirstSearch.cpp

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>

#include <iostream>

// тот самый посетитель, который просто печатает порядок обхода вершин в графе
class custom_bfs_visitor : public boost::default_bfs_visitor
{
public:

  // печатать тут
  template < typename Vertex, typename Graph >
  void discover_vertex(Vertex u, const Graph & g) const
  {
    std::cout << u << std::endl;
  }
};

int main()
{
  typedef boost::adjacency_list < boost::vecS, boost::vecS, boost::undirectedS > graph_t; // тип графа

  graph_t g; // сам граф

  add_edge(0, 1, g); // добавление рёбер в граф
  add_edge(0, 2, g);
  add_edge(1, 3, g);
  add_edge(0, 4, g);

  custom_bfs_visitor vis; // наш посетитель
  breadth_first_search(g, vertex(0, g), visitor(vis)); // вызов функции поиска в ширину

  // на выходе должно быть 0 1 2 4 3
  return EXIT_SUCCESS;
}

Ещё мне когда-то самому на этом форуме здорово помогли, так что можете повникать.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.