c++ - 如何使用 boost 图库广度优先搜索创建遍历顶点的队列？

Question

我想使用 boost 图库广度优先搜索来返回在节点 1 上启动时访问的顶点队列。我阅读了文档，但仍然无法理解如何实现这一点。

下面的结果将按顺序返回一个队列:1,2,3,4 或 1,3,2,4

typedef boost::property<boost::edge_weight_t, unsigned int> EdgeWeightProperty;
typedef boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS, 
                              boost::no_property, EdgeWeightProperty> Graph;

//create graph and add edge
Graph g;
boost::add_edge(1,2,6,g);
boost::add_edge(2,3,6,g);
boost::add_edge(3,1,6,g);
boost::add_edge(3,4,6,g);

//Perform breadth first using boost and return result in a queue.

Answer 1

boost 图形库文档定义了 BFS Visitor concept其中指出

Users can define a class with the BFS Visitor interface and pass an object of the class to breadth_first_search(), thereby augmenting the actions taken during the graph search.

基于此和 bfs.cpp example完成您所要求的首选方法是将 boost::visitor 进行子类化或boost::default_bfs_visitor并覆盖其中的一个或多个

• initialize_vertex
• discover_vertex
• examine_vertex
• examine_edge
• tree_edge
• non_tree_edge
• gray_target
• black_target
• finish_vertex

对于您的用例，我认为最适合子类 boost::default_bfs_visitor并覆盖discover_vertex :

discover_vertex(s, g)

Invoked when a vertex is encountered for the first time. s is An object of type boost::graph_traits<Graph>::vertex_descriptor and g is an object of type Graph.

下面是具体如何做到这一点的示例，其中适当处理 std::queue对象来记录顶点。

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

typedef boost::property<boost::edge_weight_t, unsigned int> EdgeWeightProperty;
typedef boost::adjacency_list<boost::setS, boost::vecS, boost::undirectedS, 
                              boost::no_property, EdgeWeightProperty> Graph;

class BFSVisitor : public boost::default_bfs_visitor {
public:    
    BFSVisitor(std::queue<Graph::vertex_descriptor>& _v) : visited(_v){}
    void discover_vertex(Graph::vertex_descriptor s, const Graph &g) {
         visited.push(s); 
    }
    std::queue<Graph::vertex_descriptor>& visited;
};

int main() {
    Graph g;
    boost::add_edge(0,1,6,g);
    boost::add_edge(1,2,6,g);
    boost::add_edge(2,3,6,g);
    boost::add_edge(3,1,6,g);
    boost::add_edge(3,4,6,g);

    Graph::vertex_descriptor s = *(boost::vertices(g).first);
    std::queue<Graph::vertex_descriptor> q;
    BFSVisitor vis(q);
    boost::breadth_first_search(g, s, boost::visitor(vis));
    while (!vis.visited.empty()) {
        std::cout << vis.visited.front() << std::endl;
        vis.visited.pop();
    }
}

将输出

0
1
2
3
4

---

注意 - Boost 预计图表从顶点 0 开始，不是1 - 因此这条线

boost::add_edge(0,1,6,g);

如果从顶点 1 开始将不会有任何输出。