c++ - 如何使用 Boost.Graph 从特定节点遍历图形分支？

Question

将不胜感激。
我有树结构，并希望在层次结构方面按出现顺序打印节点。

例如我要遍历 N1 的所有 child :

[N0, N1[N2, N3, N4[N5], N6]

我希望得到

N1 N2 N3 N4 N5

但是我收到了一些不同的东西，使用这个片段:

    typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS> MyGraph;
    typedef boost::graph_traits<MyGraph>::vertex_descriptor MyVertex;

        class MyVisitor : public boost::default_dfs_visitor
        {
        public:
          void discover_vertex(MyVertex v, const MyGraph& g) const
          {
            cerr << v << endl;
            return;
          }
        };

int _tmain(int argc, _TCHAR* argv[])
{    
     MyGraph g;

        boost::add_edge(0, 1, g);
        boost::add_edge(0, 2, g);
        boost::add_edge(0, 3, g);
        boost::add_edge(2, 4, g);

        MyVisitor vis;

        //2 - N2 node 
        boost::depth_first_search(g,  boost::visitor(vis).root_vertex(2) );
        return 0;

}

输出是:

2
0
1
3
4

但我希望(2 个和所有 child )

2
4

请帮忙。

谢谢。

Answer 1

你的图是无向的，这意味着后边 (0,2) 也被占用了。

尝试将 undirectedS 更改为 directedS

为了避免报告从其他根发现的顶点，您可以调整访问者以检测第一个 root 何时完成:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/visitors.hpp>
#include <iterator>

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS>;
using VertexPair = std::pair<Graph::vertex_descriptor, Graph::vertex_descriptor>;

struct Visitor : boost::default_dfs_visitor {
    using V = Graph::vertex_descriptor;

    void discover_vertex(V v, const Graph& /*g*/) {
        if (!root) {
            root = v;
        }
        if (!done) std::cerr << v << "\n";
    }

    void finish_vertex(V v, const Graph& /*g*/) {
        done |= (root == v);
    }
  private:
    bool done = false;
    boost::optional<V> root;
};

int main() {
    // [N0, N1[N2, N3, N4[N5], N6] :
    // VertexPair const data[] { {1, 2}, {1, 3}, {1, 4}, {4, 5}, };
    VertexPair const data[] { {0, 1}, {0, 2}, {0, 3}, {2, 4}, };
    Graph g(std::begin(data), std::end(data), 7);

    boost::depth_first_search(g, boost::visitor(Visitor()).root_vertex(2));
    //boost::write_graphviz(std::cout, g);
}

打印

2
4

更新

如果为了 boost 效率你想避免遍历树的剩余部分，你可以使用depht_first_visit，它可以接受一个TerminatorFunc。在这里，我将其添加到同一个访问者:

Live On Coliru

// in Visitor:

    // the TerminatorFunc
    bool operator()(V, Graph const&) const { return done; }

// later:

    Visitor vis_termfuc; // combines visitor and terminator functions
    std::vector<boost::default_color_type> colormap(num_vertices(g));
    boost::depth_first_visit(g, 2, vis_termfuc, colormap.data(), vis_termfuc);