3

我试图在无向图中找到属于任何循环的所有边。使用 Boost 的depth_first_search和我对back edges的理解，我不明白为什么在back_edge不包含任何循环的示例 Graph 中为两条边调用该方法。

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

using namespace std;
using namespace boost;

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

class MyVisitor : public default_dfs_visitor {
    public: void back_edge(Edge e, const Graph& g) const {
        // should only be called when cycle found, right?
        cerr << "back_edge " << e << endl;
        return;
    }
};

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

    MyVisitor vis;
    depth_first_search(g, visitor(vis));
    return 0;
}
4

1 回答 1

2

由于您的图是无向的，因此任何树边也是后边。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));
}
于 2013-10-15T21:32:54.337 回答