提升DFS后退(_E)

由于你的图是无向的,所以任何树的边都是后边。这个 documentation for DFSVisitor 没有不提到这一点。

对于无向图,树边和后边之间存在一些模糊性,因为边(u,v)和(v,u)是同一条边,但两者都是 tree_edge() 和 back_edge() 将调用函数。

解决这种模糊性的一种方法是记录树的边缘,然后忽略已经标记为树边缘的后边缘。记录树边缘的一种简单方法是在tree_edge事件点记录前置。

以最直接的方式实现这一点: Live on Coliru

#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>

namespace {
    using namespace boost;

    typedef adjacency_list<vecS, vecS, undirectedS, no_property, property<edge_weight_t, int> > Graph;
    typedef graph_traits<Graph>::edge_descriptor Edge;
    typedef std::set<Edge> EdgeSet;
}

struct MyVisitor : default_dfs_visitor {
    MyVisitor(EdgeSet& tree_edges) : tree_edges(tree_edges) {}

    void tree_edge(Edge e, const Graph& g) const {
        std::cerr << "tree_edge " << e << std::endl;
        tree_edges.insert(e);
    }
    void back_edge(Edge e, const Graph& g) const {
        if (tree_edges.find(e) == tree_edges.end())
            std::cerr << "back_edge " << e << std::endl;
    }

  private: 
    EdgeSet& tree_edges;
};

int main() {
    Graph g;
    add_edge(0, 1, g);
    add_edge(0, 2, g);

    std::set<Edge> tree_edges;
    MyVisitor vis(tree_edges);

    depth_first_search(g, visitor(vis));
}