使用 BFS 查找到顶点的距离

Question

using namespace boost;

typedef adjacency_list<setS, vecS, bidirectionalS,
no_property,
property<edge_weight_t, float>> Graph_type;

typedef graph_traits<Graph_type>::edge_iterator edge_iterator;


int main() {
    // create graph
    Graph_type g;
    add_edge(0,1,g);
    add_edge(1,2,g);
    add_edge(2,0,g);

    
    // output graph
    std::pair<edge_iterator, edge_iterator> ei = edges(g);
    for (edge_iterator edge_iter = ei.first; edge_iter != ei.second; ++edge_iter)
        std::cout << source(*edge_iter, g) << " - " << target(*edge_iter, g) << "\n";

    // attempt to find shortest distance from vetex 0 to all other vertices
    breadth_first_search(g,0);
    return 0;
}

我试图从顶点0开始调用vartth_first_search，并获得与图中所有其他顶点的最短距离。我如何错误地调用该功能？建议使用哪种容器来存储结果？

Answer 1

首先现代化代码：

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

using Graph_type =
    boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS,
                          boost::no_property,
                          boost::property<boost::edge_weight_t, float>>;

int main() {
    // create graph
    Graph_type g;
    add_edge(0, 1, g);
    add_edge(1, 2, g);
    add_edge(2, 0, g);

    // output graph
    for (auto e : boost::make_iterator_range(edges(g)))
        std::cout << e << "\n";

    // attempt to find shortest distance from vetex 0 to all other vertices
    breadth_first_search(g, 0);
}

clang and GCC 给出不同的诊断 GCC是最详尽的：

<source>: In function 'int main()':
<source>:24:32: error: no matching function for call to 'breadth_first_search(Graph_type&, int)'
   24 |     boost::breadth_first_search(g, 0);
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
In file included from <source>:2:
/opt/compiler-explorer/libs/boost_1_78_0/boost/graph/breadth_first_search.hpp:123:6: note: candidate: 'template<class VertexListGraph, class SourceIterator, class Buffer, class BFSVisitor, class ColorMap> void boost::breadth_first_search(const VertexListGraph&, SourceIterator, SourceIterator, Buffer&, BFSVisitor, ColorMap)'
  123 | void breadth_first_search(const VertexListGraph& g,
      |      ^~~~~~~~~~~~~~~~~~~~
/opt/compiler-explorer/libs/boost_1_78_0/boost/graph/breadth_first_search.hpp:123:6: note:   template argument deduction/substitution failed:
<source>:24:32: note:   candidate expects 6 arguments, 2 provided
   24 |     boost::breadth_first_search(g, 0);
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
In file included from <source>:2:
/opt/compiler-explorer/libs/boost_1_78_0/boost/graph/breadth_first_search.hpp:141:6: note: candidate: 'template<class VertexListGraph, class Buffer, class BFSVisitor, class ColorMap> void boost::breadth_first_search(const VertexListGraph&, typename boost::graph_traits<Graph>::vertex_descriptor, Buffer&, BFSVisitor, ColorMap)'
  141 | void breadth_first_search(const VertexListGraph& g,
      |      ^~~~~~~~~~~~~~~~~~~~
/opt/compiler-explorer/libs/boost_1_78_0/boost/graph/breadth_first_search.hpp:141:6: note:   template argument deduction/substitution failed:
<source>:24:32: note:   candidate expects 5 arguments, 2 provided
   24 |     boost::breadth_first_search(g, 0);
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
In file included from <source>:2:
/opt/compiler-explorer/libs/boost_1_78_0/boost/graph/breadth_first_search.hpp:328:6: note: candidate: 'template<class VertexListGraph, class P, class T, class R> void boost::breadth_first_search(const VertexListGraph&, typename boost::graph_traits<Graph>::vertex_descriptor, const boost::bgl_named_params<T, Tag, Base>&)'
  328 | void breadth_first_search(const VertexListGraph& g,
      |      ^~~~~~~~~~~~~~~~~~~~
/opt/compiler-explorer/libs/boost_1_78_0/boost/graph/breadth_first_search.hpp:328:6: note:   template argument deduction/substitution failed:
<source>:24:32: note:   candidate expects 3 arguments, 2 provided
   24 |     boost::breadth_first_search(g, 0);
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
Compiler returned: 1

确实是检查：确实是检查文档 没有表现出2个参数。您至少需要三分之一， boost :: nesual_parameters 对象

让我们坚持使用：

breadth_first_search(g, 0, boost::no_named_parameters{});

现在应该告诉我们丢失了哪些参数，如果有：成功！

您可能要传递参数的原因是，如果您的图形没有隐式属性映射（例如 vertex_index_map ），或者当您想覆盖util/out的默认值时， 访问者。在您的情况下，您很有可能要覆盖IT，因为否则您将无法访问问题的答案：

std::vector<size_t> distances(num_vertices(g));
auto recorder = record_distances(distances.data(), boost::on_tree_edge{});

breadth_first_search(g, 0, visitor(make_bfs_visitor(recorder)));

for (auto v : boost::make_iterator_range(vertices(g)))
    std::cout << "distance 0 .. " << v << ": " << distances.at(v) << "\n";

prints 在编译器资源管理器上实时：

(0,1)
(1,2)
(2,0)
distance 0 .. 0: 0
distance 0 .. 1: 1
distance 0 .. 2: 2

奖励/警告

警告：您的图形模型“ edge> edge> edge_weight （尽管您的示例从未将其初始化为非零值）。如果它们是相关的，那么BFS是不够的。对于非负重的重量，您应该使用Dijkstra，在我看来，这恰好更容易使用：

“ nofollow noreferrer ”>实时

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <iostream>

using G = boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS,
                                boost::no_property,
                                boost::property<boost::edge_weight_t, float>>;
using V = G::vertex_descriptor;

int main() {
    // create graph
    G g;
    add_edge(0, 1, 30, g);
    add_edge(1, 2, 43, g);
    add_edge(2, 0, 5, g);

    // output graph
    auto wmap = get(boost::edge_weight, g);
    for (auto e : boost::make_iterator_range(edges(g)))
        std::cout << e << " weight " << wmap[e] << "\n";

    // attempt to find shortest distance from vetex 0 to all other vertices
    auto s = vertex(0, g);
    assert(s == 0);

    std::vector<size_t> distances(num_vertices(g));
    boost::dijkstra_shortest_paths(g, s, boost::distance_map(distances.data()));

    for (auto v : boost::make_iterator_range(vertices(g)))
        std::cout << "distance 0 .. " << v << ": " << distances.at(v) << "\n";
}

打印

(0,1) weight 30
(1,2) weight 43
(2,0) weight 5
distance 0 .. 0: 0
distance 0 .. 1: 30
distance 0 .. 2: 73

---