使用 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;
}

我正在尝试调用 breadth_first_search，从顶点 0 开始，并获得到图中所有其他顶点的最短距离。我如何错误地调用该函数？推荐使用什么容器来存储结果？

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 和 GCC give different diagnostics，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

确实检查 the documentation 显示没有采用 2 个参数的重载。你至少需要三分之一，boost::named_parameters object

让我们坚持一个存根：

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

现在它应该告诉我们缺少哪些参数，如果有的话：Success!

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

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";

打印 Live On Compiler Explorer:

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

BONUS/Caveats

注意：您的图形模型“具有”edge_weight（尽管您的示例从未将其初始化为 non-zero 值）。如果它们是相关的，那么 BFS 是不够的。对于 non-negative 权重，你应该使用 Dijkstra，在我看来它更容易使用：

Live

#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

使用 BFS 查找到顶点的距离

Find distances to vertices using BFS

c++

boost

boost-graph

BONUS/Caveats